ICTS

Tree Resolution, lower bounds via Prover-Delayer games.
General Resolution, the size-width relation as a lower-bound technqiue.

Brief overview of Frege and subclasses

-

Semi-algebraic systems SA
Brief overview of IPS

TBA

TBA 

TBA

TBA

TBA

In this talk, we explore the torus polynomial approximation based approach towards a long-standing question: whether AND can be computed by CC^0 circuits - the class of constant-depth polynomial size circuits containing MOD_m gates for some natural number m.

In this talk, we describe lower bound arguments against symmetric CC^0-circuits for computing AND. More precisely, we prove that any depth h symmetric CC^0 circuit requires 2^{Omega(n^{1/O(h)})) size to compute AND. The technique we use - the torus polynomial approximation - was introduced by Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) as an approach for proving lower bounds against ACC0 - a class containing CC0 where the circuits are also allowed AND, OR and NOT gates. We will describe this framework as wel, in the talk.

Joint work with Vaibhav Krishan (IMSc)

Ideal Proof System is an algebraic proof system, where the complexity of proof is measured in terms of algebraic complexity of the polynomials involved. One of the methods of proving lower bounds against IPS is functional method, which "transfers" syntactic lower bounds to IPS lower bounds. In this talk, we will see how to use functional method for proving lower bounds against restricted classes of IPS over large fields of positive characteristic. This is based on a joint work with Nutan Limaye, Varun Ramanathan, and Srikanth Srinivasan (https://eccc.weizmann.ac.il/report/2025/079/).

 The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it asserts that the rank and partitioning number of a Boolean matrix are quasi-polynomially related.
In this talk, I will present a relaxed but still equivalent version of the conjecture based on a new matrix parameter, $\pm$-rank: the minimum number of all-1 rectangles needed to express the Boolean matrix as a $\pm 1$-sum. $\pm$-rank lies between rank and partition number, and our main result shows that it is in fact equivalent to rank up to a logarithmic factor. This reframes the log-rank conjecture as: can every signed decomposition of a Boolean matrix be made positive with only quasi-polynomial blowup?
Additionally, I will show that the log-rank conjecture is equivalent to a conjecture on cross-intersecting set systems.
The talk is based on joint work with Shachar Lovett and Morgan Shirley.

TFZPP is the class of total NP search problems which can be solved by polynomial time randomized algorithms. We prove that in the black-box setting, TFZPP can be separated from all major TFNP classes. We initiate work on developing a taxonomy of TFZPP problems.

Based on joint work with Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, and Weiqiang Yuan which appeared at ITCS 2026.

G\"{o}\"{o}s et al. showed that $\Res \wedge \uSA = \revres$ in the following sense: if a formula $\phi$ has refutations of size at most $s$ and width/degree at most $w$ in both $\Res$ and $\uSA$, then there is a refutation for $\phi$ of size at most $\poly(s \cdot 2^w)$ in $\revres$. Their proof relies on the TFNP characterization of the aforementioned proof systems.

In this talk, we dicuss a direct and simplified proof of this result, simultaneously achieving better bounds: we show that if for a formula $\phi$ there are refutations of size at most $s$ in both $\Res$ and $\uSA$, then there is a refutation of $\phi$ of size at most $\poly(s)$ in $\revres$. This potentially allows us to ``lift'' size lower bounds from $\revres$ to $\Res$ for the formulas for which there are upper bounds in $\uSA$. This kind of lifting was not possible before because of the exponential blow-up in size from the width.

Finally, we generalize those intersection theorems to some proof systems for which we currently do not have a TFNP characterization.

In this talk, we discuss the propositional proof system resolution over parities ($\text{Res}(\oplus)$), which extends standard resolution by operating with disjunctions of linear equations modulo 2. The main open problem for this system, proving a superpolynomial lower bound on the proof size, remains unresolved. Nevertheless, we contribute to the study of the bounded-depth case.

We show that for any unsatisfiable CNF formula $\varphi$ that requires resolution refutation width at least $w$, and for any $1$-stifling gadget $g$ (for example, $g=MAJ_3$), (1) every Res($\oplus$) refutation of the lifted formula $\varphi \circ g$ of size at most $S$ has depth at least $\Omega(w^2/\log S)$; (2) every $\resoplus$ refutation of the lifted formula $\varphi \circ g$ has size $\Omega(w^2)$.

Our proof combines the random-walk-with-restarts method of Alekseev and Itsykson [STOC 2025] with a new idea: the random walk is defined relative to the structure of the refutation graph, rather than by a distribution on inputs induced by the formula.

We establish two applications of our technique. First, we construct a family of polynomial-size formulas that admit polynomial-size resolution refutations, while any Res($\oplus$) refutation of depth $o(n^2/\log^4 n)$ requires superpolynomial size.

Second, we prove that, for every constant $\varepsilon$>0, automatability is NP-hard for any propositional proof system that lies between regular resolution and depth-$n^{2-\varepsilon}$ Res($\oplus$).

The talk is based on joint work with Vladimir Podolskii and Alexander Shekhovtsov.

Circuit complexity lower bounds for explicit functions are hard to prove. This has been true anecdotally but has also been backed up by the Natural Proof Barrier framework of Razborov and Rudich, which views lower bound proofs as computational tasks. It states that assuming the existence of a pseudorandom function generator supported on small circuits there is no "natural" lower bound proof that a function does not have a small circuit.

When restricting to constant depth circuits we are able to prove far stronger, subexponential, lower bounds. However improvements on these lower bounds have also been anecdotally hard to prove. We note that most state-of-the-art lower bound proofs for constant depth circuits are computational tasks that are computable by polysize constant depth circuits. More generally, we show that they are "AC0-natural". We then show that "AC0-natural" lower bound proofs cannot significantly improve the state of the art lower bounds. Notably we show this unconditionally by providing a construction of pseudorandom function generators supported on constant depth circuits of subexponential size that fool ALL polysize constant depth circuits. This is proven via the best known lower bounds against constant depth circuits, thereby using the lower bound itself to prove the hardness of improving the lower bound.

We study the average-case hardness of establishing that a graph does not have a large clique in both proof and communication complexity. We show exponential lower bounds on the length of cutting planes and bounded-depth resolution over parities refutations of the binary encoding of clique formulas on randomly sampled dense graphs. Moreover, we show that the randomized communication complexity of finding a falsified clause in these formulas is polynomial.

Based on joint work with de Rezende, Engström, Ghannane, and Riazanov that appeared at ICALP'26.

A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean functions; the prevailing conjecture is that they cannot be so. In a seminal work, Razborov (2002) resolved this question for AND-functions of the form
$F(x,y)=f(x_1 \land y_1 , \cdots , ,x_n \land y_n)$,
when the outer function f is symmetric, by proving that their bounded-error quantum and classical communication complexities are polynomially related. Since then, extending this result to all AND-functions has remained open and has been posed by several authors.
In this work, we settle this problem in a strong way. We show that for every Boolean function f, the bounded-error quantum and classical deterministic communication complexities of the function $f \circ \text{AND}_2$ are polynomially related, up to polylogarithmic factors in n. We prove this by showing that both are characterized--up to polynomial loss--by the logarithm of the De Morgan sparsity of f.
Our results build on the recent work of Chattopadhyay, Dahiya, and Lovett (2025) on structural characterizations of non-sparse Boolean functions, which we extend to resolve the conjecture for general AND-functions

The Lovász-Theta function of a graph is an important function which can be used to analyze several fundamental properties of a graph. In particular, the Lovász-Theta function is an upper bound on the Shannon capacity of a graph and the Lovász-Theta function of the complement of a graph is always between the clique number and the chromatic number of the graph.
 
For a random G(n,1/2) graph, it has long been known that the Lovász-Theta is a constant times the square root of n but the exact constant was unknown. In this work, we resolve this question by showing that with high probability, the Lovász-Theta function of a random graph is (1+o(1)) times the square root of n.

To prove this result, we give an intricate and novel construction of a candidate solution for the dual SDP for the Lovász-Theta function and show that with high probability, it is feasible and has value (1+o(1)) times the square root of n. In this talk, I will describe our construction and give intuition for why it works.

We study non-deterministic representation of Boolean functions by polynomials.
A polynomial $p(x)$ is said to be a \emph{non-deterministic polynomial} for a
Boolean function $f$ if for all $a\in \{0,1\}^n$, $p(a)\neq 0$ iff $f(a)=1$.
The \emph{non-deterministic degree} of $f$, denoted $\ndeg(f)$, is the
minimal degree of a non-deterministic polynomial for $f$.

In this talk, we will explore extremal properties of non-deterministic
represenation. In particular, we will show that almost all Boolean functions
on $n$ variables have non-deterministic degree at most
$n/2 + O(\sqrt{n\log n})$. This confirms a conjecture of (Iyer et al., 2023).
Furthermore, together with their lower bound, it establishes a tight bound on
the rational degree of random Boolean functions up to lower order terms.
We also disprove a conjecture of (Kothari et al., 2026) about effective
hypercube nullstellensatz for more than two polynomials.

This talk is based on a joint work with Sudharshan Rajagopalan (IIT Hyderabad).

An overview of recent developments in topological methods for use in separating pseudodeterministic and randomized communication complexity as well as tightly determining the sign rank of the gap-hamming problem.

Techniques involve Z2-equivariant topology and the design of replicable learning algorithms.

The red-blue pebble game is a well known two-player game on graphs that has been used in the past as a tool to analyze complexity measures in several computation models as well as proof systems. We define a new way to measure the cost of the game, the blue cost, which only counts the number of pebbles that are colored blue during the game. This new measure characterizes exactly several space bounds in tree-like and negative Resolution.

In particular we prove that for any unsatisfiable formula $F$, the clause space requirements of the formula in tree-like Resolution, exactly coincide with the minimum blue pebbling cost of the game played on a refutation graph of $F$ (not necessarily a tree). This exactly parallels the known result for general Resolution in terms of the standard black pebble game, and improves the existing approximated characterization of tree-like space in terms of reversible pebbling.

We show that the blue pebbling cost is also well suited for analyzing the space requirements of the lifted pebbling formulas $Peb_G[\vee]$ and $Peb_G[\oplus]$ in the two Resolution restrictions. In the case of tree-like Resolution, the clause space of $Peb_G[\vee]$ asymptotically coincides with the blue cost of the underlying graph $G$.
For the case of negative Resolution, we obtain almost matching upper and lower bounds for the space in the two classes of lifted formulas, similar to the ones existing for general Resolution.

We also prove a close to optimal space separation between tree-like and negative Resolution, presenting a class of formulas with $n$ variables that require clause space $\Omega(\frac{n}{\log n})$ in negative Resolution, but have constant space tree-like refutations. This contrasts with the fact that negative Resolution can simulate tree-like Resolution with a small increase in size.

We present a generic way to obtain level lower bounds for (promise) CSP hierarchies from degree lower bounds for algebraic proof systems. More specifically, we show that pseudo-reduction operators in the sense of Alekhnovich and Razborov [Proc. Steklov Inst. Math. 2003] can be used to fool the cohomological k-consistency algorithm. As applications, we prove optimal level lower bounds for c vs. l-coloring for all l≥c≥3, and give a simplified proof of the lower bounds for lax and null-constraining CSPs of Chan and Ng [STOC 2025].

In algebraic complexity theory, one typically studies algebraic models to compute polynomials over fields. As a generalization, one can consider polynomials over semirings; in particular, we’ll focus on min-plus semirings. Polynomials over min-plus semirings are min-of-sums and so, these correspond to several minimization problems (e.g., Travelling Salesman problem). Many dynamic programming algorithms (e.g., Bellman-Held-Karp algorithm for TSP) can be viewed as circuits over min-plus semirings. In this talk, we’ll discuss about algebraic branching programs (which are weaker than circuits) over min-plus semirings. In particular, we’ll talk about ABPs of small width (which are well-studied over fields) over min-plus semirings; here, restricting the width means that only a few DP table entries are allowed to be updated in each round/phase of the algorithm. Finally, we’ll discuss an analogue of the class VNP (which, over fields, is defined as hypercube sums over small circuits) over min-plus semirings, its relationship with VP, and its equivalent definitions in terms of weaker (than circuits) models. This talk will be based on joint discussions with Balagopal Komarath and Jayalal Sarma