We propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words.

The paper explains several advantages of the new model. A central aspect is that it allows us ... more >>>

We prove that \emph{at least} one of the following statements is true:

-- (Infinitely-often) Public-key encryption and key agreement can be based on injective one-way functions;
-- For every inverse polynomial $\epsilon$, the 4-round protocol from [Feige and Shamir, STOC 90] is distributional concurrent zero knowledge for any ... more >>>

Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such ``magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits ... more >>>

We consider $\cal C$-compression games, a hybrid model between computational and communication complexity. A $\cal C$-compression game for a function $f \colon \{0,1\}^n \to \{0,1\}$ is a two-party communication game, where the first party Alice knows the entire input $x$ but is restricted to use strategies computed by $\cal C$-circuits, ... more >>>

We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:

- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can ... more >>>

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

We show that in the context of nonuniform complexity,
nondeterministic logarithmic space bounded computation can be made
unambiguous. An analogous result holds for the class of problems
reducible to context-free languages. In terms of complexity classes,
this can be stated as:
NL/poly = UL/poly
LogCFL/poly ... more >>>

A basic question in any computational model is how to reliably compute a given function when the inputs or intermediate computations are subject to noise at a constant rate. Ideally, one would like to use at most a constant factor more resources compared to the noise-free case. This question has ... more >>>

We prove a time-space tradeoff lower bound of $T =
\Omega\left(n\log(\frac{n}{S}) \log \log(\frac{n}{S})\right) $ for
randomized oblivious branching programs to compute $1GAP$, also
known as the pointer jumping problem, a problem for which there is a
simple deterministic time $n$ and space $O(\log n)$ RAM (random
access machine) algorithm.

In ... more >>>

The long code is a central tool in hardness of approximation, especially in
questions related to the unique games conjecture. We construct a new code that
is exponentially more ecient, but can still be used in many of these applications.
Using the new code we obtain exponential improvements over several ... more >>>

A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and non-malleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These ... more >>>

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>

We give in this paper a different and simpler proof of the tractability of Mal'tsev contraints.

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... more >>>

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,
that get rid of some drawbacks of previous measure notions:
martingale families can make money on all strings,
and yield random sequences with an equal frequency of 0's and 1's.
As applications to F-measure,
more >>>

We consider a model of teaching in which the learners are consistent and have bounded state, but are otherwise arbitrary. The teacher is non-interactive and ``massively open'': the teacher broadcasts a sequence of examples of an arbitrary target concept, intended for every possible on-line learning algorithm to learn from. We ... more >>>

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. ... more >>>

We show that there are degree-$d$ polynomials over $\mathbb{F}_{2}$ with
correlation $\Omega(d/\sqrt{n})$ with the majority function on $n$
bits. This matches the $O(d/\sqrt{n})$ bound by Smolensky.

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to ... more >>>

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>>

Hypercontractive inequalities for real-valued functions over the Boolean cube play an important role in theoretical computer science. In this work, we prove a hypercontractive inequality for matrix-valued functions defined over large alphabets, generalizing the result of Ben-Aroya, Regev, de Wolf (FOCS'08) for the Boolean alphabet. To obtain our result we ... more >>>

In continuation to our recent work on noncommutative
polynomial factorization, we consider the factorization problem for
matrices of polynomials and show the following results.
\begin{itemize}
\item Given as input a full rank $d\times d$ matrix $M$ whose entries
$M_{ij}$ are polynomials in the free noncommutative ring
more >>>

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices over $GF(2)$ have rigidity $\Omega(\frac{n^3}{r^2\log n})$ for rank $r \ge \sqrt{n}$, with high probability. This improves, for $r = o(n/\log n \log\log n)$, over the $\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$ bound that is known for many explicit matrices.

Our result implies that the explicit ... more >>>

We study the matroid intersection problem from the parallel complexity perspective. Given
two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted ... more >>>

We introduce a simple technique to obtain reductions
between optimization constraint satisfaction problems. The
technique uses the probabilistic method to reduce the size of
disjunctions. As a first application, we prove the
MAX NP-completeness of MAX 3SAT without using the PCP theorem
(thus solving an open ... more >>>

We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice ($AMEXP_{/2^{n^{\varepsilon}}}$) requires circuit complexity at least $2^n/n$. Previously, the best known such near-maximum lower bounds were for symmetric exponential time by Chen, Hirahara, and Ren (STOC'24) and Li (STOC'24), or randomized exponential time with MCSP oracle and ... more >>>

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ time due to Micali and Vazirani ... more >>>

Maximum-likelihood decoding is one of the central algorithmic
problems in coding theory. It has been known for over 25 years
that maximum-likelihood decoding of general linear codes is
NP-hard. Nevertheless, it was so far unknown whether maximum-
likelihood decoding remains hard for any specific family of
more >>>

We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weakening (the system MaxResW), p-simulates tree-like resolution. In devising a lower bound technique specific to MaxRes (and not merely inheriting lower bounds from ... more >>>

We associate a CNF-formula to every instance of the mean-payoff game problem in such a way that if the value of the game is non-negative the formula is satisfiable, and if the value of the game is negative the formula has a polynomial-size refutation in $\Sigma_2$-Frege (i.e.~DNF-resolution). This reduces mean-payoff ... more >>>

In this paper, we propose a quantification of distributions on a set
of strings, in terms of how close to pseudorandom the distribution
is. The quantification is an adaptation of the theory of dimension of
sets of infinite sequences first introduced by Lutz
\cite{Lutz:DISS}.
We show that this definition ... more >>>

We revisit the problem of generalising Lutz's resource bounded measure
(rbm) to small complexity classes.
We propose a definition of a perfect rbm on P,
and give sufficient and necessary conditions for such a measure to exist.
We also revisit $\mu_\tau$, an rbm for P
defined in previous articles (c.f. ... more >>>

In (Allender and Strauss, FOCS '95), we defined a notion of
measure on the complexity class P (in the spirit of the work of (Lutz,
JCSS '92) that provides a notion of measure on complexity classes at least
as large as E, and the work of (Mayordomo, Phd. ... more >>>

We present a notion of resource-bounded measure for P and other
subexponential-time classes. This generalization is based on Lutz's
notion of measure, but overcomes the limitations that cause Lutz's
definitions to apply only to classes at least as large as E. We
present many of the basic properties of this ... more >>>

While deterministic finite automata seem to be well understood, surprisingly
many important problems
concerning nondeterministic finite automata (nfa's) remain open.

One such problem area is the study of different measures of nondeterminism in
finite automata and the
estimation of the sizes of minimal nondeterministic finite automata. In this
paper the ... more >>>

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This paper addresses the simultaneous challenges of realizing these two distinct tasks with the same data ... more >>>

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.

Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS '91, Algorithmica '94), allow a user to store and maintain a large memory on a remote ... more >>>

If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>>

We show that the black-box complexity with memory restriction one of the $n$-dimensional $\onemax$ function class is at most $2n$. This disproves the $\Theta(n \log n)$ conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006) 525--544).

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in~$n$) of random samples. A line of recent works continued that research direction and showed that for ... more >>>

This paper presents the first Distributed Oblivious RAM (DORAM) protocol that achieves sub-logarithmic communication overhead without computational assumptions.
That is, given $n$ $d$-bit memory locations, we present an information-theoretically secure protocol which requires $o(d \cdot \log(n))$ bits of communication per access (when $d = \Omega(\log^2(n)$).

This comes as a surprise, ... more >>>

This paper studies the \emph{refuter} problems, a family of decision-tree $\mathrm{TFNP}$ problems capturing the metamathematical difficulty of proving proof complexity lower bounds. Suppose $\varphi$ is a hard tautology that does not admit any length-$s$ proof in some proof system $P$. In the corresponding refuter problem, we are given (query ... more >>>

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... more >>>

We show that if gap-3SAT has no sub-exponential time algorithms then a weak form of the sliding scale conjecture holds. Namely, for every $\alpha>0$ any algorithm for $n^\alpha$-approximating the value of label cover must run in time at least $n^{\Omega(\exp(1/\alpha))}$, where $n$ is the size of the instance.

Put differently, ... more >>>

We introduce the notion of \emph{Min-Entropic Optimality} thereby providing a framework for arguing that a given algorithm computes a function better than any other algorithm. An algorithm is $k(n)$ Min-Entropic Optimal if for every distribution $D$ with min-entropy at least $k(n)$, its expected running time when its input is drawn ... more >>>

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained
by setting all *-entries to constants 0 or 1. A system of semi-linear
equations over GF(2) has the form Mx=f(x), where M is a completion of
A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ... more >>>

The deficiency of a propositional formula F in CNF with n variables
and m clauses is defined as m-n. It is known that minimal
unsatisfiable formulas (unsatisfiable formulas which become
satisfiable by removing any clause) have positive deficiency.
Recognition of minimal unsatisfiable formulas is NP-hard, and it was
shown recently ... more >>>

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>

For circuit classes R, the fundamental computational problem, Min-R,
asks for the minimum R-size of a boolean function presented as a truth
table. Prominent examples of this problem include Min-DNF, and
Min-Circuit (also called MCSP). We begin by presenting a new reduction
proving that Min-DNF is NP-complete. It is significantly ... more >>>

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>>

We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions ... more >>>

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for ``easy'' Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an $n$-variate Boolean function $f$ computable by some unknown small circuit ... more >>>

One can learn any hypothesis class $H$ with $O(\log|H|)$ labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires $|X|^{O(\log|H|)}$ memory states, where $X$ is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>>

With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses ... more >>>

We initiate a systematic study of mixing in non-quasirandom groups.
Let $A$ and $B$ be two independent, high-entropy distributions over
a group $G$. We show that the product distribution $AB$ is statistically
close to the distribution $F(AB)$ for several choices of $G$ and
$F$, including:

(1) $G$ is the affine ... more >>>

In this note, we show the mixing of three-term progressions $(x, xg, xg^2)$ in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any $D$-quasirandom group $G$ and any three sets $A_1, A_2, A_3 \subset G$, we have
\[ \left|\Pr_{x,y\sim G}\left[ x \in ... more >>>

Model theory is a branch of mathematical logic that investigates the
logical properties of mathematical structures. It has been quite
successfully applied to computational complexity resulting in an
area of research called descriptive complexity theory. Descriptive
complexity is essentially a syntactical characterization of
complexity classes using logical formalisms. However, there ... more >>>

Borodin, Nielsen, and Rackoff gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin extended their work to facility location and set cover problems. We generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an ... more >>>

How can we trust the correctness of a learned model on a particular input of interest? Model accuracy is typically measured $on\ average$ over a distribution of inputs, giving no guarantee for any fixed input. This paper proposes a theoretically-founded solution to this problem: to train $Self$-$Proving\ models$ that prove ... more >>>

The classes of languages accepted by nondeterministic polynomial-time
Turing machines (NP machines, in short) that have restricted access to
an NP oracle --- the machines can ask k queries to the NP oracle and
the answer they receive is the number of queries ... more >>>

We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product ... more >>>

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

For any unsatisfiable CNF formula $F$ that is hard to refute in the Resolution proof system, we show that a gadget-composed version of $F$ is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with $F$ has large ... more >>>

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity, DNF sparsification, randomness extractors, and recent advances on the Erd\H{o}s-Rado sunflower conjecture. The recent breakthrough of Alweiss, Lovett, Wu and Zhang gives an improved bound on the maximum size of a $w$-set system that excludes ... more >>>

We study the computability of one-way functions and pseudorandom generators
by monotone circuits, showing a substantial gap between the two:
On one hand, there exist one-way functions that are computable
by (uniform) polynomial-size monotone functions, provided (of course)
that one-way functions exist at all.
On the other hand, ... more >>>

In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than VNP. We observe that these monotone analogues are not equivalent unlike their ... more >>>

The rank of a matrix has been used a number of times to prove lower
bounds on various types of complexity. In particular it has been used
for the size of monotone formulas and monotone span programs. In most
cases that this approach was used, there is not a single ... more >>>

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:
(1) Constant degree dimension expanders in finite ... more >>>

In this short note, we show that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections ... more >>>

We study the complexity of proving the Pigeon Hole
Principle (PHP) in a monotone variant of the Gentzen Calculus, also
known as Geometric Logic. We show that the standard encoding
of the PHP as a monotone sequent admits quasipolynomial-size proofs
in this system. This result is a consequence of ... more >>>

In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity.

\begin{itemize}

\item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>>

We show that an LK proof of size $m$ of a monotone sequent (a sequent

that contains only formulas in the basis $\wedge,\vee$) can be turned

into a proof containing only monotone formulas of size $m^{O(\log m)}$

and with the number of proof lines polynomial in $m$. Also we show

We study the problem of monotonicity testing over the hypercube. As
previously observed in several works, a positive answer to a natural question about routing
properties of the hypercube network would imply the existence of efficient
monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs
on the directed hypercube ... more >>>

In this paper we prove two results about $AC^0[\oplus]$ circuits.

We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that
$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at ... more >>>

We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor ... more >>>

In their influential paper `Short proofs are narrow -- resolution made simple', Ben-Sasson and Wigderson introduced a crucial tool for proving lower bounds on the lengths of proofs in the resolution calculus. Over a decade later their technique for showing lower bounds on the size of proofs, by examining the ... more >>>

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>

Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).

In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant ... more >>>

In a multi-$k$-ic depth three circuit every variable appears in at most $k$ of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables ... more >>>

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. ... more >>>

An arithmetic formula is multi-linear if the polynomial computed
by each of its sub-formulas is multi-linear. We prove that any
multi-linear arithmetic formula for the permanent or the
determinant of an $n \times n$ matrix is of size super-polynomial
in $n$.

In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011).

Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). ... more >>>

We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new ... more >>>

In this paper we first show that Tester for an $F$-algebra $A$
and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear
algorithm for the product of elements in $A$
(see Algebraic
complexity theory. vol. 315, Springer-Verlag). Our
result is constructive in deterministic polynomial time. ... more >>>

Several researchers, including Leonid Levin, Gerard 't Hooft, and
Stephen Wolfram, have argued that quantum mechanics will break down
before the factoring of large numbers becomes possible. If this is
true, then there should be a natural "Sure/Shor separator" -- that is,
a set of quantum ... more >>>

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}:

1. Noise-resistant. A syntactically multilinear ... more >>>

An arithmetic circuit or formula is multilinear if the polynomial
computed at each of its wires is multilinear.
We give an explicit example for a polynomial $f(x_1,...,x_n)$,
with coefficients in $\{0,1\}$, such that over any field:
1) $f$ can be computed by a polynomial-size multilinear circuit
of depth $O(\log^2 ... more >>>

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once ... more >>>

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone ... more >>>

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

We consider the threshold circuit complexity of computing
the multiple product modulo m in threshold circuits.

We consider the following basic problem: given an $n$-variate degree-$d$ homogeneous polynomial $f$ with real coefficients, compute a unit vector $x \in \mathbb{R}^n$ that maximizes $|f(x)|$. Besides its fundamental nature, this problem arises in many diverse contexts ranging from tensor and operator norms to graph expansion to quantum information ... more >>>

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions as a possible solution to the problem of extracting random keys for cryptographic protocols from weak sources of randomness.
They showed that under a very strong complexity theoretic assumption, there exists a constant $\alpha>0$ such that ... more >>>

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.

In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>>

We investigate the complexity of integration and
derivative for multivariate polynomials in the standard computation
model. The integration is in the unit cube $[0,1]^d$ for a
multivariate polynomial, which has format
$f(x_1,\cdots,
x_d)=p_1(x_1,\cdots, x_d)p_2(x_1,\cdots, x_d)\cdots p_k(x_1,\cdots,
x_d)$,
where each $p_i(x_1,\cdots, x_d)=\sum_{j=1}^d q_j(x_j)$ with
all single variable polynomials $q_j(x_j)$ ... more >>>

Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:

(1) In the white-box setting, given an n-variate noncommutative polynomial f in F over a field F (either a ... more >>>

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>

We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\begin{itemize}
\item If there exists a perfect (imperfect) $IO$ that is computationally secure ... more >>>

We review the past ten years in computational complexity theory by
focusing on ten theorems that the author enjoyed the most. We use
each of the theorems as a springboard to discuss work done in
various areas of complexity theory.