Teaching etc.

The most basic thing that has to be understood about our PhD program is that at UofC we do not own students (and we take pride in this fact). Indeed, many of our students change their advisors as their research interests develop naturally. Some of our current students have done this more than once, and some of them have a "nominal" advisor and actually work with other faculty (including TTIC and the math department). All these forms of behavior are considered absolutely normal here.

For the purpose of this section, this means that I strongly encourage all prospective students that read this essay to check out the Web pages of my colleagues as well, and consider this as a combined resource our students are having access to.

That said, here are a few research projects (in no particular order) that, for one or another reason, are close to my heart. Some of them are being pursued by our current and former students, and some of them have even been worked out in communication with them. Many of these projects are concentrated around a ``big'' problem, although in almost all cases I see how to identify some accessible subgoals. Also, this is not meant as a comprehensive description (and definitely not a survey); I prefer to give references to a few good sources from which you can explore literature on your own (or write to me for details). In line with what was written above (yes, faculty also have the right of flexibility!), the list should be expected to change as needed and without any notices. On the other hand, I am not planning to do anything like regular maintenance of this section, so if you notice anything incorrect, outdated, broken links etc. please drop me a word.

Flag Algebras and (Hyper)Graph Limits. As of now, this is my central project, and the underlying idea is very simple. Assume that you are interested in the behavior of a very large graph or other combinatorial structure with respect to a few fixed ``templates''. Then it is natural (for a mathematician) to wonder what will happen, and what does it mean in the first place, if our graph is not just ``quite large'', but actually infinite. It turns out that we get a cute and rich mathematical theory of analytical and algebraic nature that at the same time is interesting in its own right and gives remarkably concrete applications in the field of Extremal Combinatorics.
This is the master paper on flag algebras, and my list of publications contains several other papers, easily identifiable by titles, with concrete applications of the method (more are expected soon). The best starting point to explore the general theory of graph limits is Laszlo Lovasz's page.
Proof Complexity. This is a great area dealing with problems of extremely significance that, unfortunately, suffers from the same drawback as Circuit Complexity: really interesting problems there are really (to put it very softly) hard, and we have very little clue as to how to approach them. You can check out my graduate course in proof complexity, and in particular the literature cited therein, as well as Lecture Notes for that course. My main interest in the area stems from the fact that efficient provability in weak proof systems of central open questions like P vs. NP is at least as amusing as the concept of a Natural Proof (the two were in fact conceived simultaneously). In any case, I have put practically anything I can say on the subject (albeit in a slightly condensed form) into Introduction to this paper, and if you have any ideas where to take it from there, please feel free to write to me.

Banff workshop (new!)

I recently returned from a BIRS workshop in Proof Complexity, and I have composed a small list of problems that people find exciting, and so do I.

Jakob Nordstrom points out that no progress has been done yet on problem 2 from our old space paper (superlinear lower bounds for resolution variable space) and he finds it shocking. I concur. Incidentally, Jakob is also proposing to rename ``variable space'' to "total space" while reserving the former term for counting the number of distinct variables in memory (as far as I remember, we never thought of this new measure while writing the above-mentioned 2002 paper).

(Solved! -- see ECCC paper. But their bound is barely super-polynomial, that would still be very nice to improve on it.) The only known way to come up with a linear space resolution refutation of an arbitrary contradiction blows up the refutation size -- it becomes (provably) exponential. Eli Ben-Sasson asked whether this is always necessary. i.e. if we have a sort of tradeoff between these measures. More specifically, is it true that every resolution refutation can be converted into a linear space resolution refutation with only polynomial overhead in terms of size? A negative answer for regular resolution, as well as some partial results toward the general case has been recently given by Paul Beame, Christopher Beck and Russell Impagliazzo, and Chris is coming to give a talk at our seminar on November 29.

While non-trivial space lower bounds for the system PCR were proved in the above-mentioned paper, they essentially used the fact that the original contradiction had unbounded fan-in. Jakob Nordstrom points out that problem 5 from our space paper (proving similar bounds for bounded fan-in refutations) is still open, and for the system of Cutting Planes we do not seem to have any space lower bounds at all. Some partial results in that direction (trade-off between space and size) will appear soon in a paper by Ben-Sasson, Huynh, Nordstrom and Zewi.

Albert Atserias gave a fantastic and thought-provoking talk on this paper that neatly combines logic, combinatorics, proof complexity and LP relaxations. The paper is so rich with ideas that I would simply advise to read it and see where it can be taken further... but if you want a concrete problem, here we go: prove that the integrality gap of 2 for VERTEX COVER survives $\Omega(n)$ rounds of Sherali-Adamas without UG-conjecture.

Toni Pitassi talked about their paper on Patrascu's conjecture relating certain three-party communication complexity models to difficult open problems in dynamic data structures. They prove (roughly) $\sqrt n$ upper bound (Theorem 3) and prove that under certain restrictions it is close to optimal (Section 5). Removing those restrictions would result in fantastic consequences for dynamic data structures problems (Section 6, second paragraph).

Communication Complexity. This is a very important subject that, in one or another way, is related to almost everything we are doing in Theoretical Computer Science. The standard textbook (that is a little bit outdated but still contains all classical stuff) is this. Let me try to identify a few important concrete problems and directions within this subject.
- Quantum vs. Randomized. One of the most mysterious open problems in the field is whether quantum and randomized communication complexities of total problems coincide up to a polynomial. For so-called symmetric predicates it was solved in my paper, and the next challenge is to extend this to so-called block-composed functions; this paper by A. Sherstov seems to be one of the latest writings on the subject.
- Log-Rank Conjecture. It is a shame we have not been able to solve it in 30 (or so) years. See Problem 2.20 in Kushilevitz and Nisan's book, I really do not have that much to add here.
- Information Complexity. That is a very interesting subject that has recently seen a rapid development. The traditional way to measure the complexity of a communication protocol is by the number of bits exchanged. Information complexity views it a little bit differently and proposes to count the number of information leaked during the execution of the protocol (to an external observer or to the parties involved). It turns out that with this notion, you can do a lot of great things, like prove Direct Sum/Product theorems.
  The central (at the moment) paper here seems to be this one, and the materials of the last Barbados conference (Lecture Notes are promised soon) will be another invaluable resource, more than 50% of the workshop was devoted to the subject!
Hirsch Conjecture. Like many problems in this document, it is shockingly simple to state, and has a long history (50 years or so). Given a polytope or polyhedra with $n$ facets, is the diameter of its edge graph polynomial in $n$? A combinatorial approach to this problem was developed by Gil Kalai (Discrete & Computational Geometry, 8:363_372, 1992) and by us, and has recently become the subject of the Polymath 3 project.

Geometric Proof Systems and LP/SDP Relaxations. Technically speaking, this subject is often viewed as a part of Proof Complexity, but it is so tightly related to combinatorial optimization that I have decided to single it out. If you want to compute (or approximate) some objective function using systematic relaxation procedures (like Lovasz-Schrijver or Lassiere), then it can be equivalently represented as proving that this objective function does not exceed (or not smaller than) a certain fixed value. This simple observation has led to a deep cooperation of two quite different communities that has resulted in many great findings. But the most major open problem (size lower bounds for geometric proof systems) is still widely open.
In this direction, there do exist several good surveys, for example this one (written from proof complexity perspective), or that one (more on the optimization side).

Sensitivity vs. Block-Sensitivity Conjecture. Yet another simple and important problem (this time about combinatorics of Boolean functions) with a history of unsuccessful attempts, and Scott Aaronson's philomath project (do not ask me what is the difference between Polymath and Philomath) devoted to it. This problem has a special Chicago connection as it has been tried by generations of our students. Last year three of them took the initiative to write a comprehensive survey on the subject; use it as a natural starting point.

Arithmetic Combinatorics. This is a loosely defined field roughly covering the content of Tao and Vu's book, as well as things like polynomial correlations with very immediate motivations and applications in TCS. One small problem here is that I am not very sure about deep but reasonably accessible problems, but perhaps it will change after I teach this subject as an advanced graduate course this coming autumn.