We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>

Graphical games have been proposed as a game-theoretic model of large-scale
distributed networks of non-cooperative agents. When the number of players is
large, and the underlying graph has low degree, they provide a concise way to
represent the players' payoffs. It has recently been shown that the problem of
finding ... more >>>

We introduce the notion of {\em natural} proof.
We argue that the known proofs of lower bounds on the complexity of explicit
Boolean functions in non-monotone models
fall within our definition of natural.
We show based on a hardness assumption
that natural proofs can't prove superpolynomial lower bounds ... more >>>

A long standing open problem in the computational complexity theory
is to separate NE from BPP, which is a subclass of $NP_T (NP\cap P/poly)$.
In this paper, we show that $NE\not\subseteq NP_T (NP \cap$ Nonexponentially-Dense-Class),
where Nonexponentially-Dense-Class is the class of languages A without exponential density
(for ... more >>>

We study the stability of covers of simplicial complexes. Given a map f:Y?X that satisfies almost all of the local conditions of being a cover, is it close to being a genuine cover of X? Complexes X for which this holds are called cover-stable. We show that this is equivalent ... more >>>

Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and $S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix. For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$, which we view as the heat measured by $v$ after an initial heat configuration $u$ is let to diffuse for $t$ time steps according to ... more >>>

We show that for all $\varepsilon>0$, for sufficiently large prime power $q\in\mathbb{N}$, for all $\delta>0$, it is NP-hard to distinguish whether a $2$-Prover-$1$-Round projection game with alphabet size $q$ has value at least $1-\delta$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly optimal alphabet-to-soundness tradeoff for $2$-query PCPs ... more >>>

Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured
that the variance of their highly successful priority sampling procedure
is not larger than the variance of the threshold sampling procedure with sample size one smaller.
The conjecture's significance is that the latter procedure is provably optimal ... more >>>

We show how one can use non-prime-power, composite moduli for
computing representations of the product of two $n\times n$ matrices
using only $n^{2+o(1)}$ multiplications.

We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity for natural parameter choices. Specifically, for any constant $\alpha > 0$, for $\delta > 2^{-\mathrm{poly}(1 / \varepsilon)}$, it uses $m + O(\log (1 / \delta))$ random bits to output $t = O(\log(1 ... more >>>

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ ... more >>>

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>>

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space
$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$
In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.
Previously, ... more >>>

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another ... more >>>

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.
For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.
Moreover, the queries we use are comparison ... more >>>

We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n^?(k/log k). Our trade-offs also apply to first-order counting logic, and ... more >>>

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

We present the best known separation
between tree-like and general resolution, improving
on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.
This is done by constructing a natural family of contradictions, of
size $n$, that have $O(n)$-size resolution
refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.
This result ... more >>>

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.

In this paper, we make ... more >>>

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,
the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.
Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ... more >>>

We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a ... more >>>

A nearest neighbor representation of a Boolean function $f$ is a set of vectors (anchors) labeled by $0$ or $1$ such that $f(x) = 1$ if and only if the closest anchor to $x$ is labeled by $1$. This model was introduced by Hajnal, Liu, and Turán (2022), who studied ... more >>>

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) ... more >>>

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean
functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

We conjecture that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$
such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions ... more >>>

It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>

We demonstrate a family of propositional formulas in conjunctive normal form
so that a formula of size $N$ requires size $2^{\Omega(\sqrt[7]{N/logN})}$
to refute using the tree-like OBDD refutation system of
Atserias, Kolaitis and Vardi
with respect to all variable orderings.
All known symbolic quantifier elimination algorithms for satisfiability
generate ... more >>>

Seeded extractors are fundamental objects in pseudorandomness and cryptography, and a deep line of work has designed polynomial-time seeded extractors with nearly-optimal parameters. However, existing constructions of seeded extractors with short seed length and large output length run in time $\Omega(n \log(1/\varepsilon))$ and often slower, where $n$ is the input ... more >>>

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk ... more >>>

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... more >>>

We first consider so-called {\em $(1,+s)$-branching programs}
in which along every consistent path at most $s$ variables are tested
more than once. We prove that any such program computing a
characteristic function of a linear code $C$ has size at least
more >>>

The use of Nepomnjascij's Theorem in the proofs of independence results
for bounded arithmetic theories is investigated. Using this result and similar ideas, the following statements are proven: (1) At least one of S_1 or TLS does not prove the Matiyasevich-Davis-Robinson-Putnam Theorem and (2) TLS does not prove Sigma^b_{1,1}=Pi^b_{1,1}. Here ... more >>>

We consider the general network information flow problem, which was
introduced by Ahlswede et. al. We show a periodicity effect: for
every integer m greater than 1, there exists an instance of the
network information flow problem that admits a solution if and only if
the alphabet size is a ... more >>>

The computational power of formal models for
networks of spiking neurons is compared with
that of other neural network models based on
McCulloch Pitts neurons (i.e. threshold gates)
respectively sigmoidal gates. In particular it
is shown that networks of spiking neurons are
... more >>>

One of the most basic pattern recognition problems is whether a
certain local feature occurs in some linear array to the left of
some other local feature. We construct in this article circuits that
solve this problem with an asymptotically optimal number of
threshold gates. Furthermore it is shown that ... more >>>

It has been known for quite a while that the Vapnik-Chervonenkis dimension
(VC-dimension) of a feedforward neural net with linear threshold gates is at
most O(w log w), where w is the total number of weights in the neural net.
We show in this paper that this bound is in ... more >>>

Local receptive field neurons comprise such well-known and widely
used unit types as radial basis function neurons and neurons with
center-surround receptive field. We study the Vapnik-Chervonenkis
(VC) dimension of feedforward neural networks with one hidden layer
of these units. For several variants of local receptive field
neurons we show ... more >>>

In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths $2$ and $3$, and achieving results for higher depths has been ... more >>>

Experimental data show that biological synapses behave quite
differently from the symbolic synapses in all common artificial
neural network models. Biological synapses are dynamic, i.e., their
``weight'' changes on a short time scale by several hundred percent
in dependence of the past input to the synapse. ... more >>>

In this work we explore error-correcting codes derived from
the ``lifting'' of ``affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

In this work we explore error-correcting codes derived from
the ``lifting'' of ``affine-invariant'' codes.
Affine-invariant codes are simply linear codes whose coordinates
are a vector space over a field and which are invariant under
affine-transformations of the coordinate space. Lifting takes codes
defined over a vector space of small dimension ... more >>>

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability
of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$
quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error
randomized algorithms. This is the first known improvement over brute force search in ... more >>>

The Steiner tree problem asks for the shortest tree connecting
a given set of terminal points in a metric space. We design
new approximation algorithms for the Steiner tree problems
using a novel technique of choosing Steiner points in dependence
on the possible deviation from ... more >>>

For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity ... more >>>

In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... more >>>

Ordered binary decision diagrams (OBDDs) belong to the most important
representation types for Boolean functions. Although they allow
important operations such as satisfiability test and equality test to
be performed efficiently, their limitation lies in the fact, that they
may require exponential size for important functions. Bryant ... more >>>

We describe a new family of symmetric error-correcting codes with low-density parity-check matrices (LDPC).

Our codes can be described in two seemingly different ways. First, in relation to Reed-Muller codes: our codes are functions on a subset of $\mathbb{F}^n$ whose restrictions to a prescribed set of affine lines has low ... more >>>

We show that a mild derandomization assumption together with the
worst-case hardness of NP implies the average-case hardness of a
language in non-deterministic quasi-polynomial time. Previously such
connections were only known for high classes such as EXP and
PSPACE.

There has been a long line of research trying to explain ... more >>>

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... more >>>

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).
This basic construct underlies “hardness amplification” in cryptography, circuit complexity and
PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent
result by Dinur and ... more >>>

We present a new explicit construction of onesided bipartite lossless expanders of constant degree, with arbitrary constant ratio between the sizes of the two vertex sets. Our construction is simpler to state and analyze than the prior construction of Capalbo, Reingold, Vadhan, and Wigderson (2002).

We construct our ... more >>>

Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers $n$ and $d$ such that $d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree $\delta = o(d)$ that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size $n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... more >>>

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,
explicit extractors for $2$-interleaved sources on $\{ ... more >>>

We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic $O(n^\omega)$ time, where $\omega<3$; much work has gone into bringing $\omega$ closer to $2$. Since then, a ... more >>>

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>>

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only ... more >>>

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression ... more >>>

A q-query Locally Decodable Code (LDC) encodes an n-bit message
x as an N-bit codeword C(x), such that one can
probabilistically recover any bit x_i of the message
by querying only q bits of the codeword C(x), even after
some constant fraction of codeword bits has been corrupted.

We give ... more >>>

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log ... more >>>

In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):

1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ... more >>>

In unrestricted branching programs all variables may be tested
arbitrarily often on each path. But exponential lower bounds are only
known, if on each path the number of tests of each variable is bounded
(Borodin, Razborov and Smolensky (1993)). We examine branching programs
in which for each path the ... more >>>

For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For ... more >>>

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin [Yek] and Efremenko [Efr] and are the only known families of LDCs with a constant number of queries and sub-exponential encoding ... more >>>

In this paper, we obtain new size lower bounds for proofs in the
Polynomial Calculus (PC) proof system, in two different settings.

1. When the Boolean variables are encoded using $\pm 1$ (as opposed
to $0,1$): We establish a lifting theorem using an asymmetric gadget
$G$, showing ... more >>>

Communication complexity is a central model of computation introduced by Yao in 1979, where
two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed
function f with the least amount of communication. Recently people have revisited the question of the ... more >>>

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include:

(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is optimal up to a factor $O(\log^{2}n)$. The previous best lower bound was $\Omega(\sqrt{n})$ proved in ... more >>>

We prove two lower bounds on the Statistical Query (SQ) learning
model. The first lower bound is on weak-learning. We prove that for a
concept class of SQ-dimension $d$, a running time of
$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is
defined to be the maximum number ... more >>>

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... more >>>

An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... more >>>

We present new protocols for conditional disclosure of secrets (CDS),
where two parties want to disclose a secret to a third party if and
only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,
we present two protocols that achieve ... more >>>

The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst ... more >>>

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Using ideas from automata theory we design a new efficient
(deterministic) identity test for the \emph{noncommutative}
polynomial identity testing problem (first introduced and studied by
Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,
given as input a noncommutative
circuit $C(x_1,\cdots,x_n)$ computing a ... more >>>

It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}.
This paper contains several new results on its complexity.
First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated.
A randomized algorithm for MUL_{n-1,n} with k=O(log ... more >>>

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=\frac{2}{3}s(f)^2-\frac{1}{3}s(f)$.

We show two new direct product results in two different models of communication complexity. Our first result is in the model of one-way public-coin model. Let $f \subseteq X \times Y \times Z $ be a relation and $\epsilon >0$ be a constant. Let $R^{1,pub}_{\epsilon}(f)$ represent the communication complexity of ... more >>>

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.
(1) A polynomial-time,
$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ... more >>>

What's new in the world of derandomization? Questions about pseudorandomness and derandomization have been driving progress in complexity theory for many decades. In this survey we will describe new approaches to the $\mathcal{BPP}=\mathcal{P}$ conjecture from recent years, as well as new questions, algorithmic approaches, and ways of thinking. For example: ... more >>>

The maximum 2-satisfiability problem (MAX-2-SAT) is:
given a Boolean formula in $2$-CNF, find a truth
assignment that satisfies the maximum possible number
of its clauses. MAX-2-SAT is MAXSNP-complete.
Recently, this problem received much attention in the
contexts of approximation (polynomial-time) algorithms
... more >>>

$\mbox{ACC}_m$ circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of $\mbox{ACC}_m$ circuits of quasi-polynomial size and ... more >>>

A map $g:\{0,1\}^n\to\{0,1\}^m$ ($m>n$) is a hard proof complexity generator for a proof system $P$ iff for every string $b\in\{0,1\}^m\setminus Rng(g)$, formula $\tau_b(g)$ naturally expressing $b\not\in Rng(g)$ requires superpolynomial size $P$-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan--Wigderson generator. Razborov (Annals of Mathematics ... more >>>

We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation.

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22).

In ... more >>>

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called $BPP^0$, does not contain a complete problem. In other words, there is no randomized constant-cost problem $Q \in BPP^0$, such that all other problems $P \in BPP^0$ can be computed by a constant-cost deterministic protocol with ... more >>>

We revisit one original motivation for the study of no-signaling multi-prover
interactive proofs (NS-MIPs): specifically, that two spatially separated
provers are guaranteed to be no-signaling by the physical principle that
information cannot travel from one point to another faster than light.

We observe that with ... more >>>

We study the effect of noise on the $n$-party beeping model. In this model, in every round, each party may decide to either `beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers ... more >>>

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a
set $S \subseteq \F^n$, where $\F$ is a finite field, such that
any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be
efficiently interpolated from its values on $S$, even if an
adversary corrupts a constant fraction of the values. ... more >>>

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>

The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped ... more >>>

In the noisy population recovery problem of Dvir et al., the goal is to learn
an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$,
a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with
more >>>

Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric $f$-channels: In every round of the $f$-channel, each of its $n$ parties decides to either ... more >>>

In this paper, we study two questions related to
the problem of testing whether a function is close to a homomorphism.
For two finite groups $G,H$ (not necessarily Abelian),
an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,
say that $f$ is $\epsilon$-close to a homomorphism ... more >>>

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive ... more >>>

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model.
It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers.
We show that ... more >>>

We show that for several natural classes of ``structured'' matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime $p$ is as hard as computing the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

We investigate autoreducibility properties of complete sets for $\cNEXP$ under different polynomial reductions.
Specifically, we show under some polynomial reductions that there is are complete sets for
$\cNEXP$ that are not autoreducible. We obtain the following results:
- There is a $\reduction{p}{tt}$-complete set for $\cNEXP$ that is not $\reduction{p}{btt}$-autoreducible.
more >>>

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem.

This paper overcomes the barrier. We ... more >>>

We investigate the phenomenon of depth-reduction in commutative
and non-commutative arithmetic circuits. We prove that in the
commutative setting, uniform semi-unbounded arithmetic circuits of
logarithmic depth are as powerful as uniform arithmetic circuits of
polynomial degree; earlier proofs did not work in the ... more >>>

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-
alize algebraic branching programs (ABP). This model is called unambiguous because it captures the
polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-
morphic).
We ... more >>>

The semantics of decision problems are always essentially independent of the
underlying representation. Thus the space of input data (under appropriate
indexing) is closed
under action of the symmetrical group $S_n$ (for a specific data-size)
and the input-output relation is closed under the action of $S_n$.
more >>>

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits.

We strengthen the above lower bound to an average case one, by proving that for all constants c, ... more >>>

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete ... more >>>

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

Predictive complexity is a generalization of Kolmogorov complexity
which gives a lower bound to ability of any algorithm to predict
elements of a sequence of outcomes. A variety of types of loss
functions makes it interesting to study relations between corresponding
predictive complexities.

Non-linear inequalities between predictive complexity of ... more >>>

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

In multi-prover interactive proofs (MIPs), the verifier is usually non-adaptive. This stems from an implicit problem which we call “contamination” by the verifier. We make explicit the verifier contamination problem, and identify a solution by constructing a generalization of the MIP model. This new model quantifies non-locality as a new ... more >>>

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... more >>>

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to many elegant constructions and applications in cryptography. However, most works so far only ... more >>>

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>>

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a ... more >>>

We give an explicit construction of non-malleable codes with rate $1-o(1)$ for the tampering class of poly-size circuits. This rate is optimal, and improves upon the previous explicit construction of Ball, Dachman-Soled and Loss (CRYPTO 2022) which achieves a rate smaller than $\frac{1}{n}$. Our codes are based on the same ... more >>>

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>>

We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: ... more >>>

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami ... more >>>

Dodis and Wichs \cite{DW09} introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable ... more >>>

We construct non-malleable extractors with seed length $d = O(\log{n}+\log^{3}(1/\epsilon))$ for $n$-bit sources with min-entropy $k = \Omega(d)$, where $\epsilon$ is the error guarantee. In particular, the seed length is logarithmic in $n$ for $\epsilon> 2^{-(\log{n})^{1/3}}$. This improves upon existing constructions that either require super-logarithmic seed length even for constant ... more >>>

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function $nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either ... more >>>

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<ul>
<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>
<li>1-tt-reducibility and m-reducibility differ on NP.</li>
<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ... more >>>

Let a program p on input a output b. We are looking for a
shorter program p' having the same property (p'(a)=b). In
addition, we want p' to be simple conditional to p (this
means that the conditional Kolmogorov complexity K(p'|p) is
negligible). In the present paper, we prove that ... more >>>

We study the power of non-uniform attacks against one-way
functions and pseudorandom generators.

Fiat and Naor show that for every function
$f: [N]\to [N]$
there is an algorithm that inverts $f$ everywhere using
(ignoring lower order factors)
time, space and advice at most $N^{3/4}$.

We show that ... more >>>

We discuss some connections between polynomial time and non-uniform, small depth circuits. A connection is shown with simulating deterministic time in small space. The well known result of Hopcroft, Paul and Valiant showing that space is more powerful than time can be improved, by making an assumption about the connection ... more >>>

We may believe SAT does not have small Boolean circuits.
But is it possible that some language with small circuits
looks indistiguishable from SAT to every polynomial-time
bounded adversary? We rule out this possibility. More
precisely, assuming SAT does not have small circuits, we
show that ... more >>>

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ... more >>>

We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington’s Theorem. Barrington showed how to express a NC1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington’s product program ... more >>>

In this paper we explore the noncommutative analogues, $\mathrm{VP}_{nc}$ and
$\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some
striking connections to classical formal language theory. Our main
results are the following:

(1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for ... more >>>

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that $A$ is fixed. We obtain the following dichotomy: If $A/rad(A)$ is noncommutative, then computing the determinant over $A$ is hard. ``Hard'' here means $\#P$-hard over fields of characteristic $0$ and $ModP_p$-hard over ... more >>>

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>

We introduce the Nondeterministic Strong Exponential Time Hypothesis
(NSETH) as a natural extension of the Strong Exponential Time
Hypothesis (SETH). We show that both refuting and proving
NSETH would have interesting consequences.

In particular we show that disproving NSETH would ... more >>>

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice.
In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages?
Depending on the complexity of the ... more >>>

Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove ... more >>>

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known ... more >>>

This paper initiates the study of $k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A $k$-catalytic branching program computes $k$ boolean functions simultaneously on the same $n$-bit input. Each function has ... more >>>

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... more >>>

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due ... more >>>

We show that, for fixed dimension $n$, the approximation of
inner and outer $j$-radii of polytopes in ${\Re}^n$, endowed
with the Euclidean norm, is polynomial.

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the ... more >>>

In 1984, Leonid Levin has initiated a theory of average-case complexity.
We provide an exposition of the basic definitions suggested by Levin,
and discuss some of the considerations underlying these definitions.

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each ... more >>>

The thesis summarizes known results in the field of NP search problems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems.

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

Can NP-complete problems be solved efficiently in the physical universe?
I survey proposals including soap bubbles, protein folding, quantum
computing, quantum advice, quantum adiabatic algorithms,
quantum-mechanical nonlinearities, hidden variables, relativistic time
dilation, analog computing, Malament-Hogarth spacetimes, quantum
gravity, closed timelike curves, and "anthropic computing." The ... more >>>

The article investigates the relation between three well-known hypotheses.
1) Hunion: the union of disjoint complete sets for NP is complete for NP
2) Hopps: there exist optimal propositional proof systems
3) Hcpair: there exist complete disjoint NP-pairs

The following results are obtained:
a) The hypotheses are pairwise independent ... more >>>

We show that hard sets S for NP must have exponential density, i.e. |S_=n| &#8805; 2^{n^&#949;} for some &#949; > 0 and infinitely many n, unless coNP &#8838; NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n^1-&#949; queries.

In addition we study the instance ... more >>>

Mahaney's Theorem states that, assuming P $\neq$ NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of low information content," Theoret. Comp. Sci., ... more >>>

We show that the class of sets which can be polynomial
time truth table reduced to some $p$-superterse sets has
$p$-measure 0. Hence, no $P$-selective set is $\le_{tt}^p$-hard
for $E$. Also we give a partial affirmative answer to
the conjecture by Beigel, Kummer and ... more >>>

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

In this work, we prove NP-hardness of approximating meta-complexity with ... more >>>

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT'90, SICOMP'91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness ... more >>>

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>>

Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when ... more >>>

An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse ... more >>>

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NP. It is known that, with restricted amplitudes, NQP is
characterized in terms of the classical counting complexity class
C_{=}P. In this paper we prove that, with unrestricted amplitudes,
NQP indeed coincides with the ... more >>>

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ ... more >>>

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>