tag:blogger.com,1999:blog-786333285568106173.post2453126021975746241..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Top 10 Theory ImpactMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-786333285568106173.post-4138427435454164922007-09-17T21:31:00.000-04:002007-09-17T21:31:00.000-04:00Despite the fact that building decent quantum comp...<I><BR/>Despite the fact that building decent quantum computers is still on the "to do" list, the impact of quantum computing outside of theory is hard to beat.<BR/></I><BR/><BR/>What does "impact" mean? If you mean that lots of non-theoreticians think quantum computing is really cool and want to hear more about it, then I agree that it has had a big impact. On the other hand, I know of no non-theoretical intellectual/research impact, except for attempts to build a quantum computer. They aren't theoretical, but they aren't practical either.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-84797332808834232132007-09-07T14:17:00.000-04:002007-09-07T14:17:00.000-04:00> Can we take any credit for machine learning algo...> Can we take any credit for machine learning algorithms? (Adaboost?)<BR/><BR/>We better - the <A HREF="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=63451" REL="nofollow">first</A> boosting paper appeared in FOCS'89.<BR/><BR/>I would definitely add quantum <EM>computing</EM> to the list. Despite the fact that building decent quantum computers is still on the "to do" list, the impact of quantum computing outside of theory is hard to beat.<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-83487021771838851782007-09-07T10:02:00.000-04:002007-09-07T10:02:00.000-04:00Range trees/R-trees.Text indexing advances over th...Range trees/R-trees.<BR/><BR/>Text indexing advances over the last two decades which have made massive search engines possible.<BR/><BR/>Quantum cryptography.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-13865261786321145922007-09-06T22:53:00.000-04:002007-09-06T22:53:00.000-04:00Obviously, I'd argue for the "power of two choices...Obviously, I'd argue for the "power of two choices", or Balanced Allocations, which is having more impact that people realize (and now it's "cousin" cuckoo hashing as well), though this fits more generally into the hashing theme.<BR/><BR/>Along these lines, I'd certainly argue for universal hash functions and Bloom filters; although they don't fit into the "past 25 years" restriction, their power has only really been understood quite recently. (It took a while for practice to catch up with theory there!)<BR/><BR/>Looking at my syllabus for CS 222, I'd add: <BR/><BR/>Eigenvalue methods, certainly. (PageRank, HITS, SALSA, Eigentrust, PICASHOW...)<BR/><BR/>Dimensionality reduction/sketching.<BR/>(Min-wise independent hash families.)<BR/><BR/>Streaming algorithms. (In particular, algorithms for finding "heavy hitters" or elephants.)<BR/><BR/>Network coding (well, maybe, give it 5 years). <BR/><BR/>All the basic theoretically designed peer-to-peer network constructions. <BR/><BR/>Can we take any credit for machine learning algorithms? (Adaboost?)Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-60060764657450786282007-09-06T10:55:00.000-04:002007-09-06T10:55:00.000-04:00Probabilistic roadmaps for robotics.Skip lists.Probabilistic roadmaps for robotics.<BR/><BR/>Skip lists.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6019991409249962262007-09-06T03:54:00.000-04:002007-09-06T03:54:00.000-04:00* text compression and indexing: Lempel-Ziv compre...* text compression and indexing: Lempel-Ziv compression, and more recently Burrows-Wheeler compression and text indices like the FM-index<BR/><BR/>* Sequencing algorithms for biology: Developed by theorists, and based on classical combinatorial-algorithms thinking.<BR/><BR/>* Google/Eigenvalue methodsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6508660601266057132007-09-05T21:33:00.000-04:002007-09-05T21:33:00.000-04:00Some candidates [with a heavy bias :-)]--(*) Torna...Some candidates [with a heavy bias :-)]--<BR/><BR/>(*) Tornado codes (Luby, Mitzenmacher, Shokrollahi and Spielman) and more generally their work on irregular LDPC codes. This work was one of the prime reasons for resurgence of the study of LDPC codes in coding theory and practice (including the birth of Digital Fountain).<BR/><BR/>(*) List decoding algorithm for Reed-Solomon codes by Sudan (and the improvements to it by Guruswami-Sudan). As far as I know there are no commercial implementations (yet) but these papers have been highly influential in coding theory.Unknownhttps://www.blogger.com/profile/04612761074500356923noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-31253563513047454222007-09-05T16:15:00.000-04:002007-09-05T16:15:00.000-04:00This is what the Kanellakis prize is for, btw.* pu...This is what the Kanellakis prize is for, btw.<BR/><BR/>* public-key cryptography, specifically Diffie-Helman and RSA (technically it's 30 years though)<BR/><BR/>* Hashing (FKS, etc etc)<BR/><BR/>* Splay trees (now I'm just going through the Kanellakis prize list :))<BR/><BR/>* PCPs and approximations: not directly, but indirectly, by bringing the study of approximation algorithms front and center. <BR/><BR/>* Nearest neighbour methods (LSH and the like)<BR/><BR/>* Interior point methods: maybe, although I always thought that people still preferred to use simplex<BR/><BR/>* The data streaming model: certainly.<BR/><BR/>* Hubs and Authorities/Page rank ! or, 'eigenvalues of matrices/random walks'. You'd be surprised how often methods based on random walks/hubs-authorities are used.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-7813851712906780792007-09-05T15:44:00.000-04:002007-09-05T15:44:00.000-04:00Thanks, Mihai, for raising this question on the bl...Thanks, Mihai, for raising this question on the blog. My reasons for focusing on the last 25 years are:<BR/>- We should be able to present examples that are not too old to argue that what we are doing now matters.<BR/>- To avoid the counter-argument: <I>"of course, many fundamental things were pointed out in the first years of computers, but these were things that other people would have realized soon enough"</I>.<BR/><BR/>Some candidates for the list:<BR/>- Elliptic curve cryptography?<BR/>- Streaming algorithms?<BR/>- Interior point methods?Rasmus Paghhttps://www.blogger.com/profile/05722627403861422993noreply@blogger.com