Meetings
take place online
and consist of informal talks dedicated to topics of interest
in computational
complexity theory
and related areas. Our goal is for these meetings to
serve as a forum for discussion and quick dissemination of results.
While presentations should be reasonably self-contained, our target is
a more specialised audience.
The duration of each talk is determined by the speaker. Meetings will not be recorded, and
anyone
interested in complexity theory is welcome to join. You
can join the mailing list
for talk announcements and keep track of them using this calendar.
Please
contact Igor
Oliveira (Warwick) or Rahul
Santhanam
(Oxford) if you have any questions.
Seminars
are typically held on Thursday
at 5pm London local time (GMT) via Zoom. A link
will be
posted here shortly before each meeting.
Upcoming Talks:
28/January/2021 at 5pm London Time
Alexandros Hollender (Oxford) - The complexity of gradient descent: CLS = PPAD ∩ PLS
Abstract:
Please
see https://arxiv.org/abs/2011.01929
Past Talks:
14/January/2021 at 5pm London Time [ Slides ]
Eric Allender (Rutgers) - Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity
Abstract:
A
version of time-bounded Kolmogorov complexity, denoted KT, has received
attention in the past several years, due to its close connection to
circuit complexity and to the Minimum Circuit Size Problem MCSP.
Essentially all results about the complexity of MCSP hold also for MKTP
(the problem of computing the KT complexity of a string). Both MKTP and
MCSP are hard for SZK (Statistical Zero Knowledge) under BPP-Turing
reductions; neither is known to be NP-complete.
Recently, some hardness results for MKTP were proved that are not (yet)
known to hold for MCSP. In particular, MKTP is hard for DET (a
subclass of P) under nonuniform NC^0 m-reductions.
In new work, we improve this, to show that MKTP is hard for the
(apparently larger) class NISZKL under not only NC^0 reductions but
even under projections. Also MKTP is hard for NISZK under P/poly
m-reductions. Here, NISZK is the class of problems with non-interactive
zero-knowledge proofs, and NISZKL is the non-interactive version of the
class SZKL that was studied by Dvir et al.
In this talk, we'll explain why we should care about completeness under
projections, and what these new results tell us about where MCSP and
MKTP fit in the complexity landscape.
This is joint work with John Gouwar, Shuichi Hirahara, and Caleb Robelle.
3/December/2020 at 5pm London Time
Toniann Pitassi (Toronto/IAS) - Lifting with Sunflowers [ Slides ]
Abstract: In
this talk I will first motivate lifting theorems where lower bounds on
communication complexity for composed functions are obtained by a
general simulation theorem, essentially showing that no protocol can do
better than the obvious "query" algorithm. I'll give a self-contained
simplified proof of lifting that uses the sunflower lemma, and then
give some applications and open problems. This is joint work with
Shachar Lovett, Raghu Meka, Ian Mertz and Jiapeng Zhang.
12/November/2020 at 5pm London Time
Roei Tell (MIT) - Simple and fast derandomization from very
hard functions - Eliminating randomness at almost no cost [ Slides ]
Abstract:
Please
see https://eccc.weizmann.ac.il/report/2020/148/
29/October/2020 at 5pm London Time
Ryan Williams (MIT) - Almost-everywhere circuit
lower bounds from circuit-analysis algorithms [ Slides ]
Abstract:
Please
see https://eccc.weizmann.ac.il/report/2020/150/
15/October/2020 at 5pm London Time
Christian Ikenmeyer (Liverpool) - Recent progress on GCT [ Slides ]
Abstract: In
2016 the papers [Ikenmeyer-Panova FOCS 2016] and
[Bürgisser-Ikenmeyer-Panova FOCS 2016] proved that the
information about occurrences of irreducible representations in
coordinate rings of certain orbit closures is too coarse to separate
the algebraic complexity classes VBP and VNP. This disproved a key
conjecture in geometric complexity theory. This talk gives an overview
of 4 recent papers that were published after this insight.
In general, we
know that geometric complexity lower bounds can always be proved by
so-called highest weight polynomials. In the paper "On the complexity
of evaluating highest weight vectors" with Bläser and
Dörfler we prove that deciding nonzeroness of an evaluation of
a highest weight polynomial is NP-hard, even on points of Waring rank
3.
This motivates the study of
representation theoretic multiplicities as a way to circumvent working
with highest weight polynomials directly. In the paper "The
Computational Complexity of Plethysm Coefficients" with Fischer we
prove that even deciding the positivity of plethysm coefficients is
NP-hard, which makes several representation theoretic approaches more
difficult to implement.
Despite their
NP-hardness, the representation theoretic multiplicities could in
principle be a viable path towards separating complexity classes. In
the paper "On Geometric Complexity Theory: Multiplicity Obstructions
Are Stronger Than Occurrence Obstructions" with Dörfler and
Panova we give a first setting where a toy lower bound can be proved
with multiplicities, but where the same bound is provably impossible to
show using only occurrences.
We build on this
result in the paper "Implementing geometric complexity theory: On the
separation of orbit closures via symmetries" with Kandasamy. This is a
full implementation of the GCT approach in a toy model, using the
symmetry groups of two polynomials as a method to obtain multiplicity
obstructions
1/October/2020 at 5pm London Time
Rafael Pass (Cornell) - On one-way functions and Kolmogorov
complexity [ Slides
]
Abstract: We
prove the equivalence of two fundamental problems in the theory of
computing.
For every polynomial t(n)>2n, the following are equivalent:
Cryptographic one-way functions exists;
The t-time bounded Kolmogorov Complexity problem is mildly
hard-on-average.
In doing so, we present the first natural, and well-studied,
computational problem
characterizing the feasibility of the central private-key primitives
and protocols in Cryptography. Joint work with Yanyi Liu.
[ ECCC ]
17/September/2020 at 1pm London Time
Shuichi Hirahara (National Institute of Informatics, Tokyo)
- Meta-complexity theoretic approach to complexity theory
[ Slides
]
Abstract: In
this talk, I will present a broad overview of
“meta-complexity
theory” --- an emerging field of complexity theory.
Meta-complexity refers to the computational complexity of problems
asking to compute some complexity. Examples of meta-complexity
theoretic problems include the Minimum Circuit Size Problem (MCSP),
which asks for the circuit complexity of a given function, and the
time-bounded Kolmogorov complexity problem (MINKT), which asks for the
time complexity of a given string. Focusing on the relationship among
meta-complexity, average-case complexity, cryptography, and
Impagliazzo’s five worlds, I will survey recent results and
explain new “meta-complexity theoretic” approaches
towards
resolving old and challenging open questions of complexity theory.
20/August/2020 at 5pm London Time
Srikanth Srinivasan (IIT Bombay) - A robust version of
Heged\H{u}s's lemma
[ Slides
]
Abstract: Heged\H{u}s's
lemma is the following combinatorial statement regarding polynomials
over finite fields. Over a field F of characteristic p > 0 and
for q
a power of p, the lemma says that any multilinear polynomial P\in
\F[x_1,\ldots,x_n] of degree less than q that vanishes at all points in
{0,1}^n of Hamming weight k\in [q,n-q] must also vanish at all points
in {0,1}^n of weight k + q. This lemma was used by Heged\H{u}s (2009)
to give a solution to Galvin's problem, an extremal problem about set
systems; by Alon, Kumar and Volk (2018) to improve the best-known
multilinear circuit lower bounds; and by Hrube\v{s}, Ramamoorthy, Rao
and Yehudayoff (2019) to prove optimal lower bounds against depth-2
threshold circuits for computing some symmetric functions.
In this result, we
formulate a robust
version of Heged\H{u}s's lemma. Informally, this version says that if a
polynomial of degree o(q) vanishes at most points of weight k, then it
vanishes at many points of weight k+q. We prove this lemma and give
some applications to polynomial approximations of Boolean functions.
6/August/2020 at 5pm London Time
Mrinal Kumar (IIT Bombay) - On the existence of
algebraically natural proofs
[ Slides
]
Abstract:
A
recent line of research in algebraic complexity aims to understand
whether there is a Natural Proofs like barrier in algebraic complexity.
A key question here is to understand whether the complexity class VP
has constructible equations, i.e., whether there is a non-zero
polynomial of low degree and circuit complexity which vanishes on the
coefficient vectors of all efficiently computable low degree
polynomials.
In this talk, we will
discuss a recent result where we make some progress on a natural
special case of this question, and show the existence of constructible
equations for polynomials in VP which have bounded integer
coefficients. More formally, we show that for every constant c >
0, there is a family {P_{N, c}} of polynomials with degree and
algebraic circuit complexity polynomially bounded in the number of
variables N that satisfies the following properties:
1. For every family {f_n} of polynomials in VP, where f_n is an n
variate polynomial of degree at most n^c with bounded integer
coefficients and for N = \binom{n^c + n}{n}, P_{N,c} vanishes on the
coefficient vector of f_n.
2.There exists a family {h_n} of polynomials where h_n is an n variate
polynomial of degree at most n^c with bounded integer coefficients such
that for N = \binom{n^c + n}{n}, P_{N,c} does not vanish on the
coefficient vector of h_n.
Our proofs are elementary
and rely on the existence of (non-explicit) hitting sets for VP, and
also extends to the seemingly larger class VNP.
The talk is based on joint
work with Prerona Chatterjee, C. Ramya, Ramprasad Saptharishi and
Anamay Tengse.
23/July/2020 at 5pm London Time
Benjamin Rossman (Duke University) - Size-depth tradeoff for
multiplying k permutations
[ Slides
]
Abstract: We
consider the problem of computing the product of k n-by-n permutation
matrices. This problem is equivalent to Parity_k when n = 2; it is
complete for NC1 when n = 5, and complete for Logspace when k = n.
Understanding the formula complexity of this important problem is a
concrete approach to separating NC1 from Logspace.
In the bounded-depth
setting, the problem
is solvable by depth d+1 AC0 formulas of size n^O(min(dk^(1/d), log k))
for all k,n,d. In the regime k <= log log n, a tight n^Omega(log
k)
lower bound was shown in [R. ’14] up to depth (log n)/(poly
k).
In this work, we establish a tradeoff n^Omega(dk^(1/2d)) for small
depths d <= log k. The exponent 1/2d in this expression improves
an
1/(exp d) lower bound of [Beame-Impagliazzo-Pitassi ’98]. We
further improve this exponent to 1/d for *monotone* AC0 formulas
computing the product of k *sub-permutation* matrices, and to 2/d when
AND gates have fan-in polylog n; both bounds are optimal. In this talk,
I will describe the interesting combinatorial framework behind these
tradeoffs.
16/July/2020 at 5pm London Time
Lijie Chen (MIT) - Sharp threshold results
for computational complexity
[ Slides
]
Abstract:
Please
see https://eccc.weizmann.ac.il/report/2020/065/
2/July/2020 at 5pm London Time
Or Meir (University of Haifa) - The KRW Conjecture:
Past, present, and future
[ Slides
]
Abstract: Proving
super-logarithmic lower bounds on the depth of circuits is one of the
main frontiers of circuit complexity. In 1991, Karchmer, Raz and
Wigderson observed that we could resolve this question by proving the
following conjecture: Given two boolean functions f,g, the depth
complexity of their composition is about the sum of their individual
depth complexities. While we cannot prove the conjecture yet,
there has been some exciting progress toward such a proof, some of it
in the last few years.
In this
talk, I will survey the
state-of-the-art in this line of research. In particular, I will
describe a recent result that proves the conjecture for a new family of
functions based on lifting theorems. I will also propose some future
directions, including specific open problems that might be tractable.
Based on a joint work with Susanna F. de Rezende, Jakob Nordstrom,
Toniann Pitassi, and Robert Robere.
18/June/2020 at 5pm London Time
Rahul Ilango (MIT) - A lifting-esque theorem for
constant depth formulas with consequences for MCSP and lower bounds
[ Slides
]
Abstract:
Connections
between the Minimum Circuit Size Problem (MCSP) and a growing list of
subfields -- including cryptography, learning theory, and average-case
complexity -- strongly motivate understanding the computational
complexity of MCSP. While attempts to prove the intractability of MCSP
date as far back as the late 1950s, resolving this question remains a
major open problem.
This talk
will discuss progress in understanding
the Minimum Circuit Size Problem for restricted classes of circuits.
While Masek proved in the late 1970s that minimizing DNF formulas is
NP-hard, extending this to depth-3 formulas with AND and OR gates was
open. We show that minimizing depth-d formulas given a function's truth
table is NP-hard for all d >= 2, under quasipolynomial-time
randomized reductions. Our approach is based on a method to "lift''
depth-d formula lower bounds to depth-(d+1). Combined with existing
depth-hierarchy theorems, this method also implies the existence of a
function with a 2^{c_d(n^\epsilon)} additive gap between its depth-d
and depth-(d+1) formula complexity where c_d > 0 is some
constant
that depends on d and \epsilon > 0 is some constant
*independent* of
d.