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

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 processors P_1,...,P_{k-1} ... more >>>

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 this problem requires Omega(k) steps on an ... more >>>

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 of this problem, as well ... more >>>

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

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

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 can ... more >>>

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 \oplus- (or \vee-)node with a fan-out ... more >>>

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

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

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

We 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 an approximation ... more >>>

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

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

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 a canonical finite graph, ... more >>>

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following: (I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

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

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

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

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

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

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 we can make ... more >>>

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

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

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