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 (Spring 19)
 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
First, a few words to our prospective graduate students.
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 socalled
weak proof systems like Resolution, Polynomial Calculus and
SemiAlgebraic Proof Systems (Cutting Planes, SumOfSquares,
LovaszSchrijver). 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:
Soon after I started doing this, I was surprised and delighted to see that some authors formally refer to this
site in research papers. Well, with great power comes great responsibility. I may occasionally reshuffle the
content, clarify the statements or add comments; in particular, I am making now a special subsection
"Solved" (which in one case means "morally disproved"). But whatever is asked here once, will stay here
"forever".
Open problems
 Superpolynomial lower bounds for Frege or Extended Frege modulo any reasonable (that is, not
attempting to state $NP\neq coNP$ 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....

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 superpolynomial (in $N$!) size lower bounds for boundeddepth Frege
or at least depth2 Frege, aka DNF resolution. Prove superpolynomial lower bounds on (DAGlike) 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 SumofSquares.

Superpolynomial lower bounds for boundeddepth Frege with
logical connectives expressing counting modulo a given fixed prime $p$.

Superpolynomial lower bounds on the refutation size in the LovaszSchrijver system $LS$. One promising approach might
be to prove the monotone feasible interpolation property (for the nonmonotone 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.

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 superlogarithmic rank lower bounds for this system (see
Complexity of Semialgebraic Proofs for the context
and an $\Omega(\log n)$ bound).
 For a space complexity measure $\mu$, define its amortized 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
treelike or regular resolution and for $\Sigma_2$ space, and these questions are equivalent to
several prominent open problems regarding relations between complexity of Hilbertstyle and
configurational proofs. For an extended context, see On Space and Depth in
Resolution and Space
characterizations of complexity measures....
 Is SumofSquares automatizable with respect to degree? Is it automatizable with respect to monomial
size? These are arguably the most important questions left open by the breakthrough papers Automating Resolution is NPHard, Automating Algebraic Proof Systems is
NPHard.
 Prove supercritical tradeoffs (see A new kind of
tradeoffs... for a highlevel explanation of the phenomenon) between size and depth in either
Resolution or Cutting Planes. Say, construct unsatisfiable CNFs that have polynomial or quasipolynomial
size DAGlike refutations in one of these two systems but with the property that every such refutation must
have superlinear depth.
 The polynomial version of supercritical tradeoff between resolution size and clause space was
proved in TimeSpace Tradeoffs...
This result is a bit disappointing numerically, however: the tradeoff effect vanishes at size $n^{\epsilon
\log \log n/\log \log \log n }$ which is barely superpolynomial. Do there exist unsatisfiable CNFs that have
quasipolynomial size DAGlike resolution refutations with the property that every such refutation must
have superlinear clause space?

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.

On the Power and Limitations... has recently
proved that the Stabbing Planes proof system with polynomially bounded coefficients can be quasipolynomially
simulated by Cutting Planes. Can the restriction on the coefficients be removed? Can the simulation be improved
to polynomial?

Resolution with Counting... has
proved superpolynomial lower bounds for the system Res(Lin). Can such bounds be established for systems of
linear equations resulting from natural translations of CNF formulas?
 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).
 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.

Let $PHP^\infty_n$ be the pigeonholeprinciple with infinitely (= arbitrarily many) pigeons. Does it have
polynomial size proofs in boundeddepth Frege?

The answer to the previous question is affirmative if "polynomial" is replaced by "quasipolynomial"
(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 quasipolynomial size proofs of $PHP^\infty_n$ for any fixed $k$?
 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.

The onto functional pigeonholeprinciple $ontoFPHP^m_n$ simply asserts that there is no bijection between
$[m]$ and $[n]$. Prove polynomial calculus degree lower bounds for $ontoFPHP^{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.
Solved
 (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 in A generalized method...

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 quasipolynomial size
refutations in
On the Complexity of Branching Proofs. Several problems
still remain open, like what will happen to random 3CNFs 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.

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.
Solved in Total Space in Resolution and Space proof complexity for
random 3CNFs.

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.
 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 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 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 quasirandomness.

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:

LogRank 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 socalled symmetric predicates it was solved in Quantum communication
complexity of symmetric predicates, and the next challenge is to extend this to socalled
blockcomposed functions.
 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 in Upper bounds for the diameter... and
Diameter of Polyhedra: Limits of
Abstraction, and at some point even became the subject of a Polymath
project.