My take on computer science --
algorithms, networking, information theory --
and related items.
Thursday, June 18, 2009
SLOGN
While people are all talking about ICS, another new conference was also being whispered about in the hallways at STOC. I'm happy to say that SLOGN now has a call for papers up (sent to me by Ryan O'Donnell and Rocco Servedio). It promises to be something different entirely.
This sounded just right for the paper I am finishing up, all about shaving off a sublogarithmic factor. The location seems a bit inaccessible, though. :(
It seems like you guys forgot one thing. If there is any mention of an experiment or implementation in the submission, then the submission would be immediately rejected. Of course, if they need to implement their algorithm or do any experiments, then the theory is not strong enough!
I do not understand this sentiment against writing thirty page papers which uses deep mathematics. It should now be obvious to everyone that any paper settling or even making non-zero progress on the central questions of TCS (namely, those around the P/NP problem) will be considerably longer than thirty pages and will involve rather deep mathematics. While I understand that not everyone will want to work on such questions, I think it has suddenly become fashionable to uphold simplicity as a prime virtue, and technical mastery as some kind showmanship which should be exposed and vilified. Short simple-minded papers in TCS which contain little or no mathematics are usually mostly drivel.
To Anon 7:18pm, if any paper proposes an _algorithm_ then isn't that clearly a ground for its rejection? After all, can algorithms be deep mathematics?
Proof Verification and the Hardness of Approximation Problems, by S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, 54 pages. "For shaving a sqrt(log n) factor off the query complexity in [AS92]."
Expander Flows, Geometric Embeddings and Graph Partitioning, by S. Arora, S. Rao, U. Vazirani, 30 pages. "For improving on the 16-year-old approximation ratio for Sparsest-Cut by a sqrt(log n) factor."
Triangulating a Simple Polygon in Linear Time, by B. Chazelle, 40 pages. "For shaving a log^*n factor off the previous best running time."
Free Bits, PCPs, and Non-Approximability -- Towards Tight Results, by M. Bellare, O. Goldreich, M. Sudan, 113 pages. "For the bound of 0.55218507 in Case 2.2.1.3 on page 66."
A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(sqrt{V} E) General Graph Matching Algorithm, by V. Vazirani, 57 pages. "For providing full details of the seminal fast matching algorithm of Micali and Vazirani."
The Complexity of Computing a Nash Equilibrium, by C. Daskalakis, P. Goldberg, C. Papadimitriou, 70 pages. "For pushing PPAD-completeness down from 4- to 3- to 2-player games."
How are we supposed to submit? Does anyone know if they'll use easychair.
Anon #5: I think if the algorithm is so unnatural that no one would consider implementing it or has prohibitively high O(1) constants it would be considered.
"I think if the algorithm is so unnatural that no one would consider implementing it or has prohibitively high O(1) constants it would be considered."
I think though that amongst algorithmic results, only those which prove the existence of an algorithm with certain complexity, but is unable to explicitly describe them, would have a chance to be accepted. A proof that having an explicit description would imply that the either the Hodge conjecture or the GRH is false will seal the deal.
While I do not generally advertise on the blog, I do sometimes link to books, and I take part in the Amazon Associates program, getting some small credit if you purchase a book I recommend.
8 comments:
Excellent !!
This sounded just right for the paper I am finishing up, all about shaving off a sublogarithmic factor. The location seems a bit inaccessible, though. :(
It seems like you guys forgot one thing. If there is any mention of an experiment or implementation in the submission, then the submission would be immediately rejected. Of course, if they need to implement their algorithm or do any experiments, then the theory is not strong enough!
I do not understand this sentiment against writing thirty page papers which uses deep mathematics. It should now be obvious to everyone that any paper settling or even making non-zero progress on the central questions of TCS (namely, those around the P/NP problem) will be considerably longer than thirty pages and will involve rather deep mathematics. While I understand that not everyone will want to work on such questions, I think it has suddenly become fashionable to uphold simplicity as a prime virtue, and technical mastery as some kind showmanship which should be exposed and vilified. Short simple-minded papers in TCS which contain little or no mathematics are usually mostly drivel.
To Anon 7:18pm, if any paper proposes an _algorithm_ then isn't that clearly a ground for its rejection? After all, can algorithms be deep mathematics?
Previous winners of the SLOGN "Best Paper" award:
Proof Verification and the Hardness of Approximation Problems, by S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, 54 pages. "For shaving a sqrt(log n) factor off the query complexity in [AS92]."
Expander Flows, Geometric Embeddings and Graph Partitioning, by S. Arora, S. Rao, U. Vazirani, 30 pages. "For improving on the 16-year-old approximation ratio for Sparsest-Cut by a sqrt(log n) factor."
Triangulating a Simple Polygon in Linear Time, by B. Chazelle, 40 pages. "For shaving a log^*n factor off the previous best running time."
Free Bits, PCPs, and Non-Approximability -- Towards Tight Results, by M. Bellare, O. Goldreich, M. Sudan, 113 pages. "For the bound of 0.55218507 in Case 2.2.1.3 on page 66."
A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(sqrt{V} E) General Graph Matching Algorithm, by V. Vazirani, 57 pages. "For providing full details of the seminal fast matching algorithm of Micali and Vazirani."
The Complexity of Computing a Nash Equilibrium, by C. Daskalakis, P. Goldberg, C. Papadimitriou, 70 pages. "For pushing PPAD-completeness down from 4- to 3- to 2-player games."
How are we supposed to submit? Does anyone know if they'll use easychair.
Anon #5: I think if the algorithm is so unnatural that no one would consider implementing it or has prohibitively high O(1) constants it would be considered.
"I think if the algorithm is so unnatural that no one would consider implementing it or has prohibitively high O(1) constants it would be considered."
I think though that amongst algorithmic results, only those which prove the existence of an algorithm with certain complexity, but is unable to explicitly describe them, would have a chance to be accepted. A proof that having an explicit description would imply that the either the Hodge conjecture or the GRH is false will seal the deal.
Post a Comment