Teaching etc.

The most basic thing that has to be understood about our PhD program is that at UofC we do not own people (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 at CS, Math and TTIC. 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.

Coming now to the point, here are a few research projects that, for one or another reason, are close to my heart; some of them are being pursued by our current and former students. 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). The list should be expected to change as needed and without any notices but, 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.

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. On the contrary, there's been a steady progress on the so-called weak proof systems like Resolution, Polynomial Calculus and Semi-Algebraic Proof Systems (Cutting Planes, Sum-Of-Squares, Lovasz-Schrijver). Luckily, these are precisely 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 the latter in Moshe Vardi`s article).
The list of open problems below stemmed from a variety of sources including:
- My topic course in proof complexity.
- Research work in and contemplations about the area, see my SIGACT essay or ECM article for an outcome.
- Papers, personal communications and conferences we run regularly, see e.g. the one in Oberwolfach and the one in Banff.
Soon after I started doing this, I was surprised and delighted to see that some authors formally refer to this secion in research papers. Well, with great power comes great responsibility. I may occasionally re-shuffle the content, clarify the statements or add comments; in particular, I am making now a special sub-section "Solved" (which in one case means "morally disproved"). But whatever is asked here once, will stay here "forever".
Open problems
1. Super-polynomial lower bounds for Frege or Extended Frege modulo any reasonable (that is, not attempting to state $NP\neq co-NP$ in disguise) complexity or cryptographic assumption. For extended context on this and the closely related next question see the introductory section in Pseudorandom generators hard for....
2. Consider propositional tautologies encoding that $f_n$ does not possess a circuit of size $t(n)$. Here $f_n$ are absolutely arbitrary Boolean functions in $n$ variables, $t(n)\geq n^{\omega(1)}$ and the statement is encoded by a sequence of truth tables so that in particular the number of propositional variables is roughly $N=2^n$. The strongest proof systems for which the hardness of this principle is known unconditionally are $Res(\epsilon\log n)$ (Pseudorandom generators hard for...) and the polynomial calculus (Lower bounds for the polynomial calculus).
  Prove unconditional hardness of these tautologies for more proof systems that can be handled with current techniques. Specifically, prove super-polynomial (in $N$!) size lower bounds for bounded-depth Frege or at least depth-2 Frege, aka DNF resolution. Prove super-polynomial lower bounds on (DAG-like) size in Cutting Planes, or at least a $t(n)^{\Omega(1)}$ lower bound on depth. Prove the same $t(n)^{\Omega(1)}$ degree lower bound in Sum-of-Squares.
3. Super-polynomial lower bounds for bounded-depth Frege with logical connectives expressing counting modulo a given fixed prime $p$.
4. Super-polynomial lower bounds on the refutation size in the Lovasz-Schrijver system $LS$. One promising approach might be to prove the monotone feasible interpolation property (for the non-monotone version see Lower bounds for resolution and cutting planes proofs and monotone computations.); a negative answer to the latter question would also be very interesting.
5. The system $LS^*$ is obtained from $LS$ by adding one more inference rule: $f\geq 0, g\geq 0 \to fg\geq 0$, where $f,g$ are arbitrary affine forms. Prove super-logarithmic rank lower bounds for this system (see Complexity of Semi-algebraic Proofs for the context and an $\Omega(\log n)$ bound).
6. For a space complexity measure $\mu$, define its regularized version $\mu^\ast$ by letting $ mu^\ast(\pi) = \mu(\pi)\cdot \log |\pi|$, where $\pi$ is a proof in the configurational form. Are $\mu$ and $\mu^\ast$ equivalent up to a polynomial and $(\log n)^{O(1)}$ factors when $\mu$ is clause, variable or monomial space? This is true for total space, clause space in either tree-like or regular resolution and for $\Sigma_2$ space, and these questions are equivalent to several prominent open problems regarding relations between complexity of Hilbert-style and configurational proofs. For an extended context, see On Space and Depth in Resolution and Space characterizations of complexity measures....
7. Is Sum-of-Squares automatizable with respect to degree? Is it automatizable with respect to monomial size? Along with the previous item, these are arguably the most important questions left open by the breakthrough papers Automating Resolution is NP-Hard, Automating Algebraic Proof Systems is NP-Hard.
8. The polynomial version of super-critical trade-off between resolution size and clause space was proved in Time-Space Trade-offs... This result is a bit disappointing numerically, however: the trade-off effect vanishes at size $n^{\epsilon \log \log n/\log \log \log n }$ which is barely super-polynomial. Do there exist unsatisfiable CNFs that have quasi-polynomial size DAG-like resolution refutations with the property that every such refutation must have super-linear clause space?
9. The space complexity of cutting planes refutations proved that every unsatisfiable CNF has a constant space refutation in Cutting Planes. Prove lower bounds in the case of polynomially bounded coefficients.
10. On the Power and Limitations... has recently proved that the Stabbing Planes proof system with polynomially bounded coefficients can be quasi-polynomially simulated by Cutting Planes. Can the restriction on the coefficients be removed? Can the simulation be improved to polynomial?
11. Resolution with Counting... has proved super-polynomial lower bounds for the system Res(Lin). Can such bounds be established for systems of linear equations resulting from natural translations of CNF formulas?
12. Prove resolution lower bounds for the principle expressing that a random $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 we are looking for bounds of the form $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 (Clique Is Hard on Average for Regular Resolution, further details can be also found there).
13. Strong Exponential Time 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$. Strong ETH holds for regular resolution solved it for Regular Resolution and also reported some progress for the general case.
14. Let $PHP^\infty_n$ be the pigeon-hole-principle with infinitely (= arbitrarily many) pigeons. Does it have polynomial size proofs in bounded-depth Frege?
15. The answer to the previous question is affirmative if "polynomial" is replaced by "quasi-polynomial" (A New Proof of the Weak Pigeonhole Principle), and the upper bound coming from that paper is $Res((\log n)^{O(1)})$. Does $Res(k)$ have quasi-polynomial size proofs of $PHP^\infty_n$ for any fixed $k$?
16. As far as resolution proofs are concerned, the best known upper bound on the size complexity of $PHP^\infty_n$ is exponential in $n^{1/2}$ (Resolution and the weak pigeonhole principle), and the best known lower bound is $\exp(\Omega(n^{1/3}))$ (Improved Resolution Lower Bounds ...). Determine the right value of the exponent here.
17. The onto functional pigeon-hole-principle $onto-FPHP^m_n$ simply asserts that there is no bijection between $[m]$ and $[n]$. Prove polynomial calculus degree lower bounds for $onto-FPHP^{n+p}_n$ over fields of characteristic $p$. For the weaker Nullstellensatz proof system such bounds were proved in More on the relative strength of counting principles.
(Morally) Solved
1. (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, Alekhnovich-Razborov solved it modulo some twist in the way pigeon axioms are encoded.
  
  Solved in A generalized method...
2. 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.
  Random CNFs are hard... proved that $O(\log n)$-CNFs are hard by showing that they are amenable to the monotone feasible interpolation techniques. On the contrary, Tseitin tautologies have been shown to have quasi-polynomial size refutations in On the Complexity of Branching Proofs. Several problems still remain open, like what will happen to random 3-CNFs or whether the last result can be improved to polynomial. But all in all, the developments on this question have taken quite unexpected turn, somewhat defeating my original motivations to ask it.
3. 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, Ben-Sasson and Wigderson more than a decade ago... still wide open, not entirely clear why.
  Solved in Total Space in Resolution and Space proof complexity for random 3-CNFs.
4. 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?
  Solved in Polynomial Calculus Space and Resolution Width. Remarkably, their result is much stronger than what was asked above: any space $s$ refutation in the functional calculus (see Appendix in Space Complexity in Propositional Calculus), which includes PCR over an arbitrary field, gives rise to a width $O(s^2)$ refutation. Whether this quadratic increase in complexity is actually necessary remains an interesting open question.
5. Prove super-critical trade-offs (see A new kind of trade-offs... for a high-level explanation of the phenomenon) between size and depth in either Resolution or Cutting Planes. Say, construct unsatisfiable CNFs that have polynomial or quasi-polynomial size DAG-like refutations in one of these two systems but with the property that every such refutation must have super-linear depth.
  Solved in Extremely Deep Proofs. Their depth bound, however, is super-linear only in the number of variables. It is still open whether a similar trade-off is possible with depth super-linear in the size of the CNF.
6. Is bounded-depth Frege, or at least Res(log), automatizable?
  Solved in Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It and Depth d Frege systems are not automatable unless P=NP. There are caveats here: the result uses CNFs of depth d and, moreover, their size is not bounded by a polynomial not depending on n. Removing these drawbacks remains a challenging open problem.
7. For a field $k$ with $char(k)\neq 2$, let $PCR^k_{\{0,1\}}(\tau_n)$ and $PCR^k_{\{\pm 1\}}(\tau_n)$ be the monomial size in the polynomial calculus with resolution over $k$, where the subscript specifies the encoding used. Is it true that $PCR^k_{\{\pm 1\}}(\tau_n)\leq PCR^k_{\{0,1\}}(\tau_n)^{O(1)}$? A separation in the opposite direction is provided by Tseitin tautologies, and exponential lower bounds for $PCR^k_{\{\pm 1\}}$ were proven in (Semi)Algebraic Proofs over $\pm 1$ Variables
  
  Solved in Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable.
Continuous Combinatorics. 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 my master paper on Flag Algebras, a high-level 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 book Large Networks and Graph Limits. The paper Semantic Limits of Dense Combinatorial Objectsr attempts to extend the whole theory to arbitrary combinatorial objects, and Natural Quasirandom Properties gives applications to quasi-randomness.

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 Communication Complexity. The most important (and presumably very difficult) problems in the area include:
- Log-Rank Conjecture. It is a shame we have not been able to solve it in 4 0 (or so) years. See Problem 2.20 in Communication Complexity, I really do not have that much to add here.
- 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 Quantum communication complexity of symmetric predicates, and the next challenge is to extend this to so-called block-composed functions.

Teaching etc.

Former students

Current students

Courses

Possible research directions

Open problems

(Morally) Solved