tag:blogger.com,1999:blog-8890204.post3059531502508462618..comments2024-06-14T02:45:02.104-04:00Comments on My Biased Coin: Text-book Algorithms at SODA (Guest Post, Mikkel Thorup)Michael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger32125tag:blogger.com,1999:blog-8890204.post-17065312947642152872009-12-23T22:21:05.239-05:002009-12-23T22:21:05.239-05:00Instead of taking papers on this theme (which woul...<i>Instead of taking papers on this theme (which would, incidentally, be a great idea), perhaps the area could serve as the basis for a lighter afternoon entertainment session, providing cool stuff that one could take home and show students.<br /></i><br /><br />Let me play the contrarian here.<br /><br />Just to be sure, I like what you call textbook algorithms. The hashing example is a great one. I think such papers should be accepted to SODA, and we should as a community probably appreciate such works more than we do. <br /><br />That being said, I disagree with the idea of a separate "track" or afternoon session for this area. Where would the resources come from? Would you accept fewer papers in SODA to make room? Would you add even more tracks? <br /><br />Book proofs are also hard to publish and we usually think more about them and try to use to them to generalize. Book algorithms combined with experimental comparison with known techniques would likely be accepted by SODA in the current setting. I do not support giving special treatment to one area, likely at the expense of others.<br /><br />I think we need to make sure the PC has members who are qualified to judge such submissions (most theoreticians aren't). In the meantime, such submissions need to work a little harder and make compelling arguments and give empirical support to their claims of efficiency.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-34004520700079360072009-12-23T09:36:51.610-05:002009-12-23T09:36:51.610-05:00There has been several comments/questions concerni...There has been several comments/questions concerning what is the fastest universal<br />hashing for strings etc. <br /><br />Just for the reference, in section 5<br />of the paper below, I survey what<br />I think are the fastest methods known on real computers. I do believe that they out-perform most non-universal multiplication-free hacks,<br />both in speed and in quality, e.g.,<br />recently I have used them to replace<br />FNV in applications. Of course, they cannot be as fast as the most naive hacks, e.g., just using the least significant bits.<br /><br />@INPROCEEDINGS{Tho09,<br /> AUTHOR = {Mikkel Thorup}, <br /> TITLE = "String hashing for linear probing",<br /> BOOKTITLE = {Proceedings of the 20th ACM-SIAM Symposium<br /> on Discrete Algorithms (SODA)}, <br /> YEAR = {2009},<br />pages ="655--664",<br />}Mikkel Thoruphttps://www.blogger.com/profile/10495805784088145688noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-71058794912949043882009-12-22T16:59:03.751-05:002009-12-22T16:59:03.751-05:00It sounds to me like what the SODA community needs...It sounds to me like what the SODA community needs is something analogous to Richard Bird's "Functional Pearls", which favour nifty presentations, and explicitly discourage the "5 to 10 pages of complications". (Declaration of interest: I now <a href="http://www.comlab.ox.ac.uk/people/Jeremy.Gibbons/pearls/" rel="nofollow">edit this column</a>.)Jeremy Gibbonshttps://www.blogger.com/profile/03945885134870183516noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-85641617809507556652009-12-22T02:09:27.978-05:002009-12-22T02:09:27.978-05:00The fastest 2 universal hashing algorithm appeared...The fastest 2 universal hashing algorithm appeared in stoc couple of years back: it runs in linear time. It is simple and elegant.... Though the ideas are nontrivial and use spielman codes. See the work of Ishai at alAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-30351048108807450792009-12-21T11:36:38.835-05:002009-12-21T11:36:38.835-05:00Three points:
0) I think it would be great if we
...Three points:<br /><br />0) I think it would be great if we<br />for text-book algorithms<br />had something like the Math Monthly in CS, going out cheaply to a wide audience (IPL is expensive and<br />commercial). Perhaps a good role for <br />Comm. ACM.<br /><br />1) I do not think it is in our interest if the best general text-book algorithms end up in applied conferences. Applied conferences <br />are even less likely to accept something<br />simple and elegant. They prefer to have it tied up in a system, and then it will be even harder to discover that this is a general purpose algorithm that goes beyond the limits of the applied conference.<br /><br />2) I do think theory of CS can be a bit too tied to certain traditional theoretical measures. One of the points<br />with the hashing scheme [DHKP97] is that<br />it gives a large constant factor in any reasonably realistic mathematical measure, e.g., taking into account that<br />w-bit multiplication is mod 2^w (discards overflow). This is not an experimental observation, but something that follows from the definition of standard programming languages like C. I do realize that the theory community does not care too much about details of the running times these days, but the hashing I mention is something of major impact, e.g., in the processing of high volume streams where the info is lost if not handled in time.Mikkel Thoruphttps://www.blogger.com/profile/10495805784088145688noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-65132574411878229462009-12-20T21:02:02.065-05:002009-12-20T21:02:02.065-05:00Dan Spielman wrote:
I would love to see more examp...Dan Spielman wrote:<br /><i>I would love to see more examples of textbook algorithms. If you have more in mind, please post them!</i><br /><br />Here are two examples of papers (of mine) that aren't nearly as useful as that hashing trick but have a little text-book flavor in the naturalness of the problems and simplicity of solutions (in my biased opinion).<br /><br /><a href="http://www.cs.brown.edu/~ws/papers/maxcut.pdf" rel="nofollow">Yet another algorithm for dense max cut: go greedy</a><br />* simple algorithm<br />* implementable except that constants are universe-sized if you want theoretical guarentee<br />* problem natural and interesting to theoreticians but not to practitioners<br />* main contribution simple idea but enough complications to make it look hard<br />* previous work got same results more complicated ways<br />* SODA accept<br /><br /><a href="http://www.cs.brown.edu/~ws/papers/scc.pdf" rel="nofollow">Finding Strongly Connected Components in Parallel using O(log^2 n) Reachability Queries</a><br />* simple algorithm<br />* very implementable and amenable to heuristic improvements<br />* problem of minor interest to practitioners<br />* analysis quite simple (important parts about 1 page), combining existing techniques in new but non-surprising ways.<br />* The previous work includes some quite famous people who would have scooped me if they had found my result obvious in foresight<br />* STOC reject, SPAA accept<br /><br />Dan Spielman wrote:<br /><i>As for getting them into SODA, I think we have a bit of a chicken-and-egg problem. Because they don't tend to appear in SODA, it is harder for a reviewer to become familiar with the state of the art. This makes it more difficult to make confident reviews.</i><br /><br />Another chicken-and-egg problem: with the current status quo the only text-book algorithms that are likely to be submitted to STOC/FOCS/SODA are those that the relevant practitioner communities are not inclined to accept at their own conferences. It's even harder for the reviewers to select the best text-book algorithms if the best aren't even submitted!Unknownhttps://www.blogger.com/profile/01106301822827737278noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-68671839796223502432009-12-20T20:06:15.944-05:002009-12-20T20:06:15.944-05:00I know it's just loosely related to the main t...I know it's just loosely related to the main topic of the discussion:<br /><br />Michael wrote:<br /><br />"I don't see why impact is harder to judge than "quality" for other theory papers."<br /><br />In the UK, there is a very interesting discussion about the quality vs the impact (usually, in the sense of economic impact though). See, for example, http://www.csc.liv.ac.uk/~leslie/impact/impact.html<br /><br />Most of people in the UK I know wouldn't agree with your claim: it's very difficult to assess "the impact".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-11172351968526036412009-12-20T15:05:05.418-05:002009-12-20T15:05:05.418-05:00I think we are conflating two different qualities ...I think we are conflating two different qualities of an algorithm here: is it simple, and is it useful (likely to have a big impact on disciplines outside of theory)? The hash example has both. We can judge simplicity immediately (and at theory conferences it is often seen as a negative), but the best test of usefulness is the test of time.<br /><br />As a demonstration that it is still possible to get simple algorithms into SODA (I make no claim of usefulness), I'll point to <a href="http://arxiv.org/abs/0909.1870" rel="nofollow">my own paper from this coming conference</a>. Simple algorithm for approximating max independent set: use the leaves of a depth-first search tree. Simple algorithm for approximating TSP when all distances are 1 or 2: use a depth-first ordering on the graph of distance-1 pairs. Although both problems are hard to approximate, one of these two is always a good approximation for any particular graph; the paper contains several similar results. The paper also does contain the requisite "5-10 pages of complications" that, as Mikkel observes, seem to be necessary to get something like this into a good theory conference.<br /><br />If an algorithm is simple and useful, but not theoretical novel (we already know an impractical solution to universal hashing, so why do we need another more practical one) then it needs more than theory to be published on its own: algorithm experiments showing it to be much better than the alternative, for instance, leading to a paper at ALENEX. This post seems to be arguing that the difficulty of publishing a purely theoretical algorithms paper for this sort of improvement is a systemic problem, but I'm not entirely convinced: if we want to argue that an algorithm is better than prior alternatives despite not giving us any new theoretical results, shouldn't there be some justification for that claim?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-25377871671571190422009-12-20T14:24:28.555-05:002009-12-20T14:24:28.555-05:00Notation overload is common in both math and CS pa...<i>Notation overload is common in both math and CS papers.</i><br /><br />Indeed. Imagine if TCS couldn't deal with the difference between the definitions of "source code" among programmers and information theorists!Unknownhttps://www.blogger.com/profile/14749446395269735704noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-7661623582100871182009-12-20T13:54:26.137-05:002009-12-20T13:54:26.137-05:00My main suggestion was that deriving good text boo...My main suggestion was that deriving good text book algorithms is<br />something that we should be competitive about, giving the best<br />contributions the same kind of conference credit that we do for other<br />important algorithmic contributions. They should lead to great talks.<br /><br />Authors of text books should be good at collecting and presenting the<br />best publicly known algorithms, but we cannot expect them to come up<br />with ideas for new more elegant algorithms than those already known.<br /><br />Currently, we don't really know what to do with a cool simple text book algorithm giving a really useful solution to an important<br />problem. They may just be discussed locally as folklore, and never<br />come out in public, or if they do, they may be well-hidden as part of<br />a solution to a different problem. Without proper published records,<br />it is hard to claim that one has a new better text book solution.<br /><br />I don't think evaluation is a principal problem. At STOC/FOCS we<br />already handle apples and oranges, e.g., algorithms and crypto. Math<br />has a long tradition for appreciating simpler proofs, and I think we<br />can all appreciate a really nice text book solution. If the abstract<br />uses the key-word "text book (style)" then reviewers should stop<br />looking for complexity and instead judge based on simplicity and<br />elegance, ease of implementation etc.<br />Needless to say that we still want <br />a clear new angle for the problem considered, as in my hashing example where [DHKP97] find an elegant use relative primality.Mikkel Thoruphttps://www.blogger.com/profile/10495805784088145688noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-66644192409659601302009-12-20T12:17:20.995-05:002009-12-20T12:17:20.995-05:00Perhaps there could be a special track for papers ...Perhaps there could be a special track for papers on textbook algorithms.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-36568455428618848082009-12-20T11:38:04.385-05:002009-12-20T11:38:04.385-05:00I would love to see more examples of textbook algo...I would love to see more examples of textbook algorithms. If you have more in mind, please post them!<br /><br />As for getting them into SODA, I think we have a bit of a chicken-and-egg problem. Because they don't tend to appear in SODA, it is harder for a reviewer to become familiar with the state of the art. This makes it more difficult to make confident reviews. <br /><br />It also makes it harder for the next textbook author to become aware of these algorithms!<br /><br />Perhaps someone should start a wiki or blog about textbook algorithms?Dan Spielmanhttps://www.blogger.com/profile/02430505190600344820noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-80035058802214756892009-12-20T00:12:34.250-05:002009-12-20T00:12:34.250-05:00Hi Adam. I'm glad you agree it would be a fun...Hi Adam. I'm glad you agree it would be a fun thing to try!<br /><br />I do wish to still register my disagreement with this paragraph:<br /><br /><i> The task of the SODA PC (note: I've also served on one of those) is to evaluate a paper's contribution to our broad algorithmic knowledge base. The notion of impact is much less well-defined, and this is why I think it is likely to be more subjective. </i><br /><br />Sentence 1: I think the type of thing Mikkel is talking about would certainly count as a "contribution to our broad algorithmic knowledge base". I don't think he's talking about programming tricks; he's talking about connecting the theory to implementation. I believe a SODA PC could/should judge these types of papers. Some efforts, though, would have to be made; as I stated in my earlier comment, I'm willing to cede that theorists have, as a community, moved so far from implementation that many theorists would not be suitable to review such papers. [I should point out I think that's a problem, that we as a community should be trying to fix...] At the same time, I feel underqualified when having to, for example, review a quantum computing paper for FOCS/STOC; that doesn't mean such papers shouldn't be submitted or accepted when I am on the PC, or even that I can't review them!<br /><br />Sentence 2: I don't see why impact is harder to judge than "quality" for other theory papers. I review a lot of papers; I see papers with valid proofs -- as valid (and sometimes moreso) than papers that are in FOCS/STOC -- that I think should be rejected from LATIN. What separates one class of papers from another? My (or, rather, the community's) subjective notion of what's "interesting", "quality" work. <br /><br />Impact can be demonstrated through actual implementations and deployment (in which case I think such judgments will not be subjective), or potential impact can be gauged by suitable reviewers -- of which there are many available. Yes, there will be some subjective judgment in choosing papers for potential rather than demonstrated impact -- but such subjective judgments are made all the time, even for purely theoretical papers.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-77671199971452059832009-12-19T19:59:50.228-05:002009-12-19T19:59:50.228-05:00Answering Michael M. (NB: threading comments would...Answering Michael M. (NB: threading comments would be helpful here):<br /><br />I understand that systems-oriented communities evaluate impact all the time and fairly reliably. (I have seen this in action on various "applied" security PCs and panels.) However, they do it in an application-specific context. And when they referee papers that step a little outside their specialty, they tend to be much less reliable (I am thinking, for example, of papers on privacy at database, datamining and security conferences). <br /><br />The task of the SODA PC (note: I've also served on one of those) is to evaluate a paper's contribution to our broad algorithmic knowledge base. The notion of impact is much less well-defined, and this is why I think it is likely to be more subjective.<br /><br />All that said, it would be great to do the experiment and try it at some upcoming SODA.<br /><br />PS: As for x mod y: I encountered this notation overload in my first abstract algebra class in college. The professor explained briefly the differences between the two widespread uses of the notation, and from then on I always was able to deduce, from context, which meaning of "mod" was intended. Notation overload is common in both math and CS papers. Sometimes it's bad, sometimes it's good. I don't think it has much to do with the relative importance of mathematical depth in different fields.Adam Smithhttp://www.cse.psu.edu/~asmithnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-84374084457877658492009-12-19T19:44:46.058-05:002009-12-19T19:44:46.058-05:00I'd rather see discussion of Mikkel's poin...<i><br />I'd rather see discussion of Mikkel's points here; feel free to continue this arcane and inane discussion <br /></i><br /><br />This discussion is not arcane and in fact might in fact be pertinent to the point in the original post.<br /><br />Clearly, there are two views about TCS. From one point of view, algorithms are like any other mathematical objects, and proving bounds on their complexity is a natural mathematical endeavor (akin to proving uniform bounds in any other area of mathematics). From this point of view, questions of "practicality" is really outside the domain of TCS, best left to the "practitioners". To people who subscribe to this point of view, writing "a mod b" when one means "rem(a,b)" is a horror of horrors. <br /><br />A second point of view of algorithms (that perhaps the original poster subscribes to) holds practicality as the more important goal. From this point of view mathematical rigor (and its associated baggage of culture and discipline etc.) fades into background, and such basic questions about notation becomes moot.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-42046170463252171052009-12-19T19:20:12.982-05:002009-12-19T19:20:12.982-05:00but TCS is not a subfield of number theory -- and ...<i><br />but TCS is not a subfield of number theory -- and hence has its own style and variants of notation.<br /></i><br /><br />TCS is certainly not a subfield of number theory, but it is a mathematical field. For instance, ECCC the principal repository of papers of TCS, requires that the papers it accepts have ...<br />" ... clear mathematical profile and<br /> strictly mathematical format."<br /><br />As a mathematical discipline TCS papers should stick to commonly accepted mathematical formalism -- deviating from these principles usually results in controversies such as Neal Koblitz's well publicized and justified criticism of TCS style cryptography.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-9253238067102189312009-12-19T18:51:09.416-05:002009-12-19T18:51:09.416-05:00I'd rather see discussion of Mikkel's poin...I'd rather see discussion of Mikkel's points here; feel free to continue this arcane and inane discussion about x mod y <a href="http://jonkatz.wordpress.com/2009/12/19/x-mod-y-is-now-controversial/" rel="nofollow">elsewhere</a>.Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-25290530375729209162009-12-19T18:28:40.877-05:002009-12-19T18:28:40.877-05:00"This careless attitude towards mathematical ..."This careless attitude towards mathematical language and notation is a persistent problem in theoretical CS literature (probably due to a lack of proper training in mathematical writing). However, unless such levity with mathematical notation is gotten rid of, it is hard to take such papers seriously."<br /><br />Really?? this for a notation for x mod y? It amazes me how easy you find it to belittle the mathematical maturity/training of an entire area by the somewhat different notation they use for such a simple concept, a concept that everyone understood back in highschool. Admittedly, the notation is different from what is common in number theory, but TCS is not a subfield of number theory -- and hence has its own style and variants of notation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-26786111427929038002009-12-19T14:00:18.083-05:002009-12-19T14:00:18.083-05:00x mod y
(where y is a positive integer), written ...<i><br />x mod y<br /><br />(where y is a positive integer), written in LaTeX using \bmod, is the non-negative integer that is less than y and is congruent to x (mod y).<br /></i><br /><br />This is a very bad and confusing notation that needs to be avoided. It involves an arbitrary choice of representative from a congruence class. Normally, there is no sensible choice of such a representative (for example, when one "mods" out by a vector subspace in a vector space). Moreover, it conflicts with the standard definition of "modulo" as the equivalence relation induced by quotienting by a sub-object.<br /><br />In the number theoretic context, or in the case of rings of polynomials in one variable or other Euclidean domains, the notation rem(a,b) -- the remainder of a after dividing by b -- is well defined (upto multiplication by units) and should be used instead. <br /><br />Unlike, what some other commentators have said, this is not a matter of mathematical pedantry at all. Language is a very (most ?) important aspect of mathematics, and should be respected as such. Choice of the right notation often makes complicated statements look completely obvious -- and the ultimate goal of mathematics is to make the "unobvious look obvious" and a huge part of that is the right choice of notation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-7999757900177748302009-12-19T11:47:50.231-05:002009-12-19T11:47:50.231-05:00As someone who's spent far more time on comput...As someone who's spent far more time on computer program efficiency than on theoretical computer science, that example comes off to me as pretty cool (though I'm still wondering what the "(*)" is doing there, and a bit distressed that a computer scientist can be so theoretical that he or she forgets what "mod" means in an algorithm as opposed to in number theory). It also explains a lot about my publication record: My advisor wrote a defining textbook, renown for the brevity of its proofs and explanations. But his favorite result of mine, something sort and sweet, was rejected by referees. I had to eventually just shoehorn it in to a somewhat related paper. Your point makes the case for accepting short papers as a special case. If it were clear what was being asked for and if the acceptance rate were low enough, getting one of them in could be even more prestigious than having a full paper (Eventually I could envision the following process: Prepare the short result; if that gets rejected as too "uncomplicated," then add to it for the next conference.) But first you have to make room. Sadly, some forums (e.g., IEEE Transactions on Information Theory) have done just the opposite.Unknownhttps://www.blogger.com/profile/14749446395269735704noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-81743629423918144422009-12-19T08:21:15.630-05:002009-12-19T08:21:15.630-05:00Here is my eurocent: The background knowledge of t...Here is my eurocent: The background knowledge of the reader determines what is complicated and what is not. With space constraints, authors must judge how much background to include. Even without space constraints, you run the risk of boring your readers if you include too much background.<br /><br />How hard it is to understand a paper is mainly a function of the overlap between the background knowledge of the writer and that of the reader and secondarily a function of the author's writing skills. It is <i>not</i> a function of the value of the idea being presented.<br /><br />A good paper should be <i>easy to understand</i> and <i>useful</i>. Of course, the trick is that "useful" means different things to different people: can be put in a program, reveals unexpected theoretical connections, etc.<br /><br />Now let me tell you a secret. I wrote the above because I felt obliged to contribute to the main subject to earn the right to ask my silly(?) question.<br /><br />My TAoCP copy recommends the hashing scheme <i>h_b(x) = ((bx) mod 2^w) div 2^(w-u)</i>, with <i>b</i> being an odd number close to 2^w/1.62. (The golden ratio is supposed to make it work well for keys in arithmetic progression. And then says how for hashing short strings something different than the golden ration works better.) Knuth credits Floyd for 'most of these ideas'. So the main observation of [DHKP97] is that random (odd) <i>b</i>s gives a universal <i>set</i> of hash functions. Right?<br /><br />PS: The complaint about 'mod' not being a binary operator illustrated perfectly the background mismatch I mentioned earlier. I know I'm evil, but I found it hilarious.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-83773576500236188282009-12-18T23:48:34.634-05:002009-12-18T23:48:34.634-05:00Adam,
I think I disagree with your final point:
...Adam,<br /><br />I think I disagree with your final point:<br /><br />"How do we measure impact reliably? Whatever the answer is, it will probably look very different from (and, my gut suggests, more subjective than) the criteria that are currently the norm in theory."<br /><br />Perhaps it is my experience in networking/systems conferences, but I think that reasonable PCs can perfectly well assess how interesting an algorithm implementation idea is. In systems conferences, a major component of what they do is determine which implementations they think are interesting and will have the most impact, in terms of the actual implementation or the underlying ideas. I'd agree some of the criteria are different than those used in judging theory papers, and I'd agree that the theory community, as a whole, has not exercised this type of judgment sufficiently in, say, the last two decades and would have to "re-train those muscles," so to speak. But I think that impact (realized or potential) can be adequately judged by people who work on algorithms "in the real world", and their judgments would likely be no more (and possibly would be less) subjective than those used to decide what papers get into theory conferences currently. <br /><br />The main judgment, I think, would be, "Would I or someone I know potentially find this useful?" People who code and deploy algorithms regularly will, I think, have good judgment about what sort of things pass this test. Of course, good papers will attempt to demonstrate that their algorithm is useful in real-world contexts by explaining where they could be used or actually showing their performance in real applications.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-30447304479550050512009-12-18T23:34:28.301-05:002009-12-18T23:34:28.301-05:00Anon #4: It's pretty clear that Mikkel has us...Anon #4: It's pretty clear that Mikkel has used "math terminology" to contrast with the line later in his text that he labeled "C code" -- the point being is that while the two equations look quite similar at the mathematical level, they're quite different at the code implementation level. And yes, he's using mod as a binary operator here. <br /><br />(Still, always nice to have some mathematical pedant to point out that mod is an equivalence relation so how can we computer scientists write things like a = 1 mod p ; I get one in my algorithms class most every year, too!) <br /><br />I do hope as DE suggests we go back to comments on the actual theme of Mikkel's post, which relates to why there are so few algorithms-as-I-like-to-define-them (that is, algorithms that people might actually use in running programs) at a conference like SODA, and whether perhaps that could be changed.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-50410243821189927532009-12-18T23:31:49.620-05:002009-12-18T23:31:49.620-05:00To get back on to the topic of the post:
I think ...To get back on to the topic of the post:<br /><br />I think one of the reasons that simple ideas (algorithms, models, whatever) have trouble getting accepted to conferences is that it is much harder to referee them; their value is tricky to assess. <br /><br />Some reasons:<br /><br />1) It is difficult to assess the novelty of something that is obvious in retrospect. (What if it was folklore? What if it was an idea that was "in the air" but not really folklore yet?) It is remarkably easy to convince yourself that you basically knew something but had never bothered to flesh out the idea... unless fleshing out the idea obviously took a month of time from someone talented and technically well-versed in the details of a field.<br /><br />2) There are lots clean, nontrivial implementation ideas that aren't all that important since they are not the bottleneck in any crucial applications. <br /><br />In most communities, simple nontrivial ideas can get attention as long as they change the state of the art for some important problem. For example, if you last year you had come up with a simple trick that halved the error rate of prediction algorithms for the Netflix prize, you would have gotten $1M. <br />And similarly, simple ideas that solve important open problems in theory (think Moser's STOC best paper) get well-deserved praise. <br /><br />I like the idea of an afternoon at SODA devoted to the type of work described in Mikkel's post. IPL is also a good journal venue for them. <br /><br />My question is: if we want major *theory* conferences to reward this type of work with publication in the main track, how should we evaluate the submissions? <br /><br />Again: improving a widely deployed algorithm (like universal hashing) is pretty clearly a good thing; but what if I improve my own algorithm, that is not yet widely deployed? How do we measure impact reliably? Whatever the answer is, it will probably look very different from (and, my gut suggests, more subjective than) the criteria that are currently the norm in theory.Adam Smithhttp://www.cse.psu.edu/~asmithnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-4018783228699954372009-12-18T20:48:42.957-05:002009-12-18T20:48:42.957-05:00On the off-topic thread: it is clear that C gets m...On the off-topic thread: it is clear that C gets modular arithmetic wrong, but it is not entirely clear what the correct answer is in the unusual case that the modulous is negative. For example should 5 mod -3 equal 2 or -1?<br /><br />See http://portal.acm.org/citation.cfm?id=128862Unknownhttps://www.blogger.com/profile/01106301822827737278noreply@blogger.com