<p>One research area that uses empirical methods and methods of Theoretical Computer Science is the field called "Experimental Algorithmics" or "Algorithm Engineering". Like Chris mentioned, high performance computing relies heavily on this as modern systems have complex cache and latency issues that we have a hard time modeling.</p>

<p><a href="http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/b/Brodal:Gerth_St=oslash=lting.html" rel="nofollow noreferrer">Gerth Brodal</a> and <a href="http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Sanders:Peter.html" rel="nofollow noreferrer">Peter Sanders</a> are good examples of researchers who maintain a foot in both the "proof" and "empirical" realms.</p>

<p>--Update 1/20/2013--
I would also mention a great presentation by <a href="http://www.cs.princeton.edu/~rs/talks/ScienceCS.pdf" rel="nofollow noreferrer">Robert Sedgewick</a>.</p>

CC BY-SA 3.0
2014-11-20T18:14:10.530Z
@Raphael You would have to model a sphere around each VonNeuman compute node and explicitly put and get memory objects with a latency cost proportional to the distance; random access is $O(CubeRoot(n))$, the diameter of the memory sphere, speed of light is your best case latency.
Chad Brewbaker
CC BY-SA 2.5
2011-02-22T23:53:15.933Z
Both ALENEX and ESA encourage applied algorithms work, and there's also a conference (SAE) on this topic.
Suresh Venkat
CC BY-SA 2.5
2011-02-23T04:31:59.317Z
What is SAE? That TLA is ungoogleable.  Do you have a URL for it?
Peter Boothe
CC BY-SA 2.5
2011-02-23T07:23:26.213Z
SAE is a typo for SEA, the Symposium on Experimental Algorithms.
David Eppstein
CC BY-SA 2.5
2011-02-24T17:24:07.103Z
You can also do Algorithm Engineering in a more rigorous way, i.e. refine theoritcal models so they fit reality but stil do precise analyses. It's hard, though.
Raphael
CC BY-SA 3.0
2011-02-22T23:03:34.110Z
2017-01-05T13:45:53.907Z
2017-01-05T13:45:53.907Z
Chad Brewbaker
<p>Implementing algorithms well is a skill which takes a different set of tools than just proving theorems. Many algorithms which were discovered by the theory community have indeed been implemented in practice (although I would like to see the theory community take a bigger role in this process). Physics doesn't ask the same researchers to do theory and experiment, although it is expected that the two groups communicate. Why shouldn't you expect to see the same divide in computer science?</p>

<p>ADDED IN EDIT:</p>

<p>Expanding on my comment in answer to Suresh's about what I meant by "role" above, at Bell Labs and AT&amp;T Labs, researchers in algorithms were encouraged to talk to people in development. I didn't do as much of this as I probably should have, but I did get <a href="http://www.springerlink.com/content/v7227874015t1l6m/">at least one paper</a> out of it, and I think it would be good for the field if there were more communication between people in theory at universities and practitioners. This doesn't mean that I think everybody who comes up with an algorithm should code it (even if it's practical).</p>

<p>On the other hand, coding algorithms (or having a student code them) that you think might be practical can be useful in getting them adapted by practitioners. Consider one example. Lempel and Ziv wrote two technical papers in 1977 and 1978 on new data compression algorithms. Everybody ignored them. In 1984, Welch wrote <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&amp;arnumber=1659158&amp;isnumber=34743">a much less technical paper</a> giving a slight twist on LZ78 that improved its performance somewhat, and gave the results of a small study comparing its performance with other data compression methods. It was published in a journal read by a number of programmers, and the algorithm was given by a few lines of pseudocode. The method was quickly adapted in a number of places, eventually resulting in an infamous intellectual property dispute.</p>

<p>Of course, one of the best ways for algorithms researchers to communicate with practice is to produce grad students who go off and work at Google, IBM, or other companies, and we're already doing that. Another way might be to answer practitioner's questions in this forum. Hopefully, we're doing a reasonable job of that as well.</p>

CC BY-SA 2.5
2011-02-23T21:51:19.223Z
So you're saying that even though in physics there's no expectation of the same person doing both, in theoryCS we should do both ? is it because models of computation are much more of an approximation to reality than physics models ?
Suresh Venkat
CC BY-SA 2.5
2011-02-23T22:02:03.610Z
I'm saying that the theorists should talk more to the practitioners. If you look at the history of physics, bad things start happening when theorists stop talking to experimentalists. I actually think we have a reasonable amount of communication between the two groups right now, but that it wouldn't hurt to have some more.
Peter Shor 
CC BY-SA 2.5
2011-02-23T22:27:49.207Z
I won't generalize but I think that many researchers simply cannot code/don't like to and they would rather let the practical work be done by one of their students. That's the case with me and my mentor.
toto
CC BY-SA 2.5
2011-02-24T13:13:20.430Z
The tension associated to formal specification versus practical computation goes far back in STEM history.   Sometimes formal specification leads (von Neumann's "On the theory of stationary detonation waves" [1948] versus subsequent computational simulations) and sometimes practical computation leads (Bowditch's "New American Practical Navigator" [1807] versus Gauss' "Disquisitiones generales circa superficies curvas" [1827]).  The greatest mathematicians (Gauss and von Neumann in the examples cited above) have often combined formal specifications with practical computations.
John Sidles
CC BY-SA 2.5
2011-02-24T16:57:38.727Z
Nice. btw in retrospect my comment made it sound like I was arguing with you, whereas my intent was only clarification. I also know well the beneficial aspects at AT&T of talking to researchers outside algorithms :)
Suresh Venkat
CC BY-SA 2.5
2011-02-26T14:53:34.847Z
The history of Lempel-Ziv, and looking at posts on StackOverflow, have just led me to formulate a very simple precept which might help get algorithms theorists come up with implemented vy practitioners: *If you think your algorithm might be practical, put pseudocode in your paper.*
Peter Shor 
CC BY-SA 2.5
2011-02-23T21:35:21.287Z
2011-02-24T12:08:00.230Z
2011-02-24T12:08:00.230Z
Peter Shor 
<p>This depends on the discipline you are in; as Jeremy states, there is a spectrum of theory vs. practice.</p>

<p>Topics like <em>complexity</em> tend to be weighted towards the theory side, as often the goal is to find a boundary for the space or runtime. Implementing an algorithm in C++ and then running it a bunch of times isn't going to prove that a problem is NP-complete.</p>

<p>As a polar opposite, <em>high-performance computing</em> (with conferences like <a href="http://supercomputing.org/" rel="noreferrer">Supercomputing</a>) are all empirical; no one would ever submit a proof to an HPC publication as there is too much variability with regard to memory hierarchy and kernel overhead.</p>

<p>So what seems like the same question (How long does something take to run?) will be approached two completely different ways depending on the goals, techniques, community, etc. See Poul-Henning Kamp's <a href="http://queue.acm.org/detail.cfm?id=1814327" rel="noreferrer">You're Doing It Wrong</a> for an example of the dissonance.</p>

CC BY-SA 2.5
2011-02-22T22:00:19.597Z
2011-02-24T18:29:15.910Z
2011-02-24T18:29:15.910Z
chrisaycock
<p>In programming languages research many ideas for new programming language constructs or new type checking mechanisms stem from theory (perhaps informed by experience in practice, perhaps not). Often a paper is written about such mechanisms from a formal/theoretical/conceptual perspective. That's relatively easy to do. Next comes the first hurdle: implementing the new constructs in the context of an existing compiler and experimenting with it, in terms of efficiency or flexibility. This too is relatively easy. </p>

<p>But can we then say that the programming construct constitutes an advance to the science of programming? Can we say that it makes writing programs easier? Can we say that it makes the programming language better?</p>

<p>The answer is no. A proper empirical evaluation involving scores of experienced programmers over large periods of time would be needed to answer those kinds of questions. This research is hardly ever done. The only judge of the value of a programming language (and its constructs) is the popularity of the language. And for programming language purists, this goes against what our hypotheses tell us.</p>

CC BY-SA 2.5
2011-02-23T07:20:47.760Z
2011-02-23T07:20:47.760Z
Dave Clarke
<p>Perhaps I'm missing the motivation for your question but there are many examples of empirical results motivating research, algorithms and other results.</p>

<p><a href="http://en.wikipedia.org/wiki/MP3">MP3</a> use <a href="http://en.wikipedia.org/wiki/Psychoacoustics">psychoacoustic</a> to optimize the algorithm for human encoding.</p>

<p><a href="http://groups.google.com/group/sci.math.symbolic/browse_thread/thread/6b79152956098607/28159974a1fe298e?pli=1">Plouffe</a> gives an account of discovering the <a href="http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula">BBP spigot algorithm for the digits of $\pi$</a> where he recounts the use of whatever <a href="http://en.wikipedia.org/wiki/Integer_relation_algorithm">Integer Relation Algorithm</a> Mathematica was using to discover the formula.</p>

<p>Along the same line, Bailey and Borwein are big proponents of experimental mathematics.  See <a href="http://rads.stackoverflow.com/amzn/click/1568813430">"The Computer as Crucible: An Introduction to Experimental Mathematics"</a>, <a href="http://rads.stackoverflow.com/amzn/click/1441930000">"Computational Excursions in Number Theory"</a> amongst <a href="http://www.amazon.com/s/ref=ntt_athr_dp_sr_1?_encoding=UTF8&amp;sort=relevancerank&amp;search-alias=books&amp;field-author=Jonathan%20Borwein#/ref=sr_pg_1?rh=n%3A283155%2Cp_27%3AJonathan+Borwein&amp;sort=relevancerank&amp;ie=UTF8&amp;qid=1298576327">others</a>.  One might argue that this is more experimental <em>Mathematics</em> but I would argue that at this level the discussion the distinction is semantic.</p>

<p>Phase transitions of NP-Complete problems are another area where empirical results are heavily used.  See <a href="http://www.math.ucla.edu/~percus/Teaching/RIPS/nature.pdf">Monasson, Zecchina, Kirkpatrick, Selman and Troyansky</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.2866&amp;rep=rep1&amp;type=pdf">Gent and Walsh</a>  for starters, though there are many, many more (see <a href="http://www.tud.ttu.ee/material/enn/GraphTheory/0602129v1.pdf">here</a> for a brief survey).</p>

<p>Though not quite on the level of Theoretical Computer Science or Mathematics, there is a discussion <a href="http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/#fish_made_a_mess">here</a> about how the unix utility grep's average case runtime beats optimized worst case algorithms because it relies on the fact that it's searching human readable text (grep does as bad or worst on files with random characters in them).</p>

<p>Even Gauss used <a href="http://en.wikipedia.org/wiki/Prime_number_theorem#History_of_the_asymptotic_law_of_distribution_of_prime_numbers_and_its_proof">experimental evidence</a> to give his hypothesis of the Prime Number Theorem.</p>

<p>Data mining (<a href="http://www.netflixprize.com/assets/ProgressPrize2008_BellKor.pdf">Bellkor's solution</a> to the <a href="http://en.wikipedia.org/wiki/Netflix_Prize">Netflix Prize</a> to make a better recommendation system) might be argued to be a theory completely based on empirical evidence.  Artificial Intelligence (genetic algorithms, neural networks, etc.) relies heavily on experimentation.  Cryptography is in a constant push and pull between code makers and code breakers.  I've really only named a few and if you relax your definition of empirical, then you could cast an even wider net.</p>

<p>My apologies for being so scattered in answering your question but I hope I've given at least a few examples that are helpful.</p>

CC BY-SA 2.5
2011-02-24T20:07:19.183Z
2011-02-24T20:07:19.183Z
user834
<p>Mathematics is a science also, and you would have to search for a long time to find published empirical results in this field (although I guess there must be some).  There are other scientific domains where "lemmas and proofs" are valued over experience, such as quantum physics. That said, most sciences mix theory and practice (with various ratios), and Computer Science is no exception.</p>

<p>Computer Science has its roots in Mathematics (see Turing's biography for instance <a href="http://en.wikipedia.org/wiki/Alan_Turing">http://en.wikipedia.org/wiki/Alan_Turing</a>), and as such many results (generally dubbed as in the field of "theoretical computer science") consist in proofs that computers in some computational model can solve some problem in a given amount of operations (e.g. conferences such as FOCS, STOC, SODA, SoCG, etc..). Nevertheless, many other results of computer science are concerned with the applicability of those theories to practical life, through the analysis of experimental results (e.g. conferences such as WADS, ALENEX, etc...). </p>

<p>It is often suggested that the ideal is a good balance between theory and practice, as in "Natural Science", where the observation of experiments prompts the generation of new theories, which in turn suggest new experiments to confirm or infirm those: as such many conferences attempts to accept both experimental and theoretic results (e.g. ESA,  ICALP, LATIN, CPM, ISAAC, etc...). The subfield of "Algorithms and Data Structures" in computer science might suffer of an imbalance in the sense that "Theoretical" conferences are generally more highly ranked than experimental ones. I believe that this is not true in other subfields of computer science, such as HCI or AI.</p>

<p>Hope it helps?</p>

CC BY-SA 2.5
2011-02-22T21:37:43.043Z
Thanks, it helps a lot indeed. I have been interested in graph theory lately and in the papers I was reading, almost none of them had code or experimental results. This is why I asked. When you do pure maths, you cannot produce experimental results hence proofs are everything. But in Graph Theory it's not THAT hard to code your algorithm and produce useful experimental results! Let's take the MST problem. Current industry implementations are Prim/Kruskal and Boruvska and yet, more powerful algorithms are described in papers but they are not used since no one has ever coded them.
toto
CC BY-SA 2.5
2011-02-22T22:19:10.127Z
Yes, you could implement algorithms from graph theory. But for many of the _interesting problems_ in graph theory, that is at least $NP$-hard, that would be useless as only very small inputs would be (acceptably) computable due to the exponential-time complexity of the algorithms.
Mathieu Chapelle
CC BY-SA 2.5
2011-02-22T23:01:29.530Z
@ toto Certainly what you are saying applies to some problems, but for the MST problem, you can see the results (maybe somewhat outdated) of implementing some of the powerful algorithms in http://books.google.com/books?id=NRrcsIJZAYMC&pg=PA400&lpg=PA400&dq=cheriton+spanning+tree+implementation&source=bl&ots=ynei7PH4fs&sig=J2wWcZ7HSJhIGfAjNPtSpqO47nM&hl=en&ei=mj5kTd6gEdPPgAfh8Z2IAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CB0Q6AEwAQ#v=onepage&q=cheriton%20spanning%20tree%20implementation&f=false
Abel Molina
CC BY-SA 2.5
2011-02-23T02:05:07.267Z
@toto. This is not the only reason older algorithms are used. For the TCS perspective $O ( n )$ is always better than $O( n \log n)$. But big-oh can hide a  large constant that makes the algorithm impractical in practice. Such a work aims at TCS people and coding the algorithm would provide no gain or even confuse the reader.
chazisop
CC BY-SA 2.5
2011-02-22T19:41:30.993Z
2011-02-22T19:41:30.993Z
J.y B.y
<p>I'm new to the CS field and I have noticed that in many of the papers that I read, there are no empirical results (no code, just lemmas and proofs). Why is that? Considering that Computer Science is a science, shouldn't it follow the scientific method?</p>

CC BY-SA 2.5
2011-02-22T18:49:37.163Z
The short answer is that "computer science" is many things. Some parts like (some) AI actually are science. Other parts are engineering, and the theoretical side is (applied) math. Parts of HCI are more like art. Computer science is a broad tent.
Aaron Roth
CC BY-SA 2.5
2011-02-22T19:07:34.230Z
If you have proofs, why do you even need empirical results?
Aryabhata
CC BY-SA 2.5
2011-02-22T19:34:34.403Z
@Moron: How do you prove that an algorithm is implementable without implementing it?
Jukka Suomela
CC BY-SA 2.5
2011-02-22T19:50:38.013Z
@Jukka: That is a good research question :-) Really though, for a lot of papers (say written in 1960s/1970s), the implementation + performance results are quite meaningless when viewed today. If you have a proof, I really don't see a point of a "proof" of concept implementation, but perhaps that is because I am lazy :-)
Aryabhata
CC BY-SA 2.5
2011-02-22T19:56:40.110Z
Nitpicking: I hope that the papers which you read also prove some _theorems_ instead of just lemmas.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-22T21:12:21.717Z
I have seen many papers in which the authors show only empirically what should have been proven. @Jukka: If it's computable, it's implementable. Or are you referring to niceness?
Raphael
CC BY-SA 2.5
2011-02-22T23:15:19.360Z
Theoretical CS seems to be akin to Mathematical Physics which also avoids empirical results. If you want something like Experimental Physics, you could look at research in Software Engineering, Program Verification, Database Systems etc
Yaroslav Bulatov
CC BY-SA 2.5
2011-02-23T01:21:09.193Z
@Tsuyoshi, nitpicking on the nitpicking: Papers who only prove "lemmas" are strong papers ;) (See the [quote from "Proofs from the Book"](http://books.google.com.tw/books?id=CuTpgZaLahkC&pg=PA195&hl=zh-TW&ei=t2BkTZz1I4PCccaRtI8F&sa=X&oi=book_result&ct=result&resnum=2&ved=0CC8Q6AEwAQ#v=onepage&q&f=false).)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-23T02:56:13.080Z
@Hsien-Chih: You won the battle of nitpicking.  I will try to do better next time.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-23T07:07:11.070Z
nitpicking: "*the* scientific method"?
Kaveh
CC BY-SA 3.0
2012-09-20T05:35:06.907Z
a big problem is that many or most meaningful CS thms & ideas seem to refer to very large objects that are too big to manipulate by machines even taking phenomenal technological advances like moores law and "the cloud" into account. see eg [is experimental complexity theory being used to solve open problems](http://cstheory.stackexchange.com/questions/524/isexperimental-complexity-theory-being-used-to-solve-open-problems). but however contrast this with a fervent _enthusiasm_ by mathematicians for [experimental mathematics](http://mathoverflow.net/questions/12085/experimental-mathematics)
vzn
CC BY-SA 3.0
2012-09-20T05:38:34.780Z
see also [a reading list on experimental algorithmics](http://cstheory.stackexchange.com/questions/822/a-reading-list-on-experimental-algorithmics)
vzn
CC BY-SA 3.0
2013-01-20T22:07:07.020Z
The saying goes that any subject with "science" in the name is not a science :p
Max
<soft-question><research-practice><writing>
Empirical results in CS papers
toto
# Empirical results in CS papers

(Asked by: username_0 on 2011-02-22)

I'm new to the CS field and I have noticed that in many of the papers that I read, there are no empirical results (no code, just lemmas and proofs). Why is that? Considering that Computer Science is a science, shouldn't it follow the scientific method?

**Tags:** soft-question, research-practice, writing

> **Comments:**
> **username_1**: The short answer is that "computer science" is many things. Some parts like (some) AI actually are science. Other parts are engineering, and the theoretical side is (applied) math. Parts of HCI are more like art. Computer science is a broad tent.  
> **username_2**: If you have proofs, why do you even need empirical results?  
> **username_3**: @Moron: How do you prove that an algorithm is implementable without implementing it?  
> **username_2**: @Jukka: That is a good research question :-) Really though, for a lot of papers (say written in 1960s/1970s), the implementation + performance results are quite meaningless when viewed today. If you have a proof, I really don't see a point of a "proof" of concept implementation, but perhaps that is because I am lazy :-)  
> **username_4**: Nitpicking: I hope that the papers which you read also prove some _theorems_ instead of just lemmas.  
> **username_5**: I have seen many papers in which the authors show only empirically what should have been proven. @Jukka: If it's computable, it's implementable. Or are you referring to niceness?  
> **username_6**: Theoretical CS seems to be akin to Mathematical Physics which also avoids empirical results. If you want something like Experimental Physics, you could look at research in Software Engineering, Program Verification, Database Systems etc  
> **username_7**: @Tsuyoshi, nitpicking on the nitpicking: Papers who only prove "lemmas" are strong papers ;) (See the [quote from "Proofs from the Book"](http://books.google.com.tw/books?id=CuTpgZaLahkC&pg=PA195&hl=zh-TW&ei=t2BkTZz1I4PCccaRtI8F&sa=X&oi=book_result&ct=result&resnum=2&ved=0CC8Q6AEwAQ#v=onepage&q&f=false).)  
> **username_4**: @Hsien-Chih: You won the battle of nitpicking.  I will try to do better next time.  
> **username_8**: nitpicking: "*the* scientific method"?  
> **username_9**: a big problem is that many or most meaningful CS thms & ideas seem to refer to very large objects that are too big to manipulate by machines even taking phenomenal technological advances like moores law and "the cloud" into account. see eg [is experimental complexity theory being used to solve open problems](http://cstheory.stackexchange.com/questions/524/isexperimental-complexity-theory-being-used-to-solve-open-problems). but however contrast this with a fervent _enthusiasm_ by mathematicians for [experimental mathematics](http://mathoverflow.net/questions/12085/experimental-mathematics)  
> **username_9**: see also [a reading list on experimental algorithmics](http://cstheory.stackexchange.com/questions/822/a-reading-list-on-experimental-algorithmics)  
> **username_10**: The saying goes that any subject with "science" in the name is not a science :p  

---

## 6 answers

### Answer by username_20 on 2011-02-22. Score: 22 | Accepted answer

Mathematics is a science also, and you would have to search for a long time to find published empirical results in this field (although I guess there must be some). There are other scientific domains where "lemmas and proofs" are valued over experience, such as quantum physics. That said, most sciences mix theory and practice (with various ratios), and Computer Science is no exception.

Computer Science has its roots in Mathematics (see Turing's biography for instance <http://en.wikipedia.org/wiki/Alan_Turing>), and as such many results (generally dubbed as in the field of "theoretical computer science") consist in proofs that computers in some computational model can solve some problem in a given amount of operations (e.g. conferences such as FOCS, STOC, SODA, SoCG, etc..). Nevertheless, many other results of computer science are concerned with the applicability of those theories to practical life, through the analysis of experimental results (e.g. conferences such as WADS, ALENEX, etc...).

It is often suggested that the ideal is a good balance between theory and practice, as in "Natural Science", where the observation of experiments prompts the generation of new theories, which in turn suggest new experiments to confirm or infirm those: as such many conferences attempts to accept both experimental and theoretic results (e.g. ESA, ICALP, LATIN, CPM, ISAAC, etc...). The subfield of "Algorithms and Data Structures" in computer science might suffer of an imbalance in the sense that "Theoretical" conferences are generally more highly ranked than experimental ones. I believe that this is not true in other subfields of computer science, such as HCI or AI.

Hope it helps?

> **Comments:**
> **username_0**: Thanks, it helps a lot indeed. I have been interested in graph theory lately and in the papers I was reading, almost none of them had code or experimental results. This is why I asked. When you do pure maths, you cannot produce experimental results hence proofs are everything. But in Graph Theory it's not THAT hard to code your algorithm and produce useful experimental results! Let's take the MST problem. Current industry implementations are Prim/Kruskal and Boruvska and yet, more powerful algorithms are described in papers but they are not used since no one has ever coded them.  
> **username_21**: Yes, you could implement algorithms from graph theory. But for many of the _interesting problems_ in graph theory, that is at least $NP$-hard, that would be useless as only very small inputs would be (acceptably) computable due to the exponential-time complexity of the algorithms.  
> **username_22**: @ username_0 Certainly what you are saying applies to some problems, but for the MST problem, you can see the results (maybe somewhat outdated) of implementing some of the powerful algorithms in http://books.google.com/books?id=NRrcsIJZAYMC&pg=PA400&lpg=PA400&dq=cheriton+spanning+tree+implementation&source=bl&ots=ynei7PH4fs&sig=J2wWcZ7HSJhIGfAjNPtSpqO47nM&hl=en&ei=mj5kTd6gEdPPgAfh8Z2IAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CB0Q6AEwAQ#v=onepage&q=cheriton%20spanning%20tree%20implementation&f=false  
> **username_23**: @username_0. This is not the only reason older algorithms are used. For the TCS perspective $O ( n )$ is always better than $O( n \log n)$. But big-oh can hide a  large constant that makes the algorithm impractical in practice. Such a work aims at TCS people and coding the algorithm would provide no gain or even confuse the reader.  

---

### Answer by username_15 on 2011-02-23. Score: 25

Implementing algorithms well is a skill which takes a different set of tools than just proving theorems. Many algorithms which were discovered by the theory community have indeed been implemented in practice (although I would like to see the theory community take a bigger role in this process). Physics doesn't ask the same researchers to do theory and experiment, although it is expected that the two groups communicate. Why shouldn't you expect to see the same divide in computer science?

ADDED IN EDIT:

Expanding on my comment in answer to Suresh's about what I meant by "role" above, at Bell Labs and AT&T Labs, researchers in algorithms were encouraged to talk to people in development. I didn't do as much of this as I probably should have, but I did get [at least one paper](http://www.springerlink.com/content/v7227874015t1l6m/) out of it, and I think it would be good for the field if there were more communication between people in theory at universities and practitioners. This doesn't mean that I think everybody who comes up with an algorithm should code it (even if it's practical).

On the other hand, coding algorithms (or having a student code them) that you think might be practical can be useful in getting them adapted by practitioners. Consider one example. Lempel and Ziv wrote two technical papers in 1977 and 1978 on new data compression algorithms. Everybody ignored them. In 1984, Welch wrote [a much less technical paper](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1659158&isnumber=34743) giving a slight twist on LZ78 that improved its performance somewhat, and gave the results of a small study comparing its performance with other data compression methods. It was published in a journal read by a number of programmers, and the algorithm was given by a few lines of pseudocode. The method was quickly adapted in a number of places, eventually resulting in an infamous intellectual property dispute.

Of course, one of the best ways for algorithms researchers to communicate with practice is to produce grad students who go off and work at Google, IBM, or other companies, and we're already doing that. Another way might be to answer practitioner's questions in this forum. Hopefully, we're doing a reasonable job of that as well.

> **Comments:**
> **username_12**: So you're saying that even though in physics there's no expectation of the same person doing both, in theoryCS we should do both ? is it because models of computation are much more of an approximation to reality than physics models ?  
> **username_15**: I'm saying that the theorists should talk more to the practitioners. If you look at the history of physics, bad things start happening when theorists stop talking to experimentalists. I actually think we have a reasonable amount of communication between the two groups right now, but that it wouldn't hurt to have some more.  
> **username_0**: I won't generalize but I think that many researchers simply cannot code/don't like to and they would rather let the practical work be done by one of their students. That's the case with me and my mentor.  
> **username_16**: The tension associated to formal specification versus practical computation goes far back in STEM history.   Sometimes formal specification leads (von Neumann's "On the theory of stationary detonation waves" [1948] versus subsequent computational simulations) and sometimes practical computation leads (Bowditch's "New American Practical Navigator" [1807] versus Gauss' "Disquisitiones generales circa superficies curvas" [1827]).  The greatest mathematicians (Gauss and von Neumann in the examples cited above) have often combined formal specifications with practical computations.  
> **username_12**: Nice. btw in retrospect my comment made it sound like I was arguing with you, whereas my intent was only clarification. I also know well the beneficial aspects at AT&T of talking to researchers outside algorithms :)  
> **username_15**: The history of Lempel-Ziv, and looking at posts on StackOverflow, have just led me to formulate a very simple precept which might help get algorithms theorists come up with implemented vy practitioners: *If you think your algorithm might be practical, put pseudocode in your paper.*  

---

### Answer by username_11 on 2011-02-22. Score: 17

One research area that uses empirical methods and methods of Theoretical Computer Science is the field called "Experimental Algorithmics" or "Algorithm Engineering". Like Chris mentioned, high performance computing relies heavily on this as modern systems have complex cache and latency issues that we have a hard time modeling.

[Gerth Brodal](http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/b/Brodal:Gerth_St=oslash=lting.html) and [Peter Sanders](http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Sanders:Peter.html) are good examples of researchers who maintain a foot in both the "proof" and "empirical" realms.

--Update 1/20/2013--
I would also mention a great presentation by [Robert Sedgewick](http://www.cs.princeton.edu/~rs/talks/ScienceCS.pdf).

> **Comments:**
> **username_12**: Both ALENEX and ESA encourage applied algorithms work, and there's also a conference (SAE) on this topic.  
> **username_13**: What is SAE? That TLA is ungoogleable.  Do you have a URL for it?  
> **username_14**: SAE is a typo for SEA, the Symposium on Experimental Algorithms.  
> **username_5**: You can also do Algorithm Engineering in a more rigorous way, i.e. refine theoritcal models so they fit reality but stil do precise analyses. It's hard, though.  
> **username_11**: @username_5 You would have to model a sphere around each VonNeuman compute node and explicitly put and get memory objects with a latency cost proportional to the distance; random access is $O(CubeRoot(n))$, the diameter of the memory sphere, speed of light is your best case latency.  

---

### Answer by username_17 on 2011-02-22. Score: 13

This depends on the discipline you are in; as Jeremy states, there is a spectrum of theory vs. practice.

Topics like *complexity* tend to be weighted towards the theory side, as often the goal is to find a boundary for the space or runtime. Implementing an algorithm in C++ and then running it a bunch of times isn't going to prove that a problem is NP-complete.

As a polar opposite, *high-performance computing* (with conferences like [Supercomputing](http://supercomputing.org/)) are all empirical; no one would ever submit a proof to an HPC publication as there is too much variability with regard to memory hierarchy and kernel overhead.

So what seems like the same question (How long does something take to run?) will be approached two completely different ways depending on the goals, techniques, community, etc. See Poul-Henning Kamp's [You're Doing It Wrong](http://queue.acm.org/detail.cfm?id=1814327) for an example of the dissonance.


---

### Answer by username_18 on 2011-02-23. Score: 11

In programming languages research many ideas for new programming language constructs or new type checking mechanisms stem from theory (perhaps informed by experience in practice, perhaps not). Often a paper is written about such mechanisms from a formal/theoretical/conceptual perspective. That's relatively easy to do. Next comes the first hurdle: implementing the new constructs in the context of an existing compiler and experimenting with it, in terms of efficiency or flexibility. This too is relatively easy.

But can we then say that the programming construct constitutes an advance to the science of programming? Can we say that it makes writing programs easier? Can we say that it makes the programming language better?

The answer is no. A proper empirical evaluation involving scores of experienced programmers over large periods of time would be needed to answer those kinds of questions. This research is hardly ever done. The only judge of the value of a programming language (and its constructs) is the popularity of the language. And for programming language purists, this goes against what our hypotheses tell us.


---

### Answer by username_19 on 2011-02-24. Score: 8

Perhaps I'm missing the motivation for your question but there are many examples of empirical results motivating research, algorithms and other results.

[MP3](http://en.wikipedia.org/wiki/MP3) use [psychoacoustic](http://en.wikipedia.org/wiki/Psychoacoustics) to optimize the algorithm for human encoding.

[Plouffe](http://groups.google.com/group/sci.math.symbolic/browse_thread/thread/6b79152956098607/28159974a1fe298e?pli=1) gives an account of discovering the [BBP spigot algorithm for the digits of $\pi$](http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula) where he recounts the use of whatever [Integer Relation Algorithm](http://en.wikipedia.org/wiki/Integer_relation_algorithm) Mathematica was using to discover the formula.

Along the same line, Bailey and Borwein are big proponents of experimental mathematics. See ["The Computer as Crucible: An Introduction to Experimental Mathematics"](http://rads.stackoverflow.com/amzn/click/1568813430), ["Computational Excursions in Number Theory"](http://rads.stackoverflow.com/amzn/click/1441930000) amongst [others](http://www.amazon.com/s/ref=ntt_athr_dp_sr_1?_encoding=UTF8&sort=relevancerank&search-alias=books&field-author=Jonathan%20Borwein#/ref=sr_pg_1?rh=n%3A283155%2Cp_27%3AJonathan+Borwein&sort=relevancerank&ie=UTF8&qid=1298576327). One might argue that this is more experimental *Mathematics* but I would argue that at this level the discussion the distinction is semantic.

Phase transitions of NP-Complete problems are another area where empirical results are heavily used. See [Monasson, Zecchina, Kirkpatrick, Selman and Troyansky](http://www.math.ucla.edu/~percus/Teaching/RIPS/nature.pdf) and [Gent and Walsh](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.2866&rep=rep1&type=pdf) for starters, though there are many, many more (see [here](http://www.tud.ttu.ee/material/enn/GraphTheory/0602129v1.pdf) for a brief survey).

Though not quite on the level of Theoretical Computer Science or Mathematics, there is a discussion [here](http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/#fish_made_a_mess) about how the unix utility grep's average case runtime beats optimized worst case algorithms because it relies on the fact that it's searching human readable text (grep does as bad or worst on files with random characters in them).

Even Gauss used [experimental evidence](http://en.wikipedia.org/wiki/Prime_number_theorem#History_of_the_asymptotic_law_of_distribution_of_prime_numbers_and_its_proof) to give his hypothesis of the Prime Number Theorem.

Data mining ([Bellkor's solution](http://www.netflixprize.com/assets/ProgressPrize2008_BellKor.pdf) to the [Netflix Prize](http://en.wikipedia.org/wiki/Netflix_Prize) to make a better recommendation system) might be argued to be a theory completely based on empirical evidence. Artificial Intelligence (genetic algorithms, neural networks, etc.) relies heavily on experimentation. Cryptography is in a constant push and pull between code makers and code breakers. I've really only named a few and if you relax your definition of empirical, then you could cast an even wider net.

My apologies for being so scattered in answering your question but I hope I've given at least a few examples that are helpful.


---

