Stasys Jukna

A syntactic read-k times branching program has the restriction

that no variable occurs more than k times on any path (whether or not

consistent). We exhibit an explicit Boolean function f which cannot

be computed by nondeterministic syntactic read-k times branching programs

of size less than exp(\sqrt{n}}k^{-2k}), ...
more >>>

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Almost the same types of restricted branching programs (or

binary decision diagrams BDDs) are considered in complexity

theory and in applications like hardware verification. These

models are read-once branching programs (free BDDs) and certain

types of oblivious branching programs (ordered and indexed BDDs

with k layers). The complexity of ...
more >>>

Detlef Sieling

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

Vince Grolmusz

We examine the power of Boolean functions with low L_1 norms in several

settings. In large part of the recent literature, the degree of a polynomial

which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.

However, some functions ...
more >>>

Pascal Koiran

The main result of this paper is a Omega(n^{1/4}) lower bound

on the size of a sigmoidal circuit computing a specific AC^0_2 function.

This is the first lower bound for the computation model of sigmoidal

circuits with unbounded weights. We also give upper and lower bounds for

the ...
more >>>

Farid Ablayev, Marek Karpinski

We define the notion of a randomized branching program in

the natural way similar to the definition of a randomized

circuit. We exhibit an explicit function $f_{n}$ for which

we prove that:

1) $f_{n}$ can be computed by polynomial size randomized

...
more >>>

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

We extend the lower bounds on the depth of algebraic decision trees

to the case of {\em randomized} algebraic decision trees (with

two-sided error) for languages being finite unions of hyperplanes

and the intersections of halfspaces, solving a long standing open

problem. As an application, among ...
more >>>

Stasys Jukna

We prove a general combinatorial lower bound on the

size of monotone circuits. The argument is different from

Razborov's method of approximation, and is based on Sipser's

notion of `finite limit' and Haken's `counting bottlenecks' idea.

We then apply this criterion to the ...
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 >>>

Petr Savicky, Stanislav Zak

Branching programs (b.p.'s) or decision diagrams are a general

graph-based model of sequential computation. The b.p.'s of

polynomial size are a nonuniform counterpart of LOG. Lower bounds

for different kinds of restricted b.p.'s are intensively

investigated. An important restriction are so called $k$-b.p.'s,

where each computation reads each input ...
more >>>

Martin Dietzfelbinger

The fundamental assumption in the classical theory of

dissemination of information in interconnection networks

(gossiping and broadcasting) is that atomic pieces of information

are communicated. We show that, under suitable assumptions about

the way processors may communicate, computing an n-ary function

that has a "critical input" (e.g., ...
more >>>

Stasys Jukna

In a semantic resolution proof we operate with clauses only

but allow {\em arbitrary} rules of inference:

C_1 C_2 ... C_m

__________________

C

Consistency is the only requirement. We prove a very simple

exponential lower bound for the size ...
more >>>

Jan Krajicek

We introduce a notion of a "real game"

(a generalization of the Karchmer - Wigderson game),

and "real communication complexity",

and relate them to the size of monotone real formulas

and circuits. We give an exponential lower bound

for tree-like monotone protocols of small real

communication complexity ...
more >>>

Martin Sauerhoff

In this paper, we are concerned with randomized OBDDs and randomized

read-k-times branching programs. We present an example of a Boolean

function which has polynomial size randomized OBDDs with small,

one-sided error, but only non-deterministic read-once branching

programs of exponential size. Furthermore, we discuss a lower bound

technique for randomized ...
more >>>

Oded Goldreich

We consider the problem of estimating the average of a huge set of values.

That is,

given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,

we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$

upto an additive error of $\epsilon$.

We are allowed to employ a randomized algorithm which may ...
more >>>

Martin Sauerhoff

Randomized branching programs are a probabilistic model of computation

defined in analogy to the well-known probabilistic Turing machines.

In this paper, we present complexity theoretic results for randomized

read-once branching programs.

Our main result shows that nondeterminism can be more powerful than

randomness for read-once branching programs. We present a ...
more >>>

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Razborov~\cite{Razborov96} recently proved that polynomial

calculus proofs of the pigeonhole principle $PHP_n^m$ must have

degree at least $\ceiling{n/2}+1$ over any field. We present a

simplified proof of the same result. The main

idea of our proof is the same as in the original proof

of Razborov: we want to describe ...
more >>>

Bruno Codenotti, Pavel Pudlak, Giovanni Resta

We consider the conjecture stating that a matrix with rank

$o(n)$ and ones on the main diagonal must contain nonzero

entries on a $2\times 2$ submatrix with one entry on the main

diagonal. We show that a slightly stronger conjecture implies

that ...
more >>>

Stanislav Zak

Branching programs (b.p.s) or binary decision diagrams are a

general graph-based model of sequential computation. The b.p.s of

polynomial size are a nonuniform counterpart of LOG. Lower bounds

for different kinds of restricted b.p.s are intensively

investigated. The restrictions based on the number of tests of

more >>>

Jayram S. Thathachar

We obtain an exponential separation between consecutive

levels in the hierarchy of classes of functions computable by

polynomial-size syntactic read-$k$-times branching programs, for

{\em all\/} $k>0$, as conjectured by various

authors~\cite{weg87,ss93,pon95b}. For every $k$, we exhibit two

explicit functions that can be computed by linear-sized

read-$(\kpluso)$-times branching programs but ...
more >>>

Farid Ablayev, Marek Karpinski

We introduce a model of a {\em randomized branching program}

in a natural way similar to the definition of a randomized circuit.

We exhibit an explicit boolean function

$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:

1) $f_{n}$ can be computed by a polynomial size randomized

...
more >>>

Farid Ablayev, Marek Karpinski

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the

size of any randomized ordered read-once branching program

computing integer multiplication. Our proof depends on proving

a new lower bound on Yao's randomized one-way communication

complexity of certain boolean functions. It generalizes to some

other ...
more >>>

Martin Sauerhoff

We extend the tools for proving lower bounds for randomized branching

programs by presenting a new technique for the read-once case which is

applicable to a large class of functions. This technique fills the gap

between simple methods only applicable for OBDDs and the well-known

"rectangle technique" of Borodin, Razborov ...
more >>>

Paul Beame, Faith Fich

We obtain improved lower bounds for a class of static and dynamic

data structure problems that includes several problems of searching

sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent

striking improvements in searching algorithms given by Fredman and

Willard's ...
more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving

lower bounds on the size of branching programs (b.p.). The argument

is based on Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during various

stages of the computation. ...
more >>>

Marek Karpinski

We survey some upper and lower bounds established recently on

the sizes of randomized branching programs computing explicit

boolean functions. In particular, we display boolean

functions on which randomized read-once ordered branching

programs are exponentially more powerful than deterministic

or nondeterministic read-$k$-times branching programs for ...
more >>>

Stasys Jukna

We consider a general model of monotone circuits, which

we call d-local. In these circuits we allow as gates:

(i) arbitrary monotone Boolean functions whose minterms or

maxterms (or both) have length at most <i>d</i>, and

(ii) arbitrary real-valued non-decreasing functions on ...
more >>>

Detlef Sieling

For (1,+k)-branching programs and read-k-times branching

programs syntactic and nonsyntactic variants can be distinguished. The

nonsyntactic variants correspond in a natural way to sequential

computations with restrictions on reading the input while lower bound

proofs are easier or only known for the syntactic variants. In this

paper it is shown ...
more >>>

Farid Ablayev, Svetlana Ablayeva

The superposition (or composition) problem is a problem of

representation of a function $f$ by a superposition of "simpler" (in a

different meanings) set $\Omega$ of functions. In terms of circuits

theory this means a possibility of computing $f$ by a finite circuit

with 1 fan-out gates $\Omega$ of functions. ...
more >>>

Paul Beame, Michael Saks, Jayram S. Thathachar

We obtain the first non-trivial time-space tradeoff lower bound for

functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a

Boolean function f that requires exponential size to be computed by any

branching program of length cn, for some constant c>1. We also give the first

separation result between the ...
more >>>

Detlef Sieling

Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have

been suggested as a generalization of OBDDs for the representation and

manipulation of Boolean functions. Instead of variables as in the

case of OBDDs parities of variables may be tested at the nodes of an

LTOBDD. By this extension it is ...
more >>>

Marek Karpinski

We survey some of the recent results on the complexity of recognizing

n-dimensional linear arrangements and convex polyhedra by randomized

algebraic decision trees. We give also a number of concrete applications

of these results. In particular, we derive first nontrivial, in fact

quadratic, ...
more >>>

Farid Ablayev

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an

ordinary branching program with the following restrictions: (i)

along every consistent path at most $k$ variables are tested more

than once, (ii) for each node $v$ on all paths from the source to

$v$ the same set $X(v)\subseteq X$ of variables is ...
more >>>

Beate Bollig, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the

most common dynamic data structure or representation type

for Boolean functions. Among the many areas of application

are verification, model checking, and computer aided design.

For many functions it is easy to estimate the OBDD ...
more >>>

Piotr Berman, Moses Charikar, Marek Karpinski

We consider the problem of scheduling permanent jobs on related machines

in an on-line fashion. We design a new algorithm that achieves the

competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic

version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,

improving the previous competitive ratios ...
more >>>

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

We prove the first time-space lower bound tradeoffs for randomized

computation of decision problems. The bounds hold even in the

case that the computation is allowed to have arbitrary probability

of error on a small fraction of inputs. Our techniques are an

extension of those used by Ajtai in his ...
more >>>

Ran Raz, Amir Shpilka

We prove super-linear lower bounds for the number of edges

in constant depth circuits with $n$ inputs and up to $n$ outputs.

Our lower bounds are proved for all types of constant depth

circuits, e.g., constant depth arithmetic circuits, constant depth

threshold circuits ...
more >>>

A simple extension of standard neural network models is introduced that

provides a model for neural computations that involve both firing rates and

firing correlations. Such extension appears to be useful since it has been

shown that firing correlations play a significant computational role in

many biological neural systems. Standard ...
more >>>

In this paper the computational power of a new type of gate is studied:

winner-take-all gates. This work is motivated by the fact that the cost

of implementing a winner-take-all gate in analog VLSI is about the same

as that of implementing a threshold gate.

We show that ... more >>>

Lars Engebretsen

We show that the k-CSP problem over a finite Abelian group G

cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for

any constant epsilon>0, unless P=NP. This lower bound matches

well with the best known upper bound, |G|^{k-1}, of Serna,

Trevisan and Xhafa. The proof uses a combination of PCP

techniques---most notably a ...
more >>>

Martin Sauerhoff

One of the great challenges of complexity theory is the problem of

analyzing the dependence of the complexity of Boolean functions on the

resources nondeterminism and randomness. So far, this problem could be

solved only for very few models of computation. For so-called

partitioned binary decision diagrams, which are a ...
more >>>

Martin Sauerhoff

This paper deals with the number of monochromatic combinatorial

rectangles required to approximate a Boolean function on a constant

fraction of all inputs, where each rectangle may be defined with

respect to its own partition of the input variables. The main result

of the paper is that the number of ...
more >>>

Lars Engebretsen, Marek Karpinski

The general asymmetric (and metric) TSP is known to be approximable

only to within an O(log n) factor, and is also known to be

approximable within a constant factor as soon as the metric is

bounded. In this paper we study the asymmetric and symmetric TSP

problems with bounded metrics ...
more >>>

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

We give a polynomial time approximation scheme (PTAS) for dense

instances of the NEAREST CODEWORD problem.

Piotr Berman, Marek Karpinski

We consider the following optimization problem:

given a system of m linear equations in n variables over a certain field,

a feasible solution is any assignment of values to the variables, and the

minimized objective function is the number of equations that are not

satisfied. For ...
more >>>

Piotr Berman, Marek Karpinski

We consider bounded occurrence (degree) instances of a minimum

constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for

graphs. MIN-LIN2 is an optimization problem for a given system of linear

equations mod 2 to construct a solution that satisfies the minimum number

of them. E3-OCC-MIN-E3-LIN2 ...
more >>>

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

It is known that large fragments of the class of dense

Minimum Constraint Satisfaction (MIN-CSP) problems do not have

polynomial time approximation schemes (PTASs) contrary to their

Maximum Constraint Satisfaction analogs. In this paper we prove,

somewhat surprisingly, that the minimum satisfaction of dense

instances of kSAT-formulas, ...
more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving lower

bounds on the size of branching programs. The argument is based on

Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during the various

stages of computation. The uncertainty is measured by the average

more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

We extend the lower bound techniques of [Fortnow], to the

unbounded-error probabilistic model. A key step in the argument

is a generalization of Nepomnjascii's theorem from the Boolean

setting to the arithmetic setting. This generalization is made

possible, due to the recent discovery of logspace-uniform TC^0

more >>>

Marek Karpinski

We present some of the recent results on computational complexity

of approximating bounded degree combinatorial optimization problems. In

particular, we present the best up to now known explicit nonapproximability

bounds on the very small degree optimization problems which are of

particular importance on the intermediate stages ...
more >>>

Stasys Jukna, Georg Schnitger

We show that recognizing the $K_3$-freeness and $K_4$-freeness of

graphs is hard, respectively, for two-player nondeterministic

communication protocols with exponentially many partitions and for

nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to

Papadimitriou and Sipser, which says that for every ...
more >>>

Piotr Berman, Marek Karpinski

This paper studies the existence of efficient (small size)

amplifiers for proving explicit inaproximability results for bounded degree

and bounded occurrence combinatorial optimization problems, and gives

an explicit construction for such amplifiers. We use this construction

also later to improve the currently best known approximation lower bounds

more >>>

Amir Shpilka

We prove lower bounds on the number of product gates in bilinear

and quadratic circuits that

compute the product of two $n \times n$ matrices over finite fields.

In particular we obtain the following results:

1. We show that the number of product gates in any bilinear

(or quadratic) ...
more >>>

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

We study k-partition communication protocols, an extension

of the standard two-party best-partition model to k input partitions.

The main results are as follows.

1. A strong explicit hierarchy on the degree of

non-obliviousness is established by proving that,

using k+1 partitions instead of k may decrease

the communication complexity from ...
more >>>

Hubie Chen

Representations of boolean functions as polynomials (over rings) have

been used to establish lower bounds in complexity theory. Such

representations were used to great effect by Smolensky, who

established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)

by representing AC^0[MOD p] functions as low-degree multilinear

polynomials over ...
more >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

Branching programs are a well-established computation model

for Boolean functions, especially read-once branching programs

have been studied intensively. Exponential lower bounds for

deterministic and nondeterministic read-once branching programs

are known for a long time. On the other hand, the problem of

proving superpolynomial lower bounds ...
more >>>

Hubie Chen

The boolean circuit complexity classes

AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied

intensely. Other than NC^1, they are defined by constant-depth

circuits of polynomial size and unbounded fan-in over some set of

allowed gates. One reason for interest in these classes is that they

contain the ...
more >>>

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Philipp Woelfel

We present a new lower bound technique for two types of restricted

Branching Programs (BPs), namely for read-once BPs (BP1s) with

restricted amount of nondeterminism and for (1,+k)-BPs. For this

technique, we introduce the notion of (strictly) k-wise l-mixed

Boolean functions, which generalizes the concept of l-mixedness ...
more >>>

Ran Raz

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of

any arithmetic circuit for the product of two matrices,

over the real or complex numbers, as long as the circuit doesn't

use products with field elements of absolute value larger than 1

(where $m \times m$ is ...
more >>>

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

We prove upper and lower bounds on the power of quantum and stochastic

branching programs of bounded width. We show any NC^1 language can

be accepted exactly by a width-2 quantum branching program of

polynomial length, in contrast to the classical case where width 5 is

necessary unless \NC^1=\ACC. ...
more >>>

Beate Bollig

Branching programs are a well-established computation

model for boolean functions, especially read-once

branching programs (BP1s) have been studied intensively.

A very simple function $f$ in $n^2$ variables is

exhibited such that both the function $f$ and its negation

$\neg f$ can be computed by $\Sigma^3_p$-circuits,

the ...
more >>>

Iordanis Kerenidis, Ronald de Wolf

We prove exponential lower bounds on the length of 2-query

locally decodable codes. Goldreich et al. recently proved such bounds

for the special case of linear locally decodable codes.

Our proof shows that a 2-query locally decodable code can be decoded

with only 1 quantum query, and then ...
more >>>

Andrej Bogdanov, Luca Trevisan

We consider the problem of testing bipartiteness in the adjacency

matrix model. The best known algorithm, due to Alon and Krivelevich,

distinguishes between bipartite graphs and graphs that are

$\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$

queries. We show that this is optimal for non-adaptive algorithms,

up to the ...
more >>>

Scott Aaronson

We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place BQP outside ... more >>>

Piotr Berman, Marek Karpinski

We improve a number of approximation lower bounds for

bounded occurrence optimization problems like MAX-2SAT,

E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching.

Piotr Berman, Marek Karpinski, Alexander D. Scott

We study approximation hardness and satisfiability of bounded

occurrence uniform instances of SAT. Among other things, we prove

the inapproximability for SAT instances in which every clause has

exactly 3 literals and each variable occurs exactly 4 times,

and display an explicit ...
more >>>

Ziv Bar-Yossef

We present a novel technique, based on the Jensen-Shannon divergence

from information theory, to prove lower bounds on the query complexity

of sampling algorithms that approximate functions over arbitrary

domain and range. Unlike previous methods, our technique does not

use a reduction from a binary decision problem, but rather ...
more >>>

Wee, Hoeteck

A source is compressible if we can efficiently compute short

descriptions of strings in the support and efficiently

recover the strings from the descriptions. In this paper, we

present a technique for proving lower bounds on

compressibility in an oracle setting, which yields the

following results:

- We ...
more >>>

Ran Raz

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

Matthias Homeister

We prove the first lower bound for restricted read-once parity branching

programs with unlimited parity nondeterminism where for each input the

variables may be tested according to several orderings.

Proving a superpolynomial lower bound for read-once parity branching

programs is still a challenging open problem. The following variant ...
more >>>

Amit Chakrabarti, Oded Regev

We consider the approximate nearest neighbour search problem on the

Hamming Cube $\b^d$. We show that a randomised cell probe algorithm that

uses polynomial storage and word size $d^{O(1)}$ requires a worst case

query time of $\Omega(\log\log d/\log\log\log d)$. The approximation

factor may be as loose as $2^{\log^{1-\eta}d}$ for any ...
more >>>

Richard Beigel, Lance Fortnow, William Gasarch

We show that any 1-round 2-server Private Information

Retrieval Protocol where the answers are 1-bit long must ask questions

that are at least $n-2$ bits long, which is nearly equal to the known

$n-1$ upper bound. This improves upon the approximately $0.25n$ lower

bound of Kerenidis and de Wolf while ...
more >>>

Pascal Koiran

Let $\tau(k)$ be the minimum number of arithmetic operations

required to build the integer $k \in \N$ from the constant 1.

A sequence $x_k$ is said to be ``easy to compute'' if

there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$

for all $k \geq ...
more >>>

Ramamohan Paturi, Pavel Pudlak

In 1977 Valiant proposed a graph theoretical method for proving lower

bounds on algebraic circuits with gates computing linear functions.

He used this method to reduce the problem of proving

lower bounds on circuits with linear gates to to proving lower bounds

on the rigidity of a matrix, a ...
more >>>

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... more >>>

Ran Raz

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

Erez Petrank, Guy Rothblum

A large body of work studies the complexity of selecting the

$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.

the select$(j)$ operation). In this work, we study the

complexity of select in data that is partially structured by

an initial preprocessing stage and in a data structure ...
more >>>

Stasys Jukna

We consider the minimal number of AND and OR gates in monotone

circuits for quadratic boolean functions, i.e. disjunctions of

length-$2$ monomials. The single level conjecture claims that

monotone single level circuits, i.e. circuits which have only one

level of AND gates, for quadratic functions ...
more >>>

Leonid Gurvits

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables .

Assume that this polynomial satisfies the property : \\

$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$ . \\

We prove that ... more >>>

Anna Gal, Michal Koucky, Pierre McKenzie

In this paper we propose the study of a new model of restricted

branching programs which we call incremental branching programs.

This is in line with the program proposed by Cook in 1974 as an

approach for separating the class of problems solvable in logarithmic

space from problems solvable ...
more >>>

Ran Raz, Amir Shpilka, Amir Yehudayoff

We construct an explicit polynomial $f(x_1,...,x_n)$, with

coefficients in ${0,1}$, such that the size of any syntactically

multilinear arithmetic circuit computing $f$ is at least

$\Omega( n^{4/3} / log^2(n) )$. The lower bound holds over any field.

Luis Rademacher, Santosh Vempala

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume ... more >>>

Nathan Segerlind

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

Ryan Williams

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

Beate Bollig, Niko Range, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the most common

dynamic data structure or representation type for Boolean functions.

Among the many areas of application are verification, model checking,

computer aided design, relational algebra, and symbolic graph algorithms.

Although many even exponential lower bounds on the OBDD size of Boolean ...
more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

Ran Raz, Amir Yehudayoff

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

Shachar Lovett

Linearity tests are randomized algorithms which have oracle access to the truth table of some function $f$,

which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the ...
more >>>

Dieter van Melkebeek

Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by ... more >>>

Beate Bollig

Branching programs are computation models

measuring the space of (Turing machine) computations.

Read-once branching programs (BP1s) are the

most general model where each graph-theoretical path is the computation

path for some input. Exponential lower bounds on the size of read-once

branching programs are known since a long time. Nevertheless, there ...
more >>>

Zeev Dvir, Amir Shpilka, Amir Yehudayoff

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists ... more >>>

Nitin Saxena

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... more >>>

Ran Raz

A basic fact in linear algebra is that the image of the curve

$f(x)=(x^1,x^2,x^3,...,x^m)$, say over $C$, is not contained in any

$m-1$ dimensional affine subspace of $C^m$. In other words, the image

of $f$ is not contained in the image of any polynomial-mapping

$G:C^{m-1} ---> C^m$ ...
more >>>

Ran Raz, Amir Yehudayoff

We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth $d$ ... more >>>

Paul Beame, Trinh Huynh

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

Eric Allender, Michal Koucky

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

Beate Bollig

Integer multiplication as one of the basic arithmetic functions has been

in the focus of several complexity theoretical investigations.

Ordered binary decision diagrams (OBDDs) are one of the most common

dynamic data structures for boolean functions.

Among the many areas of application are verification, model checking,

computer-aided design, relational algebra, ...
more >>>

Alexander A. Sherstov

Representations of Boolean functions by real polynomials

play an important role in complexity theory. Typically,

one is interested in the least degree of a polynomial

p(x_1,...,x_n) that approximates or sign-represents

a given Boolean function f(x_1,...,x_n). This article

surveys a new and growing body of work in communication

complexity that centers ...
more >>>

Paul Beame, Trinh Huynh

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

Manindra Agrawal, V Vinay

We show that proving exponential lower bounds on depth four arithmetic

circuits imply exponential lower bounds for unrestricted depth arithmetic

circuits. In other words, for exponential sized circuits additional depth

beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

Paul Beame, Trinh Huynh

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

Atri Rudra

It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ ... more >>>

Joshua Brody, Amit Chakrabarti

The Gap-Hamming-Distance problem arose in the context of proving space

lower bounds for a number of key problems in the data stream model. In

this problem, Alice and Bob have to decide whether the Hamming distance

between their $n$-bit input strings is large (i.e., at least $n/2 +

\sqrt n$) ...
more >>>

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

Khrapchenko's classical lower bound $n^2$ on the formula size of the

parity function~$f$ can be interpreted as designing a suitable

measure of subrectangles of the combinatorial rectangle

$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we

arrived at the concept of \emph{convex measures}. We prove the

more >>>

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

Harry Buhrman, Lance Fortnow, Rahul Santhanam

We show several unconditional lower bounds for exponential time classes

against polynomial time classes with advice, including:

\begin{enumerate}

\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$

\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$

\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$

\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.

1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ...
more >>>

Nitin Saxena

Polynomial identity testing (PIT) is the problem of checking whether a given

arithmetic circuit is the zero circuit. PIT ranks as one of the most important

open problems in the intersection of algebra and computational complexity. In the last

few years, there has been an impressive progress on this ...
more >>>

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

The rigidity of a matrix A for target rank r is the minimum number of entries

of A that must be changed to ensure that the rank of the altered matrix is at

most r. Since its introduction by Valiant (1977), rigidity and similar

rank-robustness functions of matrices have found ...
more >>>

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes

whose duals have (superlinearly) {\em many} small weight ...
more >>>

Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor

This paper makes three main contributions to the theory of communication complexity and stream computation. First, we present new bounds on the information complexity of AUGMENTED-INDEX. In contrast to analogous results for INDEX by Jain, Radhakrishnan and Sen [J. ACM, 2009], we have to overcome the significant technical challenge that ... more >>>

Iddo Tzameret

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege--yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analogue of Frege proofs, different from that given in Buss ... more >>>

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum ... more >>>

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>

Boris Alexeev, Michael Forbes, Jacob Tsimerman

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). ... more >>>

Evgeny Demenkov, Alexander Kulikov

A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main ... more >>>

Anna Gal, Andrew Mills

Locally decodable codes

are error correcting codes with the extra property that, in order

to retrieve the correct value of just one position of the input with

high probability, it is

sufficient to read a small number of

positions of the corresponding,

possibly corrupted ...
more >>>

Sam Buss, Ryan Williams

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is ... more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models. We aim to understand whether ... more >>>

Guy Moshkovitz

In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of $m$-edge regular hypergraphs. Suppose they are ``indistinguishable'' with respect to hypergraphs with $m-t$ edges, in the sense that every such hypergraph has ... more >>>

Venkatesan Guruswami, Srivatsan Narayanan

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... more >>>

Chris Beck, Russell Impagliazzo, Shachar Lovett

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That ... more >>>

Rahul Santhanam, Ryan Williams

We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts:

1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is ``medium uniform'' if it can be generated by an algorithmic process that is somewhat complex ... more >>>

Ilan Komargodski, Ran Raz

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same ... more >>>

Charanjit Jutla, Vijay Kumar, Atri Rudra

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems ... more >>>

Kfir Barhum, Thomas Holenstein

We present a new framework for proving fully black-box

separations and lower bounds. We prove a general theorem that facilitates

the proofs of fully black-box lower bounds from a one-way function (OWF).

Loosely speaking, our theorem says that in order to prove that a fully black-box

construction does ...
more >>>

Paul Beame, Raphael Clifford, Widad Machmouchi

We consider time-space tradeoffs for exactly computing frequency

moments and order statistics over sliding windows.

Given an input of length $2n-1$, the task is to output the function of

each window of length $n$, giving $n$ outputs in total.

Computations over sliding windows are related to direct sum problems

except ...
more >>>

Siu Man Chan, Aaron Potechin

We prove tight size bounds on monotone switching networks for the NP-complete problem of

$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for

the P-complete problem of generation. This gives alternative proofs of the separations of m-NC

from m-P and of m-NC$^i$ from ...
more >>>

Kristoffer Arnsfelt Hansen, Vladimir Podolskii

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We ...
more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove

super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :

$\bullet$ As ... more >>>

Siu Man Chan

The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>

David Gamarnik, Madhu Sudan

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>

Ilan Komargodski, Ran Raz, Avishay Tal

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the ``expected ... more >>>

Mrinal Kumar, Shubhangi Saraf

We study the class of homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuits, which are depth 4 homogenous circuits with top fanin bounded by $r$. We show that any homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuit computing the permanent of an $n\times n$ matrix must have size at least $\exp\left(n^{\Omega(1/r)}\right)$.

In a recent result, Gupta, Kamath, Kayal and ... more >>>

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... more >>>

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>

Gregory Valiant, Paul Valiant

We consider the problem of verifying the identity of a distribution: Given the description of a distribution over a discrete support $p=(p_1,p_2,\ldots,p_n)$, how many samples (independent draws) must one obtain from an unknown distribution, $q$, to distinguish, with high probability, the case that $p=q$ from the case that the total ... more >>>

Moritz Müller, Stefan Szeider

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>>

Emanuele Viola

We draw two incomplete, biased maps of challenges in

computational complexity lower bounds. Our aim is to put

these challenges in perspective, and to present some

connections which do not seem widely known.

Paul Beame, Raphael Clifford, Widad Machmouchi

We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time $T$ and space $S$ ... more >>>

Mrinal Kumar, Shubhangi Saraf

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of {\it depth reduction} developed in the works of Agrawal-Vinay [AV08], Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partial derivative complexity measure ... more >>>

Bin Fu

We show that

derandomizing polynomial identity testing over an arbitrary finite

field implies that NEXP does not have polynomial size boolean

circuits. In other words, for any finite field F(q) of size q,

$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where

$PIT_q$ is the polynomial identity testing problem over F(q), and

NSUBEXP is ...
more >>>

Nikolay Vereshchagin

The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$, and they want to compute or approximate

more >>>

Mrinal Kumar, Shubhangi Saraf

In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree $n$ in $n^2$ variables such that any homogeneous depth 4 arithmetic circuit computing it must have size $n^{\Omega(\log \log n)}$.

Our results extend ... more >>>

Fu Li, Iddo Tzameret

Motivated by the fundamental lower bounds questions in proof complexity, we investigate the complexity of generating identities of matrix rings, and related problems. Specifically, for a field $\mathbb{F}$ let $A$ be a non-commutative (associative) $\mathbb{F}$-algebra (e.g., the algebra Mat$_d(\mathbb{F})\;$ of $d\times d$ matrices over $\mathbb{F}$). We say that a non-commutative ... more >>>

Olaf Beyersdorff, Leroy Chew

Circumscription is one of the main formalisms for non-monotonic reasoning. It uses reasoning with minimal models, the key idea being that minimal models have as few exceptions as possible. In this contribution we provide the first comprehensive proof-complexity analysis of different proof systems for propositional circumscription. In particular, we investigate ... more >>>

Mrinal Kumar, Shubhangi Saraf

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in $VP$. Our results hold for the {\it Iterated Matrix Multiplication} polynomial - in particular we show that any homogeneous depth 4 circuit computing the $(1,1)$ entry in the product of $n$ ... more >>>

Joshua Grochow, Toniann Pitassi

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

Ilya Volkovich

We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class $\mathcal{C}$ has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and ... more >>>

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

Stasys Jukna

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>

Shachar Lovett

Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Andris Ambainis, Yuval Filmus, Francois Le Gall

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.3729})$. These algorithms are obtained by analyzing higher ... more >>>

Jayadev Acharya, Clement Canonne, Gautam Kamath

A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain.

In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., ...
more >>>

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>>

Himanshu Tyagi, Shaileshh Venkatakrishnan , Pramod Viswanath, Shun Watanabe

A simulation of an interactive protocol entails the use of an interactive communication to produce the output of the protocol to within a fixed statistical distance $\epsilon$. Recent works in the TCS community have propagated that the information complexity of the protocol plays a central role in characterizing the minimum ... more >>>

Mrinal Kumar, Ramprasad Saptharishi

In this paper, we show exponential lower bounds for the class of homogeneous depth-$5$ circuits over all small finite fields. More formally, we show that there is an explicit family $\{P_d : d \in N\}$ of polynomials in $VNP$, where $P_d$ is of degree $d$ in $n = d^{O(1)}$ variables, ... more >>>

Amit Chakrabarti, Tony Wirth

Set cover, over a universe of size $n$, may be modelled as a

data-streaming problem, where the $m$ sets that comprise the instance

are to be read one by one. A semi-streaming algorithm is allowed only

$O(n \text{ poly}\{\log n, \log m\})$ space to process this ...
more >>>

Ilya Volkovich

An \emph{arithmetic circuit} is a directed acyclic graph in which the operations are $\{+,\times\}$.

In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems.

In particular, we show that:

\begin{enumerate}

\item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds.

Xi Chen, Igor Carboni Oliveira, Rocco Servedio

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>

Stasys Jukna, Georg Schnitger

We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum ... more >>>

Olaf Beyersdorff, Ilario Bonacina, Leroy Chew

A general and long-standing belief in the proof complexity community asserts that there is a close connection between progress in lower bounds for Boolean circuits and progress in proof size lower bounds for strong propositional proof systems. Although there are famous examples where a transfer from ideas and techniques from ... more >>>

Fu Li, Iddo Tzameret, Zhengyu Wang

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

The groundbreaking paper `Short proofs are narrow - resolution made simple' by Ben-Sasson and Wigderson (J. ACM 2001) introduces what is today arguably the main technique to obtain resolution lower bounds: to show a lower bound for the width of proofs. Another important measure for resolution is space, and in ... more >>>

Neeraj Kayal, Vineet Nair, Chandan Saha

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:

1. There exists an explicit $n$-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) ... more >>>

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n-o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n-o(n)$ bound of Norbert Blum (1984). The proof is based on the gate ... more >>>

Alexander Golovnev, Alexander Kulikov

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An $(n,k,s)$-quadratic disperser is a function on $n$ variables that is not constant on any subset of $\mathbb{F}_2^n$ of size at least $s$ ... more >>>

Joshua Grochow

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

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$ (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

Mrinal Kumar, Shubhangi Saraf

In recent years there has been a flurry of activity proving lower bounds for

homogeneous depth-4 arithmetic circuits [GKKS13, FLMS14, KLSS14, KS14c], which has brought us very close to statements that are known to imply VP $\neq$ VNP. It is a big question to go beyond homogeneity, and in ...
more >>>

Olaf Beyersdorff, Leroy Chew, Mikolas Janota

We investigate two QBF resolution systems that use extension variables: weak extended Q-resolution, where the extension variables are quantified at the innermost level, and extended Q-resolution, where the extension variables can be placed inside the quantifier prefix. These systems have been considered previously by Jussila et al. '07 who ... more >>>

Olaf Beyersdorff, Ján Pich

Recently Beyersdorff, Bonacina, and Chew (ITCS'16) introduced a natural class of Frege systems for quantified Boolean formulas (QBF) and showed strong lower bounds for restricted versions of these systems. Here we provide a comprehensive analysis of the new extended Frege system from Beyersdorff et al., denoted EF+$\forall$red, which is a ... more >>>

Ran Raz

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of ... more >>>

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>>

Venkatesan Guruswami, Jaikumar Radhakrishnan

Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>

Johan Håstad

We extend the recent hierarchy results of Rossman, Servedio and

Tan \cite{rst15} to any $d \leq \frac {c \log n}{\log {\log n}}$

for an explicit constant $c$.

To be more precise, we prove that for any such $d$ there is a function

$F_d$ that is computable by a read-once formula ...
more >>>

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P \in F[x_1, x_2, \ldots, x_n]$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to {syntactically} computing $P$, when $C \equiv P$ as formal polynomials. In this ... more >>>

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.

This yields a nearly tight ...
more >>>

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

Mika Göös, Rahul Jain, Thomas Watson

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 1992), who showed that proving lower bounds for $pd(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$. Despite several attempts (Pudlak, ... more >>>

Guillaume Lagarde, Guillaume Malod

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

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ...
more >>>

Nathanael Fijalkow

The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of states required to solve a given problem using an online algorithm,

represented by a machine which scans the input exactly once from left to right.

In this paper, we study alternating machines as introduced by ...
more >>>

Andrej Bogdanov, Siyao Guo, Ilan Komargodski

We prove that for every $n$ and $1 < t < n$ any $t$-out-of-$n$ threshold secret sharing scheme for one-bit secrets requires share size $\log(t + 1)$. Our bound is tight when $t = n - 1$ and $n$ is a prime power. In 1990 Kilian and Nisan proved ... more >>>

Mrinal Kumar, Ramprasad Saptharishi

In this paper, we show that there is a family of polynomials $\{P_n\}$, where $P_n$ is a polynomial in $n$ variables of degree at most $d = O(\log^2 n)$, such that

1. $P_n$ can be computed by linear sized homogeneous depth-$5$ circuits.

2. $P_n$ can be computed by ... more >>>

Amir Yehudayoff

We prove an essentially sharp $\tilde\Omega(n/k)$ lower bound on the $k$-round distributional complexity of the $k$-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson's $\tilde \Omega(n/k^2)$ lower bound. A key part of the proof is using triangular discrimination instead ... more >>>

Pavel Pudlak, Neil Thapen

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the ... more >>>

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

Badih Ghazi, Madhu Sudan

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>>

Dmitry Itsykson, Alexander Knop

Itsykson and Sokolov in 2014 introduced the class of DPLL($\oplus$) algorithms that solve Boolean satisfiability problem using the splitting by linear combinations of variables modulo 2. This class extends the class of DPLL algorithms that split by variables. DPLL($\oplus$) algorithms solve in polynomial time systems of linear equations modulo two ... more >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior ... more >>>

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show ... more >>>

Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin

In recent years the explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. An $(n,r,h,a,q)$-LRC is a $q$-ary code, where encoding is as a ... more >>>

Cody Murray, Ryan Williams

We prove that if every problem in $NP$ has $n^k$-size circuits for a fixed constant $k$, then for every $NP$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded with a circuit ... more >>>

Stasys Jukna, Hannes Seiwert

Many dynamic programming algorithms are ``pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm ... more >>>

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

Amit Levi, Erik Waingarten

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$-nodes graphs using rejection sampling queries requires complexity $\widetilde{\Omega}(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions ... more >>>

Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan

For quantified Boolean formulas (QBF) there are two main different approaches to solving: QCDCL and expansion solving. In this paper we compare the underlying proof systems and show that expansion systems admit strictly shorter proofs than CDCL systems for formulas of bounded quantifier complexity, thus pointing towards potential advantages of ... more >>>

Stasys Jukna, Hannes Seiwert

We develop general lower bound arguments for approximating tropical

(min,+) and (max,+) circuits, and use them to prove the

first non-trivial, even super-polynomial, lower bounds on the size

of such circuits approximating some explicit optimization

problems. In particular, these bounds show that the approximation

powers of pure dynamic programming algorithms ...
more >>>

Igor Carboni Oliveira, Rahul Santhanam

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include:

1. Let MCSP$[s]$ be the decision problem whose YES instances are ... more >>>

Stasys Jukna, Andrzej Lingas

We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the ``amount of negation'' in such circuits, we introduce the concept of their ``negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely ... more >>>

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. Our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish $(xy)z$ from $x(yz)$.

Our first and main conceptual result is a ... more >>>

Jayadev Acharya, Clement Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi

We study goodness-of-fit of discrete distributions in the distributed setting, where samples are divided between multiple users who can only release a limited amount of information about their samples due to various information constraints. Recently, a subset of the authors showed that having access to a common random seed (i.e., ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, ... more >>>

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).

more >>>Anant Dhayal, Russell Impagliazzo

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our ... more >>>

Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the ... more >>>

Suryajith Chillara

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of $r$ (referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>>

Stasys Jukna

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

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>