ECCC - Reports tagged with lower bounds

Electronic Colloquium on Computational Complexity

REPORTS > KEYWORD > LOWER BOUNDS:

Reports tagged with lower bounds:

TR94-026 | 12th December 1994
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

On the Power of Different Types of Restricted Branching Programs

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

TR95-002 | 1st January 1995
Detlef Sieling

New Lower Bounds and Hierarchy Results for Restricted Branching Programs

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

TR95-046 | 4th August 1995
Vince Grolmusz

On the Power of Circuits with Gates of Low L_1 Norms

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

TR95-051 | 16th October 1995
Pascal Koiran

VC Dimension in Circuit Complexity

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

TR95-054 | 24th November 1995
Farid Ablayev, Marek Karpinski

On the Power of Randomized Branching Programs

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 read-once ordered branching program with a small one-sided error; ... more >>>

TR95-063 | 19th December 1995
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

A Lower Bound for Randomized Algebraic Decision Trees

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 other things, we derive, ... more >>>

TR96-026 | 25th March 1996
Stasys Jukna

Finite Limits and Monotone Computations

Revisions: 1 , Comments: 1

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 CLIQUE function on $n$ variables and obtain ... more >>>

TR96-031 | 30th April 1996

Networks of Spiking Neurons: The Third Generation of Neural Network Models

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 computationally more powerful than these other neural network ... more >>>

TR96-050 | 23rd September 1996
Petr Savicky, Stanislav Zak

A hierarchy for (1,+k)-branching programs with respect to k

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

TR96-052 | 2nd October 1996
Martin Dietzfelbinger

Gossiping and Broadcasting versus Computing Functions in Networks

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., the OR of ... more >>>

TR97-007 | 21st February 1997
Stasys Jukna

Exponential Lower Bounds for Semantic Resolution

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 of bounded fanin semantic resolution proofs of a general {\em Hitting ... more >>>

TR97-015 | 21st April 1997
Jan Krajicek

Interpolation by a game

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 solving the monotone ... more >>>

TR97-019 | 5th May 1997
Martin Sauerhoff

A Lower Bound for Randomized Read-k-Times Branching Programs

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

TR97-030 | 25th August 1997
Martin Sauerhoff

On Nondeterminism versus Randomness for Read-Once Branching Programs

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

TR97-042 | 22nd September 1997
Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

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

TR97-043 | 25th September 1997
Bruno Codenotti, Pavel Pudlak, Giovanni Resta

Some structural properties of low rank matrices related to computational complexity

Revisions: 1 , Comments: 1

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 an explicit linear transformation cannot be computed by ... more >>>

TR97-050 | 27th October 1997
Stanislav Zak

A subexponential lower bound for branching programs restricted with regard to some semantic aspects

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 variables during any computation ... more >>>

TR98-002 | 8th January 1998
Jayram S. Thathachar

On Separating the Read-k-Times Branching Program Hierarchy

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

TR98-004 | 13th January 1998
Farid Ablayev, Marek Karpinski

On the Power of Randomized Ordered Branching Programs

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 ordered read-once branching program with a ... more >>>

TR98-011 | 29th January 1998
Farid Ablayev, Marek Karpinski

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

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 common models of randomized branching ... more >>>

TR98-018 | 27th March 1998
Martin Sauerhoff

Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Comments: 1

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

TR98-028 | 28th May 1998
Paul Beame, Faith Fich

On Searching Sorted Lists: A Near-Optimal Lower Bound

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 fusion trees and ... more >>>

TR98-030 | 9th June 1998
Stasys Jukna, Stanislav Zak

On Branching Programs With Bounded Uncertainty

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. We first demonstrate the approach for read-once ... more >>>

TR98-041 | 27th July 1998
Stasys Jukna

Combinatorics of Monotone Computations

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 d, and (ii) arbitrary real-valued non-decreasing functions on at most d variables. Our main result is ... more >>>

TR98-045 | 17th July 1998
Detlef Sieling

A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

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

TR98-050 | 6th July 1998
Farid Ablayev, Svetlana Ablayeva

A Discrete Approximation and Communication Complexity Approach to the Superposition Problem

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

TR98-053 | 30th August 1998
Paul Beame, Michael Saks, Jayram S. Thathachar

Time-Space Tradeoffs for Branching Programs

Comments: 1

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

TR99-019 | 7th June 1999
Detlef Sieling

Lower Bounds for Linear Transformed OBDDs and FBDDs

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

TR99-020 | 9th June 1999
Marek Karpinski

Randomized Complexity of Linear Arrangements and Polyhedra

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, randomized lower bounds on the problems like ... more >>>

TR99-044 | 30th September 1999
Farid Ablayev

On Complexity of Regular $(1,+k)$-Branching Programs

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

TR99-048 | 7th December 1999
Beate Bollig, Ingo Wegener

Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

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 size but asymptotically optimal bounds are only ... more >>>

TR00-025 | 20th May 2000
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

Super-linear time-space tradeoff lower bounds for randomized computation

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

TR00-029 | 30th April 2000
Ran Raz, Amir Shpilka

Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates

Revisions: 1

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 and constant depth Boolean circuits with arbitrary ... more >>>

TR00-030 | 31st May 2000

A Simple Model for Neural Computation with Firing Rates and Firing Correlations

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

TR00-032 | 31st May 2000

On the Computational Power of Winner-Take-All

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 winner-take-all gates ... more >>>

TR00-042 | 21st June 2000
Lars Engebretsen

Lower Bounds for non-Boolean Constraint Satisfaction

Revisions: 1

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

TR00-057 | 25th July 2000
Martin Sauerhoff

An Improved Hierarchy Result for Partitioned BDDs

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

TR00-058 | 1st August 2000
Martin Sauerhoff

Approximation of Boolean Functions by Combinatorial Rectangles

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

TR00-089 | 1st December 2000
Lars Engebretsen, Marek Karpinski

Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

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

TR00-091 | 21st December 2000
Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

Approximability of Dense Instances of NEAREST CODEWORD Problem

We give a polynomial time approximation scheme (PTAS) for dense instances of the NEAREST CODEWORD problem. more >>>

TR01-025 | 28th March 2001
Piotr Berman, Marek Karpinski

Approximating Minimum Unsatisfiability of Linear Equations

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 the case of the ... more >>>

TR01-026 | 3rd April 2001
Piotr Berman, Marek Karpinski

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

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 is the bounded occurrence (degree) ... more >>>

TR01-034 | 30th April 2001
Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

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, and linear equations ... more >>>

TR01-039 | 18th May 2001
Stasys Jukna, Stanislav Zak

On Uncertainty versus Size in Branching Programs

Revisions: 1

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

TR01-041 | 23rd May 2001
Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, V. Vinay

Time-Space Tradeoffs in the Counting Hierarchy

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 circuits for iterated multiplication. ... more >>>

TR01-042 | 31st May 2001
Marek Karpinski

Approximating Bounded Degree Instances of NP-Hard Problems

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 of proving approximation hardness ... more >>>

TR01-049 | 11th July 2001
Stasys Jukna, Georg Schnitger

On Multi-Partition Communication Complexity of Triangle-Freeness

Comments: 2

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

TR01-053 | 17th July 2001
Piotr Berman, Marek Karpinski

Efficient Amplifiers and Bounded Degree Optimization

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 for bounded occurrence ... more >>>

TR01-060 | 23rd August 2001
Amir Shpilka

Lower bounds for matrix product

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

TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

On Multipartition Communication Complexity

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

TR01-067 | 18th September 2001
Hubie Chen

Polynomial Programs and the Razborov-Smolensky Method

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

TR01-073 | 24th October 2001
Beate Bollig, Philipp Woelfel, Stephan Waack

Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

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 for parity read-once branching programs ... more >>>

TR01-095 | 12th November 2001
Hubie Chen

Arithmetic Versions of Constant Depth Circuit Complexity Classes

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

TR01-101 | 14th December 2001
Philipp Woelfel

A Lower Bound Technique for Restricted Branching Programs and Applications

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 defined by Jukna ... more >>>

TR02-012 | 3rd February 2002
Ran Raz

On the Complexity of Matrix Product

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

TR02-013 | 30th January 2002
Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

Quantum and Stochastic Programs of Bounded Width

Revisions: 1

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

TR02-033 | 11th June 2002
Beate Bollig

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

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 function $f$ has nondeterministic ... more >>>

TR02-059 | 9th August 2002
Iordanis Kerenidis, Ronald de Wolf

Exponential Lower Bound for 2-Query Locally Decodable Codes

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

TR02-064 | 14th November 2002
Andrej Bogdanov, Luca Trevisan

Lower Bounds for Testing Bipartiteness in Dense Graphs

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 polylogarithmic factor. We ... more >>>

TR02-072 | 12th November 2002
Scott Aaronson

Quantum Lower Bound for Recursive Fourier Sampling

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

TR03-008 | 11th February 2003
Piotr Berman, Marek Karpinski

Improved Approximation Lower Bounds on Small Occurrence Optimization

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

TR03-022 | 11th April 2003
Piotr Berman, Marek Karpinski, Alexander D. Scott

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

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 approximation lower bound for this problem. We also ... more >>>

TR03-037 | 30th April 2003
Ziv Bar-Yossef

Sampling Lower Bounds via Information Theory

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

TR03-065 | 19th June 2003
Wee, Hoeteck

Compressibility Lower Bounds in Oracle Settings

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

TR03-067 | 14th August 2003
Ran Raz

Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size

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

TR03-068 | 30th July 2003
Matthias Homeister

Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs

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 of read--once ... more >>>

TR03-070 | 19th August 2003
Amit Chakrabarti, Oded Regev

An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

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

TR03-087 | 10th December 2003
Richard Beigel, Lance Fortnow, William Gasarch

A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

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

TR04-003 | 22nd December 2003
Pascal Koiran

Valiant's model and the cost of computing integers

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 1$. It is ... more >>>

TR04-004 | 13th January 2004
Ramamohan Paturi, Pavel Pudlak

Circuit lower bounds and linear codes

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

TR04-041 | 18th May 2004
Michael Alekhnovich, Edward Hirsch, Dmitry M. Itsykson

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

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

TR04-042 | 21st May 2004
Ran Raz

Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$

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 n)$. ... more >>>

TR04-085 | 3rd October 2004
Erez Petrank, Guy Rothblum

Selection from Structured Data Sets

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

TR05-021 | 14th February 2005
Stasys Jukna

Disproving the single level conjecture

Revisions: 2 , Comments: 1

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 are not much larger than ... more >>>

TR05-103 | 17th August 2005
Leonid Gurvits

A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

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

TR06-060 | 4th May 2006
Ran Raz, Amir Shpilka, Amir Yehudayoff

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

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

TR06-102 | 15th August 2006
Luis Rademacher, Santosh Vempala

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

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

TR07-009 | 8th January 2007
Nathan Segerlind

Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

Revisions: 1 , Comments: 1

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

TR07-036 | 6th April 2007
Ryan Williams

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers

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

TR07-038 | 23rd April 2007
Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

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

TR07-049 | 1st June 2007
Beate Bollig, Niko Range, Ingo Wegener

Exact OBDD Bounds for some Fundamental Functions

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

TR07-077 | 7th August 2007
Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

Testing for Concise Representations

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

TR07-085 | 2nd September 2007
Ran Raz, Amir Yehudayoff

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

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

TR07-090 | 11th September 2007
Shachar Lovett

Tight lower bounds for adaptive linearity tests

Revisions: 1 , Comments: 1

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

TR07-099 | 30th September 2007
Dieter van Melkebeek

A Survey of Lower Bounds for Satisfiability and Related Problems

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

TR07-110 | 24th October 2007
Beate Bollig

The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function

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

TR07-121 | 21st November 2007
Zeev Dvir, Amir Shpilka, Amir Yehudayoff

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

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

TR07-124 | 23rd November 2007
Nitin Saxena

Diagonal Circuit Identity Testing and Lower Bounds

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

TR08-001 | 5th January 2008
Ran Raz

Elusive Functions and Lower Bounds for Arithmetic Circuits

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$ of degree 1(that ... more >>>

TR08-006 | 18th January 2008
Ran Raz, Amir Yehudayoff

Lower Bounds and Separations for Constant Depth Multilinear Circuits

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

TR08-024 | 26th February 2008
Paul Beame, Trinh Huynh

On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

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

TR08-038 | 4th April 2008
Eric Allender, Michal Koucký

Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

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

TR08-056 | 22nd April 2008
Beate Bollig

On the OBDD complexity of the most significant bit of integer multiplication

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

TR08-057 | 14th May 2008
Alexander A. Sherstov

Communication Lower Bounds Using Dual Polynomials

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

TR08-061 | 11th June 2008
Paul Beame, Trinh Huynh

Multiparty Communication Complexity of AC^0

Revisions: 1

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

TR08-062 | 11th June 2008
Manindra Agrawal, V. Vinay

Arithmetic Circuits: A Chasm at Depth Four

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

TR08-082 | 11th September 2008
Paul Beame, Trinh Huynh

Multiparty Communication Complexity and Threshold Circuit Size of AC^0

Revisions: 1

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

TR09-013 | 4th February 2009
Atri Rudra

Limits to List Decoding Random Codes

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

TR09-015 | 19th February 2009
Joshua Brody, Amit Chakrabarti

A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

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

TR09-040 | 20th April 2009
Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

On convex complexity measures

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 negative result that convex measures ... more >>>

TR09-046 | 9th May 2009
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Transitive-Closure Spanners of the Hypercube and the Hypergrid

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

TR09-064 | 3rd August 2009
Harry Buhrman, Lance Fortnow, Rahul Santhanam

Unconditional Lower Bounds against Advice

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

TR09-073 | 6th September 2009
Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

On Lower Bounds for Constant Width Arithmetic Circuits

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

TR09-101 | 20th October 2009
Nitin Saxena

Progress on Polynomial Identity Testing

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

TR09-106 | 28th October 2009
Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

Using Elimination Theory to construct Rigid Matrices

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

TR09-126 | 26th November 2009
Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally Testable Codes Require Redundant Testers

Revisions: 3

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

ISSN 1433-8092 | Imprint