Teaching etc.
Without education we are in a horrible and deadly danger of taking educated people seriously.

G. K. Chesterton (18741936)

Former students
Current students
Courses

Complexity Theory
 Topics in Combinatorics and Logic (Winter 19)
 Honors Discrete Mathematics (Autumn
19, Autumn 18, Autumn 17, Autumn 16)

Arithmetic Combinatorics (Spring 18, Spring 16, Autumn 11)
 Quantum Computing (Winter 20, Winter 18, Autumn 15, Spring 13, Winter 11, Spring 09) Lecture notes are
avilable.

Complexity Theory B (Spring 10)

Computability and Complexity Theory (Spring 14, Winter 12, Winter 10)

Discrete Mathematics (Autumn 13, Autumn 10, Autumn 09)

Graph Theory (Spring 12)

Propositional Proof Complexity (Winter 09) Lecture notes are avilable.
Possible research directions
This section is mostly designed for our prospective, admitted and
current students. But others are welcome to read it, too.
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, a highlevel
exposition and a survey
(almost) exclusively devoted to concrete applications. The best
starting point to explore the general theory of graph limits is Lovasz's
recent book Large Networks and Graph Limits, see also his Web 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
Winter 09 graduate course in proof complexity, and in particular the
literature cited therein, as well as Lecture
Notes for that course (see also an important addition below). My main
interest in the area stems from the fact that efficient provability in
limited 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.
New!
In my Topics
Class (Winter 2014) I revisited selected parts of the
old course on Proof Complexity, specifically focussing on socalled
weak proof systems like Resolution, Polynomial Calculus and
Geometric Proof Systems (Cutting Planes, LovaszSchrijver). These are the
systems that currently are in the focus of attention due to their tight
connections with neighboring communities like Combinatorial Optimization
and Practical SAT Solving (you can read more about this in Moshe Vardi`s article). Here are some concrete open problems that I
have recalled or identified for the course, of varying
(conjectured) difficulty.
 PHP (yes!) What is the minimal resolution refutation size of
the PigeonHolePrinciple $PHP^\infty_n$ with infinitely (=
arbitrarily many) pigeons? The best known upper bound is exponential
in $n^{1/2}$ (BussPitassi), and the best known lower bound is
$\exp(\Omega(n^{1/3}))$ (Raz, Razborov). Determine the right value of
the exponent here.
 Clique$k$ problem. Prove any nontrivial resolution
lower bounds for the principle expressing that a $k$partite
graph does not contain a (transversal) clique of size $k$. Here,
like in the parameterized complexity, we think of $k$ as a fixed
but arbitrarily large constant, and "nontrivial" means
$n^{f(k)}$, where $f$ is an unbounded function. This question was
asked by various authors (e.g. Beame, Impagliazzo, Sabharwal;
Beyesdorff, Galesi, Lauria, Razborov), but at the moment only the case of regular resolution is
known.
 Strong Exponential Time (well, Length) Hypothesis for
Resolution. Just what it says: construct contradictory
$k$CNFs that require Resolution refutation of size
$2^{(1\epsilon_k)n}$ for $\epsilon_k\to 0$. Beck and Impagliazzo
recently solved it for Regular Resolution and also reported some
progress for the general case.
 PHP again  should be doable. (Monomial) size lower
bounds on the refutations of $FPHP^{n+1}_n$ in
Polynomial Calculus with Resolution. The letter "F" stands for "functional" and in this context means that pigeon axioms are
encoded in the most straightforward way as linear equalities. This is a rather annoying
problem since there are good approaches to it that "almost"
work. For example, AlekhnovichRazborov solved it modulo some twist in the way pigeon axioms are
encoded Solved. See this paper by
Miksa and Nordstrom. .
 Combinatorial lower bounds (or, if you prefer more precise statements, lower bounds either for random $k$CNF or for Tseitin tautologies) for Cutting Planes proofs.
In view of many, this is *the* most important problem among those that are believed to be on an accessible side. New: this paper by Fleming, Pahkratov, Pitassi, Robere
proved that $O(\log n)$CNFs are hard by showing that they are amenable to the monotone feasible interpolation techniques. Proving a similar result fro constant $k$ remains a challenge. New: On the contrary, Tseitin tautologies have been proved to be easy.
 Does the *monotone* feasible interpolation hold for the
LovaszSchrijver system? An affirmative answer would imply
uncoditional size lower bounds for that system. But a
negative answer would also be quite interesting. One good
natural starting point toward the latter might be the
observation made by Eva Tardos long ago that Lovasz's theta
function separates clique and chromatic numbers. Can
perhaps its proof be formalized in the LS system thus
showing that the CLIQUECOLORING principle has polynomial
size refutations?

Just solved! See this paper by Bonacina, Galesi, Thapen and this one by Bonacina, Galesi, Huynh,
Wollan. Consider the total space model in Resolution, where you charge for every
clause in the memory by its width. Prove superlinear lower bounds for any tautology with polynomially
many axioms. Originally was asked in our paper with Alekhnovich, BenSasson and Wigderson more than
a decade ago... still wide open, not entirely
clear why.

Better tradeoffs between (resolution) proof size and space
(BenSasson). Assume that we have a contradiction that has a
refutation of size $S$. Can we construct another refutation
of linear space and of size comparable with $S$? The best
known lower bound has the form $S^{\Omega(\log\log S/\log\log\log S)}$. Improve this.

The result by Atserias and Dalmau we did in class bounds
the minimal width of a refutation of a given contradiction
in terms of the minimal space. Any relations (or perhaps
separations) between the
minimal degree and (monomial) space in PCR refutations?

Any nontrivial lower bounds for space in the Cutting Planes
proof system. At the moment only tradeoffs between size
and space are known, but I can not see any inherent reasons
why this problem should necessarily be as hard as
combinatorial size lower bounds mentioned above. Galesi,
Pudlak and Thapen have proved that every contradiction has a constant
space refutation in Cutting Planes with unbounded
coefficients, but the bounded coefficient case (often denoted CP*) remains open.

Finally, even if our minicourse was primarily about weak
proof systems, I feel bound to mention the following longstanding open problem. Size lower bounds for boundeddepth Frege with
logical connectives expressing counting modulo a given fixed prime $p$.

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 socalled symmetric predicates it was solved in my paper, and the next challenge is to extend this to socalled blockcomposed functions.

LogRank 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 LovaszSchrijver 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).

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.