R. Beigel, W. Hurwood, N. Kahale

We consider the fault diagnosis problem: how to use parallel testing

rounds to identify which processors in a set are faulty. We prove

that 4 rounds suffice when 3% or less of the processors are faulty,

and 4 rounds are necessary when any nontrivial constant fraction of

the processors are ...
more >>>

Amos Beimel, Anna Gal, Michael S. Paterson

The model of span programs is a linear algebraic model of

computation. Lower bounds for span programs imply lower bounds for

contact schemes, symmetric branching programs and for formula size.

Monotone span programs correspond also to linear secret-sharing schemes.

We present a new technique for proving lower bounds for ...
more >>>

Martin Dietzfelbinger

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,

connected by k links to form a linear array, compute a function f(x,y), for

inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and

y is only known to P_k; the intermediate ...
more >>>

Noam Nisan, Ziv Bar-Yossef

We consider the well known problem of determining the k'th

vertex reached by chasing pointers in a directed graph of

out-degree 1. The famous "pointer doubling" technique

provides an O(log k) parallel time algorithm on a

Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ...
more >>>

Valentin E. Brimkov, Stefan S. Dantchev

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)

$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework

of the Blum-Shub-Smale real number computational model \cite{BSS}.

We obtain a new lower bound

$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time

complexity ...
more >>>

Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

We prove an exponential lower bound for tree-like Cutting Planes

refutations of a set of clauses which has polynomial size resolution

refutations. This implies an exponential separation between tree-like

and dag-like proofs for both Cutting Planes and resolution; in both

cases only superpolynomial separations were known before.

In order to ...
more >>>

Miklos Ajtai

Our computational model is a random access machine with $n$

read only input registers each containing $ c \log n$ bits of

information and a read and write memory. We measure the time by the

number of accesses to the input registers. We show that for all $k$

there is ...
more >>>

Tobias Polzin, Siavash Vahdati Daneshmand

We study several old and new algorithms for computing lower

and upper bounds for the Steiner problem in networks using dual-ascent

and primal-dual strategies. These strategies have been proven to be

very useful for the algorithmic treatment of the Steiner problem. We

show that none of the known algorithms ...
more >>>

Petr Savicky, Detlef Sieling

Restricted branching programs are considered in complexity theory in

order to study the space complexity of sequential computations and

in applications as a data structure for Boolean functions. In this

paper (\oplus,k)-branching programs and (\vee,k)-branching

programs are considered, i.e., branching programs starting with a

...
more >>>

Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

This paper gives two distinct proofs of an exponential separation

between regular resolution and unrestricted resolution.

The previous best known separation between these systems was

quasi-polynomial.

Elizaveta Okol'nishnikova

The method of obtaining lower bounds on the complexity

of Boolean functions for nondeterministic branching programs

is proposed.

A nonlinear lower bound on the complexity of characteristic

functions of Reed--Muller codes for nondeterministic

branching programs is obtained.

Ke Yang

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

Avrim Blum, Ke Yang

We introduce a ``Statistical Query Sampling'' model, in which

the goal of an algorithm is to produce an element in a hidden set

$S\subseteq\bit^n$ with reasonable probability. The algorithm

gains information about $S$ through oracle calls (statistical

queries), where the algorithm submits a query function $g(\cdot)$

and receives ...
more >>>

Emanuele Viola

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

Jakob Nordström

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

Hermann Gruber, Markus Holzer

We investigate the following lower bound methods for regular

languages: The fooling set technique, the extended fooling set

technique, and the biclique edge cover technique. It is shown that

the maximal attainable lower bound for each of the above mentioned

techniques can be algorithmically deduced from ...
more >>>

Emanuele Viola

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

Emanuele Viola, Avi Wigderson

In this paper we study the one-way multi-party communication model,

in which every party speaks exactly once in its turn. For every

fixed $k$, we prove a tight lower bound of

$\Omega{n^{1/(k-1)}}$ on the probabilistic communication

complexity of pointer jumping in a $k$-layered tree, where the

pointers of the $i$-th ...
more >>>

Ronen Shaltiel, Emanuele Viola

Hardness amplification is the fundamental task of

converting a $\delta$-hard function $f : {0,1}^n ->

{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,

where $f$ is $\gamma$-hard if small circuits fail to

compute $f$ on at least a $\gamma$ fraction of the

inputs. Typically, $\eps,\delta$ are small (and

$\delta=2^{-k}$ captures the case ...
more >>>

Jakob Nordström, Johan Hastad

Most state-of-the-art satisfiability algorithms today are variants of

the DPLL procedure augmented with clause learning. The main bottleneck

for such algorithms, other than the obvious one of time, is the amount

of memory used. In the field of proof complexity, the resources of

time and memory correspond to the length ...
more >>>

Dmitriy Cherukhin

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

Ryan Williams

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

Chris Calabro

One way to quantify how dense a multidag is in long paths is to find

the largest n, m such that whichever ≤ n edges are removed, there is still

a path from an original input to an original output with ≥ m edges

- the larger ...
more >>>

Emanuele Viola

We prove lower bounds on the redundancy necessary to

represent a set $S$ of objects using a number of bits

close to the information-theoretic minimum $\log_2 |S|$,

while answering various queries by probing few bits. Our

main results are:

\begin{itemize}

\item To represent $n$ ternary values $t \in

\zot^n$ in ...
more >>>

Eli Ben-Sasson, Jakob Nordström

For current state-of-the-art satisfiability algorithms based on the

DPLL procedure and clause learning, the two main bottlenecks are the

amounts of time and memory used. Understanding time and memory

consumption, and how they are related to one another, is therefore a

question of considerable practical importance. In the field of ...
more >>>

Emanuele Viola, Emanuele Viola

We prove that to store n bits x so that each

prefix-sum query Sum(i) := sum_{k < i} x_k can be answered

by non-adaptively probing q cells of log n bits, one needs

memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +

n/log^{Omega(q)} ...
more >>>

Shachar Lovett, Ely Porat

An approximate membership data structure is a randomized data

structure for representing a set which supports membership

queries. It allows for a small false positive error rate but has

no false negative errors. Such data structures were first

introduced by Bloom in the 1970's, and have since had numerous

applications, ...
more >>>

Emanuele Viola

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, ... more >>>

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

Eric Miles, Emanuele Viola

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous

constructions. In particular, we ...
more >>>

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code

$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,

using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

Emanuele Viola

We obtain the first deterministic randomness extractors

for $n$-bit sources with min-entropy $\ge n^{1-\alpha}$

generated (or sampled) by single-tape Turing machines

running in time $n^{2-16 \alpha}$, for all sufficiently

small $\alpha > 0$. We also show that such machines

cannot sample a uniform $n$-bit input to the Inner

Product function ...
more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>>

Loïck Magnin, Jérémie Roland

The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending ... more >>>

Dmitry Itsykson, Dmitry Sokolov

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>>

Iordanis Kerenidis, Mathieu Laurière, David Xiao

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

Miklos Ajtai

For each natural number $d$ we consider a finite structure ${\bf M}_{d}$ whose universe is the set of all $0,1$-sequence of length $n=2^{d}$, each representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace$ in binary form. The operations included in the structure are the four constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

Nitin Saxena

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.

more >>>Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas. That is, we give

an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with $0, 1$-coefficients such that

for any representation of ...
more >>>

Neeraj Kayal, Chandan Saha

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>

Albert Atserias, Massimo Lauria, Jakob Nordström

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

Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah

We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives the first successful transfer of one of the lower bound techniques for classical proof systems to QBF ... more >>>

Massimo Lauria, Jakob Nordström

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^{Omega(d)} for values of d = d(n) from constant all the way up to n^{delta} for some universal constant delta. This shows that ... more >>>

Mladen Mikša, Jakob Nordström

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov '03] established that if the clause-variable incidence graph of a CNF formula F is a good ... more >>>

Michal Moshkovitz, Dana Moshkovitz

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

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

Nader Bshouty

We prove that to estimate within a constant factor the number of defective items in a non-adaptive group testing algorithm we need at least $\tilde\Omega((\log n)(\log(1/\delta)))$ tests. This solves the open problem posed by Damaschke and Sheikh Muhammad.

more >>>Venkatesan Guruswami, Andrii Riazanov

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... more >>>

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where $n$ parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>>