Theory of Computation Laboratory (ToCL)


Lab members:
Shimon Even, in memoriam

Information for prospective graduate students: We recommend the following courses given at the Technion’s Computer Science Department as a good graduate-level introduction to ToC:
  • 236313 (Complexity Theory),
  • 236359 (Algorithms 2),
  • 236374 (Probabilistic Methods and Algorithms).
Department and Technion links: Full view
Our (exciting/stimulating/pivotal/eminent/remunerative) research discipline (ToC) deals with some of the foundations of computer science. Its goals include:
  • Formulating mathematical models that define rigorously the notion of computation, and allow us to reason about computational tasks and about the computational resources required to execute them. What’s a “computational task”? – Optimizing a function, learning a concept, communicating securely, and many other things we’d be happy to list had we entertained the slightest hope that you wouldn’t get bored. What are “computational resources”? – Processing time, memory space, randomness, information, power consumption, jelly beans, … (Don’t believe everything we say.)
  • Identifying fundamental computational problems whose solution may expand our understanding of computation, and is likely to influence to a wide range of applications. This is the first lesson in the ToC business: Use the magic word (“fundamental”) wherever it fits, and also in some places where it doesn’t fit.
  • Providing a quantitative technology-independent analysis of the computational resources required to solve fundamental computational problems. “Quantitative” means that we deal with numbers. “Technology-independent” means that we don’t get sufficient funding from Microsoft. Otherwise, we’d be happy to prove theorems that are true only under the latest version of Windows.
In particular, ToC deals with the growth rate of resource requirements as a function of problem size (“asymptotic analysis” is the technical term). Think of the growing number of web pages floating around in cyberspace, or the growing number of secure credit card transactions that all this web content lures people into initiating – asymptotic analysis is all about scalability!

Not confusing enough? Try Bernard Chazelle’s treatise on the quintessential computing device of our time – the iPod: paper, AAAS ’06 slides. (It appears that Bernard managed to connect a printer to his iPod, but then the printer got infected with a virus. Is that really an achievement worth bragging about?)

Now that you are convinced that ToC is the best thing that happened to humanity since the invention of peanut butter, let us reveal the harsh and bitter truth: ToC is useless! It’s a government sponsored welfare program to keep theoreticians off the street. (Hey, we’re cheaper than astrophysicists, and our constants are bigger, too!)


Our research efforts span many of the core areas of ToC: computational complexity, theory of algorithms, combinatorial optimization, learning theory, foundations of cryptography

Lab resources: We have state-of-the-art Turing machines, voluminous handbooks (wonderful as door stoppers), designer pens, sharp pencils, writing pads, glittery whiteboards.

ToC resources: