ECCC - Reports beginning with A

Electronic Colloquium on Computational Complexity

REPORTS > A-Z > A:

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

A

TR07-047 | 15th May 2007
Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum

A (De)constructive Approach to Program Checking

Program checking, program self-correcting and program self-testing were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in the mid eighties as a new way to gain confidence in software, by considering program correctness on an input by input basis rather than full program verification. Work in the field ... more >>>

TR04-084 | 28th September 2004
George Karakostas

A better approximation ratio for the Vertex Cover problem

We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$ (instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even, and by Monien and Speckenmeyer in 1985. The improvement of the vanishing factor comes as an application of the recent results of Arora, Rao, and Vazirani that improved the approximation ... more >>>

TR09-028 | 2nd April 2009
Oded Goldreich

A Candidate Counterexample to the Easy Cylinders Conjecture

We present a candidate counterexample to the easy cylinders conjecture, which was recently suggested by Manindra Agrawal and Osamu Watanabe (ECCC, TR09-019). Loosely speaking, the conjecture asserts that any 1-1 function in $P/poly$ can be decomposed into ``cylinders'' of sub-exponential size that can each be inverted by some polynomial-size circuit. ... more >>>

TR99-030 | 9th July 1999
Meena Mahajan, P R Subramanya, V. Vinay

A Combinatorial Algorithm for Pfaffians

The Pfaffian of an oriented graph is closely linked to Perfect Matching. It is also naturally related to the determinant of an appropriately defined matrix. This relation between Pfaffian and determinant is usually exploited to give a fast algorithm for computing Pfaffians. We present the first completely combinatorial algorithm for ... more >>>

TR02-035 | 27th May 2002
Albert Atserias, Víctor Dalmau

A Combinatorial Characterization of Resolution Width

We provide a characterization of the resolution width introduced in the context of Propositional Proof Complexity in terms of the existential pebble game introduced in the context of Finite Model Theory. The characterization is tight and purely combinatorial. Our first application of this result is a surprising proof that the ... more >>>

TR03-044 | 12th May 2003
Juan Luis Esteban, Jacobo Toran

A Combinatorial Characterization of Treelike Resolution Space

We show that the Player-Adversary game from a paper by Pudlak and Impagliazzo played over CNF propositional formulas gives an exact characterization of the space needed in treelike resolution refutations. This characterization is purely combinatorial and independent of the notion of resolution. We use this characterization to give for the ... more >>>

TR96-047 | 2nd September 1996
Oded Goldreich, Muli Safra

A Combinatorial Consistency Lemma with application to the PCP Theorem

Revisions: 1

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1))) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the difficulty of obtaining strong results regarding low-degree tests; namely, results of the type obtained and used by Arora and Safra and ... more >>>

TR07-066 | 24th April 2007
Maciej Liskiewicz, Christian Hundt

A Combinatorial Geometric Approach to Linear Image Matching

The problem of image matching is to find for two given digital images $A$ and $B$ an admissible transformation that converts image $A$ as close as possible to $B$. This problem becomes hard if the space of admissible transformations is too complex. Consequently, in many real applications, like the ones ... more >>>

TR96-039 | 27th June 1996
Carme Alvarez, Raymond Greenlaw

A Compendium of Problems Complete for Symmetric Logarithmic Space

Comments: 2

We provide a compendium of problems that are complete for symmetric logarithmic space (SL). Complete problems are one method of studying this class for which programming is nonintuitive. A number of the problems in the list were not previously known to be complete. A list containing a variety of open ... more >>>

TR10-018 | 15th February 2010
Vitaly Feldman

A Complete Characterization of Statistical Query Learning with Applications to Evolvability

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves. We describe a new and simple characterization of the query complexity ... more >>>

TR96-062 | 3rd December 1996
Sanjeev Khanna, Madhu Sudan, David P. Williamson

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

In this paper we study the approximability of boolean constraint satisfaction problems. A problem in this class consists of some collection of ``constraints'' (i.e., functions $f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set of constraints applied to specified subsets of $n$ boolean variables. Schaefer earlier studied the ... more >>>

TR00-084 | 6th November 2000
Salil Vadhan, Amit Sahai

A Complete Problem for Statistical Zero Knowledge

We present the first complete problem for SZK, the class of (promise) problems possessing statistical zero-knowledge proofs (against an honest verifier). The problem, called STATISTICAL DIFFERENCE, is to decide whether two efficiently samplable distributions are either statistically close or far apart. This gives a new characterization of SZK that makes ... more >>>

TR06-046 | 1st April 2006
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

A Complete Public-Key Cryptosystem

Comments: 1

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... more >>>

TR09-140 | 18th December 2009
Saugata Basu

A complex analogue of Toda's Theorem

Revisions: 1

Toda \cite{Toda} proved in 1989 that the (discrete) polynomial time hierarchy, $\mathbf{PH}$, is contained in the class $\mathbf{P}^{\#\mathbf{P}}$, namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity ... more >>>

TR96-059 | 12th November 1996
Shai Ben-David, Nader H. Bshouty, Eyal Kushilevitz

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

This paper solves the open problem of exact learning geometric objects bounded by hyperplanes (and more generally by any constant degree algebraic surfaces) in the constant dimensional space from equivalence queries only (i.e., in the on-line learning model). We present a novel approach that allows, under certain conditions, the composition ... more >>>

TR08-046 | 14th April 2008
Nikhil R. Devanur, Lance Fortnow

A Computational Theory of Awareness and Decision Making

We exhibit a new computational-based definition of awareness, informally that our level of unawareness of an object is the amount of time needed to generate that object within a certain environment. We give several examples to show this notion matches our intuition in scenarios where one organizes, accesses and transfers ... more >>>

TR02-061 | 14th November 2002
Miklos Ajtai

A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

A measure $\mu_{n}$ on $n$-dimensional lattices with determinant $1$ was introduced about fifty years ago to prove the existence of lattices which contain points from certain sets. $\mu_{n}$ is the unique probability measure on lattices with determinant $1$ which is invariant under linear transformations with determinant $1$, where a linear ... more >>>

TR98-010 | 22nd January 1998
Phong Nguyen, Jacques Stern

A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

Revisions: 1

Recently, Ajtai discovered a fascinating connection between the worst-case complexity and the average-case complexity of some well-known lattice problems. Later, Ajtai and Dwork proposed a cryptosystem inspired by Ajtai's work, provably secure if a particular lattice problem is difficult. We show that there is a converse to the Ajtai-Dwork security ... more >>>

TR08-018 | 28th February 2008
Ran Raz

A Counterexample to Strong Parallel Repetition

The parallel repetition theorem states that for any two-prover game, with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of the game repeated in parallel $n$ times is at most $(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length (of the original game) and $c$ is a universal constant. ... more >>>

TR10-026 | 25th February 2010
Hao Huang, Benny Sudakov

A counterexample to the Alon-Saks-Seymour conjecture and related problems

Consider a graph obtained by taking edge disjoint union of $k$ complete bipartite graphs. Alon, Saks and Seymour conjectured that such graph has chromatic number at most $k+1$. This well known conjecture remained open for almost twenty years. In this paper, we construct a counterexample to this conjecture and discuss ... more >>>

TR97-055 | 22nd September 1997
Bruce Edward Litow

A Decision Method for the Rational Sequence Problem

We give a method to decide whether or not an ordinary finite order linear recurrence with constant, rational coefficients ever generates zero. more >>>

TR10-014 | 2nd February 2010
Daniele Micciancio, Panagiotis Voulgaris

A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations

We give deterministic $2^{O(n)}$-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP). This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, Math. ... more >>>

TR07-029 | 20th January 2007
Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem

Revisions: 1

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou studied in [Gopalan et al., ICALP2006] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on connectivity problems in Schaefer's framework [Schaefer, STOC1978]. A set S of logical relations is Schaefer if all relations in ... 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 >>>

TR08-106 | 12th November 2008
Jack H. Lutz

A Divergence Formula for Randomness and Dimension

If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is ... more >>>

TR09-037 | 10th April 2009
Parikshit Gopalan

A Fourier-analytic approach to Reed-Muller decoding

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

TR02-003 | 24th December 2001
Eli Ben-Sasson, Yonatan Bilu

A Gap in Average Proof Complexity

We present the first example of a natural distribution on instances of an NP-complete problem, with the following properties. With high probability a random formula from this distribution (a) is unsatisfiable, (b) has a short proof that can be found easily, and (c) does not have a short (general) resolution ... more >>>

TR02-058 | 25th September 2002
Philippe Moser

A generalization of Lutz's measure to probabilistic classes

We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes C such as BPP , BPE and BPEXP. Unlike former attempts, all our measure notions satisfy all three Lutz's measure axioms, that is every singleton {L} has measure zero in C, the whole space ... more >>>

TR98-058 | 2nd August 1998
H. Buhrman, D. van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

We introduce "resource-bounded betting games", and propose a generalization of Lutz's resource-bounded measure in which the choice of next string to bet on is fully adaptive. Lutz's martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudo-random number generators exist, ... more >>>

TR05-111 | 3rd October 2005
Dieter van Melkebeek, Konstantin Pervyshev

A Generic Time Hierarchy for Semantic Models With One Bit of Advice

We show that for any reasonable semantic model of computation and for any positive integer $a$ and rationals $1 \leq c < d$, there exists a language computable in time $n^d$ with $a$ bits of advice but not in time $n^c$ with $a$ bits of advice. A semantic model is ... more >>>

TR05-009 | 14th December 2004
David P. Woodruff, Sergey Yekhanin

A Geometric Approach to Information-Theoretic Private Information Retrieval

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>

TR09-096 | 7th October 2009
Haralampos Tsaknakis, Paul Spirakis

A Graph Spectral Approach for Computing Approximate Nash Equilibria

We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games based upon certain extensions and specializations of an existing optimization approach previously used for the derivation of fixed approximations for this problem. In particular, the general two-person problem is reduced to an indefinite quadratic programming problem ... 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 >>>

TR01-017 | 14th February 2001
Petr Savicky, Detlef Sieling

A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

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

TR08-098 | 12th November 2008
Victor Chen

A Hypergraph Dictatorship Test with Perfect Completeness

Revisions: 1

A hypergraph dictatorship test is first introduced by Samorodnitsky and Trevisan and serves as a key component in their unique games based $\PCP$ construction. Such a test has oracle access to a collection of functions and determines whether all the functions are the same dictatorship, or all their low degree ... more >>>

TR01-059 | 20th July 2001
Elvira Mayordomo

A Kolmogorov complexity characterization of constructive Hausdorff dimension

Revisions: 3

We obtain the following full characterization of constructive dimension in terms of algorithmic information content. For every sequence A, cdim(A)=liminf_n (K(A[0..n-1])/n. more >>>

TR96-036 | 28th May 1996
Petr Savicky, Stanislav Zak

A large lower bound for 1-branching programs

Revisions: 1

Branching programs (b.p.'s) or decision diagrams are a general graph-based model of sequential computation. 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 1-b.p.'s, where each computation reads each input bit at ... more >>>

TR06-098 | 17th August 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

We study semidefinite programming relaxations of Vertex Cover arising from repeated applications of the LS+ ``lift-and-project'' method of Lovasz and Schrijver starting from the standard linear programming relaxation. Goemans and Kleinberg prove that after one round of LS+ the integrality gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>

TR00-074 | 12th July 2000
Daniele Micciancio, Bogdan Warinschi

A Linear Space Algorithm for Computing the Hermite Normal Form

Computing the Hermite Normal Form of an $n\times n$ matrix using the best current algorithms typically requires $O(n^3\log M)$ space, where $M$ is a bound on the length of the columns of the input matrix. Although polynomial in the input size (which is $O(n^2\log M)$), this space blow-up can easily ... more >>>

TR09-049 | 5th May 2009
Derrick Stolee, Derrick Stolee, Chris Bourke, N. V. Vinodchandran

A log-space algorithm for reachability in planar DAGs with few sources

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>

TR08-083 | 10th June 2008
Yijia Chen, Jörg Flum

A logic for PTIME and a parameterized halting problem

In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... 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 >>>

TR99-010 | 1st April 1999
Eric Allender, Igor E. Shparlinski, Michael Saks

A Lower Bound for Primality

Comments: 1

Recent work by Bernasconi, Damm and Shparlinski proved lower bounds on the circuit complexity of the square-free numbers, and raised as an open question if similar (or stronger) lower bounds could be proved for the set of prime numbers. In this short note, we answer this question affirmatively, by showing ... 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 >>>

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

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

TR02-002 | 3rd January 2002
Howard Barnum, Michael Saks

A lower bound on the quantum query complexity of read-once functions

We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions.Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires ``decoherence'' ... more >>>

TR08-110 | 19th November 2008
Chris Calabro

A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths

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

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

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

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

TR99-036 | 6th September 1999
Edward Hirsch

A New Algorithm for MAX-2-SAT

Revisions: 2

Recently there was a significant progress in proving (exponential-time) worst-case upper bounds for the propositional satisfiability problem (SAT). MAX-SAT is an important generalization of SAT. Several upper bounds were obtained for MAX-SAT and its NP-complete subproblems. In particular, Niedermeier and Rossmanith recently proved the worst-case upper bound O(2^{K/2.88...}) for MAX-2-SAT ... more >>>

TR04-032 | 5th February 2004
Ryan Williams

A new algorithm for optimal constraint satisfaction and its implications

We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of ... more >>>

TR98-013 | 3rd March 1998
Nader H. Bshouty

A New Composition Theorem for Learning Algorithms

We present a new approach to the composition of learning algorithms (in various models) for classes of constant VC-dimension into learning algorithms for more complicated classes. We prove that if a class $\CC$ is learnable in time $t$ from a hypothesis class $\HH$ of constant VC-dimension then the class $\C^\star$ ... more >>>

TR06-096 | 10th August 2006
Iftach Haitner, Omer Reingold

A New Interactive Hashing Theorem

Interactive hashing, introduced by Naor et al. [NOVY98], plays an important role in many cryptographic protocols. In particular, it is a major component in all known constructions of statistically-hiding commitment schemes and of zero-knowledge arguments based on general one-way permutations and on one-way functions. Interactive hashing with respect to a ... more >>>

TR09-059 | 2nd July 2009
Gábor Kun, Mario Szegedy

A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE

The well known dichotomy conjecture of Feder and Vardi states that for every ﬁnite family Γ of constraints CSP(Γ) is either polynomially solvable or NP-hard. Bulatov and Jeavons re- formulated this conjecture in terms of the properties of the algebra P ol(Γ), where the latter is the collection of those ... more >>>

TR09-025 | 11th March 2009
Arnaldo Moura, Igor Carboni Oliveira

A New Look at Some Classical Results in Computational Complexity

We propose a generalization of the traditional algorithmic space and time complexities. Using the concept introduced, we derive an unified proof for the deterministic time and space hierarchy theorems, now stated in a much more general setting. This opens the possibility for the unification and generalization of other results that ... more >>>

TR10-001 | 30th December 2009
Iftach Haitner, Mohammad Mahmoody, David Xiao

A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of $NP$

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

TR98-005 | 27th January 1998
Jin-Yi Cai

A new transference theorem and applications to Ajtai's connection factor

We prove a new transference theorem in the geometry of numbers, giving optimal bounds relating the successive minima of a lattice with the minimal length of generating vectors of its dual. It generalizes the transference theorem due to Banaszczyk. We also prove a stronger bound for the special class of ... more >>>

TR99-026 | 7th July 1999
Miklos Ajtai

A Non-linear Time Lower Bound for Boolean Branching Programs

We prove that for all positive integer $k$ and for all sufficiently small $\epsilon >0$ if $n$ is sufficiently large then there is no Boolean (or $2$-way) branching program of size less than $2^{\epsilon n}$ which for all inputs $X\subseteq \lbrace 0,1,...,n-1\rbrace $ computes in time $kn$ the parity of ... more >>>

TR05-122 | 31st October 2005
Pavel Pudlak

A nonlinear bound on the number of wires in bounded depth circuits

We shall prove a lower bound on the number of edges in some bounded depth graphs. This theorem is stronger than lower bounds proved on bounded depth superconcentrators and enables us to prove a lower bound on certain bounded depth circuits for which we cannot use superconcentrators: we prove that ... more >>>

TR06-089 | 16th July 2006
Sofya Raskhodnikova, Adam Smith

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

We show that in the bounded degree model for graph property testing, adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>

TR00-043 | 21st June 2000
Uriel Feige, Marek Karpinski, Michael Langberg

A Note on Approximating MAX-BISECTION on Regular Graphs

We design a $0.795$ approximation algorithm for the Max-Bisection problem restricted to regular graphs. In the case of three regular graphs our results imply an approximation ratio of $0.834$. more >>>

TR02-069 | 14th November 2002
Luca Trevisan

A Note on Deterministic Approximate Counting for k-DNF

Revisions: 1

We describe a deterministic algorithm that, for constant k, given a k-DNF or k-CNF formula f and a parameter e, runs in time linear in the size of f and polynomial in 1/e and returns an estimate of the fraction of satisfying assignments for f up to an additive error ... more >>>

TR04-047 | 22nd April 2004
Xiaoyang Gu

A note on dimensions of polynomial size circuits

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

TR09-069 | 2nd September 2009
Parikshit Gopalan

A note on Efremenko's Locally Decodable Codes

Revisions: 1

Building on work of Yekhanin and Raghavendra, Efremenko recently gave an elegant construction of 3-query LDCs which achieve sub-exponential length unconditionally.In this note, we observe that this construction can be viewed in the framework of Reed-Muller codes. more >>>

TR99-009 | 26th March 1999
Marek Karpinski, Rustam Mubarakzjanov

A Note on Las Vegas OBDDs

We prove that the error-free (Las Vegas) randomized OBDDs are computationally equivalent to the deterministic OBDDs. In contrast, it is known the same is not true for the Las Vegas read-once branching programs. more >>>

TR94-027 | 12th December 1994
Stasys Jukna

A Note on Read-k Times Branching Programs

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}), although its complement ... more >>>

TR95-009 | 2nd February 1995
Matthias Krause

A note on realizing iterated multiplication by small depth threshold circuits

It is shown that decomposition via Chinise Remainder does not yield polynomial size depth 3 threshold circuits for iterated multiplication of n-bit numbers. This result is achieved by proving that, in contrast to multiplication of two n-bit numbers, powering, division, and other related problems, the resulting subproblems, iterated multiplication modulo ... more >>>

TR07-105 | 21st September 2007
Jelani Nelson

A Note on Set Cover Inapproximability Independent of Universe Size

Revisions: 1

In the set cover problem we are given a collection of $m$ sets whose union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection whose union still covers $[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on $m$ and observe that, for ... more >>>

TR01-029 | 27th March 2001
Denis Xavier Charles

A Note on Subgroup Membership Problem for PSL(2,p).

Comments: 1

We show that there are infinitely many primes $p$, such that the subgroup membership problem for PSL(2,p) belongs to $\NP \cap \coNP$. more >>>

TR05-130 | 31st October 2005
Ahuva Mu'alem

A Note on Testing Truthfulness

This work initiates the study of algorithms for the testing of monotonicity of mechanisms. Such testing algorithms are useful for searching dominant strategy mechanisms. An $\e$-tester for monotonicity is given a query access to a mechanism, accepts if monotonicity is satisfied, and rejects with high probability if more than $\e$-fraction ... more >>>

TR04-056 | 1st July 2004
N. V. Vinodchandran

A note on the circuit complexity of PP

In this short note we show that for any integer k, there are languages in the complexity class PP that do not have Boolean circuits of size $n^k$. more >>>

TR01-092 | 2nd October 2001
Till Tantau

A Note on the Complexity of the Reachability Problem for Tournaments

Deciding whether a vertex in a graph is reachable from another vertex has been studied intensively in complexity theory and is well understood. For common types of graphs like directed graphs, undirected graphs, dags or trees it takes a (possibly nondeterministic) logspace machine to decide the reachability problem, and the ... more >>>

TR06-076 | 4th May 2006
Noam Nisan

A Note on the computational hardness of evolutionary stable strategies

We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard ... more >>>

TR08-012 | 20th November 2007
Arnab Bhattacharyya

A Note on the Distance to Monotonicity of Boolean Functions

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... more >>>

TR00-088 | 28th November 2000
Meena Mahajan, V. Vinay

A note on the hardness of the characteristic polynomial

In this note, we consider the problem of computing the coefficients of the characteristic polynomial of a given matrix, and the related problem of verifying the coefficents. Santha and Tan [CC98] show that verifying the determinant (the constant term in the characteristic polynomial) is complete for the class C=L, and ... more >>>

TR01-058 | 28th August 2001
Stasys Jukna

A Note on the Minimum Number of Negations Leading to Superpolynomial Savings

In 1957 Markov proved that every circuit in $n$ variables can be simulated by a circuit with at most $\log(n+1)$ negations. In 1974 Fischer has shown that this can be done with only polynomial increase in size. In this note we observe that some explicit monotone functions in $P$ cannot ... more >>>

TR04-062 | 28th July 2004
Stasys Jukna

A note on the P versus NP intersected with co-NP question in communication complexity

Revisions: 1 , Comments: 1

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>

TR02-004 | 2nd November 2001
Till Tantau

A Note on the Power of Extra Queries to Membership Comparable Sets

A language is called k-membership comparable if there exists a polynomial-time algorithm that excludes for any k words one of the 2^k possibilities for their characteristic string. It is known that all membership comparable languages can be reduced to some P-selective language with polynomially many adaptive queries. We show however ... more >>>

TR98-042 | 27th July 1998
Pavel Pudlak

A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits

Comments: 1

We consider computations of linear forms over {\bf R} by circuits with linear gates where the absolute values coefficients are bounded by a constant. Also we consider a related concept of restricted rigidity of a matrix. We prove some lower bounds on the size of such circuits and the restricted ... more >>>

TR04-118 | 21st December 2004
Marek Karpinski, Yakov Nekrich

A Note on Traversing Skew Merkle Trees

We consider the problem of traversing skew (unbalanced) Merkle trees and design an algorithm for traversing a skew Merkle tree in time O(log n/log t) and space O(log n (t/log t)), for any choice of parameter t\geq 2. This algorithm can be of special interest in situations when the exact ... more >>>

TR96-023 | 21st March 1996
Eric Allender

A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Comments: 1

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer [CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0 is properly contained in the counting hierarchy. Thus, [CMTV] shows that there are problems in ModPH that require superpolynomial-size uniform ACC^0 circuits, and problems in the counting hierarchy that ... more >>>

TR07-016 | 13th February 2007
Prasad Raghavendra

A Note on Yekhanin's Locally Decodable Codes

Revisions: 1

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors. In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p ... more >>>

TR09-027 | 2nd April 2009
Iftach Haitner

A Parallel Repetition Theorem for Any Interactive Argument

Revisions: 1

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>>

TR10-019 | 19th February 2010
Andrew Drucker

A PCP Characterization of AM

We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class $\mathsf{AM}$. This gives a `PCP characterization' of $\mathsf{AM}$ analogous to the PCP Theorem for $\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, ... more >>>

TR00-064 | 29th August 2000
Klaus Jansen, Marek Karpinski, Andrzej Lingas

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximize or minimize, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first polynomial time approximation ... more >>>

TR02-041 | 2nd July 2002
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given finite metric space into two halves so as to minimize the sum of distances across that partition. The method of solution depends on a new metric placement partitioning method which could be ... more >>>

TR02-044 | 16th July 2002
Wenceslas Fernandez de la Vega, Marek Karpinski

A Polynomial Time Approximation Scheme for Subdense MAX-CUT

We prove that the subdense instances of MAX-CUT of average degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general 2-ary maximum constraint satisfaction problems (MAX-CSP) of the same average density have PTASs. Our results display for the first ... more >>>

TR04-038 | 27th April 2004
John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann

A Polynomial Time Learner for a Subclass of Regular Patterns

Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns $\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$ for unknown $m$ but known $c$, from number ... more >>>

TR00-079 | 12th September 2000
Mark Jerrum, Eric Vigoda

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries. more >>>

TR09-078 | 16th September 2009
Falk Unger

A Probabilistic Inequality with Applications to Threshold Direct-product Theorems

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments. This inequality allows us to simplify and strengthen several known direct-product ... more >>>

TR98-051 | 20th July 1998
Petr Savicky

A probabilistic nonequivalence test for syntactic (1,+k)-branching programs

Branching programs are a model for representing Boolean functions. For general branching programs, the satisfiability and nonequivalence tests are NP-complete. For read-once branching programs, which can test each variable at most once in each computation, the satisfiability test is trivial and there is also a probabilistic polynomial time test of ... 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 >>>

TR04-063 | 23rd July 2004
Yehuda Lindell, Benny Pinkas

A Proof of Yao's Protocol for Secure Two-Party Computation

In the mid 1980's, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao's protocol, along with a rigorous proof of security. Despite the importance of Yao's protocol to the field ... more >>>

TR96-065 | 13th December 1996
Miklos Ajtai, Cynthia Dwork

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1 , Comments: 1

We present a probabilistic public key cryptosystem which is secure unless the following worst-case lattice problem can be solved in polynomial time: "Find the shortest nonzero vector in an n dimensional lattice L where the shortest vector v is unique in the sense that any other vector whose length is ... more >>>

TR03-086 | 1st December 2003
Amos Beimel, Tal Malkin

A Quantitative Approach to Reductions in Secure Computation

Secure computation is one of the most fundamental cryptographic tasks. It is known that all functions can be computed securely in the information theoretic setting, given access to a black box for some complete function such as AND. However, without such a black box, not all functions can be securely ... more >>>

TR08-017 | 16th December 2007
Dieter van Melkebeek, Thomas Watson

A Quantum Time-Space Lower Bound for the Counting Hierarchy

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

TR09-074 | 10th September 2009
Suguru Tamaki, Yuichi Yoshida

A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness

Long Code testing is a fundamental problem in the area of property testing and hardness of approximation. Long Code is a function of the form $f(x)=x_i$ for some index $i$. In the Long Code testing, the problem is, given oracle access to a collection of Boolean functions, to decide whether ... more >>>

TR05-156 | 13th December 2005
Jonathan A. Kelner, Daniel A. Spielman

A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)

We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input. We begin by reducing the input linear program to a special form in which we ... more >>>

TR05-107 | 28th September 2005
Avi Wigderson, David Xiao

A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Revisions: 1

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>

TR05-035 | 24th March 2005
Christian Glaßer, Stephen Travers, Klaus W. Wagner

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

We introduce the polynomial-time tree reducibility (ptt-reducibility). Our main result states that for languages $B$ and $C$ it holds that $B$ ptt-reduces to $C$ if and only if the unbalanced leaf-language class of $B$ is robustly contained in the unbalanced leaf-language class of $C$. This is the {\em unbalanced} analogue ... more >>>

TR04-006 | 6th January 2004
Günter Hotz

A remark on nondecidabilities of the initial value problem of ODEs

We prove that it is not decidable on R-machines if for a fixed finite intervall [a,b) the solution of the initial value problems of systems of ordinary differetial equations have solutions over this interval. This result holds independly from assumptions about differentiability of the right sides of the ODEs. Futhermore ... more >>>

TR97-020 | 15th May 1997
Oded Goldreich

A Sample of Samplers -- A Computational Perspective on Sampling (survey).

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 err with probability ... more >>>

TR01-024 | 1st March 2001
Stephen Cook, Antonina Kolokolova

A second-order system for polynomial-time reasoning based on Graedel's theorem

We introduce a second-order system V_1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Graedel's second-order Horn characterization of P. Our system has comprehension over P predicates (defined by Graedel's second-order Horn formulas), and only finitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates ... more >>>

TR00-027 | 11th April 2000
Pavol Duris, Juraj Hromkovic, Katsushi Inoue

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. In this paper for the first time a "strong" separation between the power of determinism, Las Vegas randomization, and nondeterminism for a compu- ting model is proved. The computing ... 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 >>>

TR06-121 | 14th September 2006
Charanjit Jutla

A Simple Biased Distribution for Dinur's Construction

more >>>

TR08-093 | 1st October 2008
Cristopher Moore, Alexander Russell

A simple constant-probability RP reduction from NP to Parity P

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... 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 >>>

TR08-081 | 11th September 2008
Alexander Razborov

A simple proof of Bazzi's theorem

In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas. The aim of this note is to present a simplified version of his proof. more >>>

TR07-114 | 28th September 2007
Jakob Nordström

A Simplified Way of Proving Trade-off Results for Resolution

We present a greatly simplified proof of the length-space trade-off result for resolution in Hertel and Pitassi (2007), and also prove a couple of other theorems in the same vein. We point out two important ingredients needed for our proofs to work, and discuss possible conclusions to be drawn regarding ... more >>>

TR09-047 | 20th April 2009
Eli Ben-Sasson, Jakob Nordström

A Space Hierarchy for k-DNF Resolution

The k-DNF resolution proof systems are a family of systems indexed by the integer k, where the kth member is restricted to operating with formulas in disjunctive normal form with all terms of bounded arity k (k-DNF formulas). This family was introduced in [Krajicek 2001] as an extension of the ... more >>>

TR95-060 | 21st November 1995
Nader H. Bshouty

A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

We present a $2^{\tilde O(\sqrt{n})}$ time exact learning algorithm for polynomial size DNF using equivalence queries only. In particular, DNF is PAC-learnable in subexponential time under any distribution. This is the first subexponential time PAC-learning algorithm for DNF under any distribution. 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 >>>

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

TR09-075 | 17th September 2009
Oded Goldreich, Brendan Juba, Madhu Sudan

A Theory of Goal-Oriented Communication

Comments: 1

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

TR98-034 | 23rd June 1998
Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

A tight characterization of NP with 3 query PCPs

It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a {\em one-sided} error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 queries possess non-trivial verification power ... more >>>

TR04-073 | 9th July 2004
Henning Fernau

A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set

In this paper, we show how to systematically improve on parameterized algorithms and their analysis, focusing on search-tree based algorithms for d-Hitting Set, especially for d=3. We concentrate on algorithms which are easy to implement, in contrast with the highly sophisticated algorithms which have been elsewhere designed to improve on ... more >>>

TR03-075 | 7th September 2003
Agostino Capponi

A tutorial on the Deterministic two-party Communication Complexity

Communication complexity is concerned with the question: how much information do the participants of a communication system need to exchange in order to perform certain tasks? The minimum number of bits that must be communicated is the deterministic communication complexity of $f$. This complexity measure was introduced by Yao \cite{1} ... more >>>

TR01-016 | 22nd December 2000
Ran Canetti

A unified framework for analyzing security of protocols

Revisions: 3

Building on known definitions, we present a unified general framework for defining and analyzing security of cryptographic protocols. The framework allows specifying the security requirements of a large number of cryptographic tasks, such as signature, encryption, authentication, key exchange, commitment, oblivious transfer, zero-knowledge, secret sharing, general function evaluation, and more. ... more >>>

TR05-078 | 25th May 2005
Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz

A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme

Revisions: 1

In this paper, firstly we propose two new concepts concerning the notion of key escrow encryption schemes: provable partiality and independency. Roughly speaking we say that a scheme has provable partiality if existing polynomial time algorithm for recovering the secret knowing escrowed information implies a polynomial time algorithm that can ... 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 >>>

TR07-088 | 7th September 2007
Elad Hazan, C. Seshadhri

Adaptive Algorithms for Online Decision Problems

Revisions: 1

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>

TR06-042 | 16th March 2006
Amit Deshpande, Santosh Vempala

Adaptive Sampling and Fast Low-Rank Matrix Approximation

We prove that any real matrix $A$ contains a subset of at most $4k/\eps + 2k \log(k+1)$ rows whose span ``contains" a matrix of rank at most $k$ with error only $(1+\eps)$ times the error of the best rank-$k$ approximation of $A$. This leads to an algorithm to find such ... more >>>

TR96-051 | 1st October 1996
Richard Beigel, William Gasarch, Ming Li, Louxin Zhang

Addition in $\log_2{n}$ + O(1)$ Steps on Average: A Simple Analysis

We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two $n$-bit numbers in $\ceiling{\log_2{n}}+2$ steps on average. We simplify the analysis of Burks, Goldstine, and von Neumann in 1946 and (in more complete forms) of Briley and of Schay. more >>>

TR10-044 | 12th March 2010
Eli Ben-Sasson, Swastik Kopparty

Affine Dispersers from Subspace Polynomials

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

TR01-035 | 15th April 2001
Amir Shpilka

Affine Projections of Symmetric Polynomials

In this paper we introduce a new model for computing=20 polynomials - a depth 2 circuit with a symmetric gate at the top=20 and plus gates at the bottom, i.e the circuit computes a=20 symmetric function in linear functions - $S_{m}^{d}(\ell_1,\ell_2,...,\ell_m)$ ($S_{m}^{d}$ is the $d$'th=20 elementary symmetric polynomial in $m$ ... more >>>

TR04-028 | 19th March 2004
Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker

Aggregates with Component Size One Characterize Polynomial Space

Aggregates are a computational model similar to circuits, but the underlying graph is not necessarily acyclic. Logspace-uniform polynomial-size aggregates decide exactly the languages in PSPACE; without uniformity condition they decide the languages in PSPACE/poly. As a measure of similarity to boolean circuits we introduce the parameter component size. We prove ... more >>>

TR94-020 | 12th December 1994

Agnostic PAC-Learning of Functions on Analog Neural Nets

We consider learning on multi-layer neural nets with piecewise polynomial activation functions and a fixed number k of numerical inputs. We exhibit arbitrarily large network architectures for which efficient and provably successful learning algorithms exist in the rather realistic refinement of Valiant's model for probably approximately correct learning ("PAC-learning") where ... more >>>

TR00-013 | 14th February 2000
Daniel Král

Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

Ordered binary decision diagrams (OBDDs) and parity ordered binary decision diagrams have proved their importance as data structures representing Boolean functions. In addition to parity OBDDs we study their generalization which we call parity AOBDDs, give the algebraic characterization theorem and compare their minimal size to the size of parity ... more >>>

TR07-022 | 20th February 2007
Rafail Ostrovsky, William Skeith

Algebraic Lower Bounds for Computing on Encrypted Data

In cryptography, there has been tremendous success in building primitives out of homomorphic semantically-secure encryption schemes, using homomorphic properties in a black-box way. A few notable examples of such primitives include items like private information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general methodology for ... more >>>

TR01-011 | 21st January 2001
Dima Grigoriev, Edward Hirsch

Algebraic proof systems over formulas

We introduce two algebraic propositional proof systems F-NS and F-PC. The main difference of our systems from (customary) Nullstellensatz and Polynomial Calculus is that the polynomials are represented as arbitrary formulas (rather than sums of monomials). Short proofs of Tseitin's tautologies in the constant-depth version of F-NS provide an exponential ... more >>>

TR07-111 | 1st November 2007
Tali Kaufman, Madhu Sudan

Algebraic Property Testing: The Role of Invariance

We argue that the symmetries of a property being tested play a central role in property testing. We support this assertion in the context of algebraic functions, by examining properties of functions mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$. We consider $\F$-linear properties that ... more >>>

TR05-132 | 8th November 2005
Venkatesan Guruswami

Algebraic-geometric generalizations of the Parvaresh-Vardy codes

This paper is concerned with a new family of error-correcting codes based on algebraic curves over finite fields, and list decoding algorithms for them. The basic goal in the subject of list decoding is to construct error-correcting codes $C$ over some alphabet $\Sigma$ which have good rate $R$, and at ... more >>>

TR08-005 | 15th January 2008
Scott Aaronson, Avi Wigderson

Algebrization: A New Barrier in Complexity Theory

Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier ... more >>>

TR08-039 | 7th April 2008
Oded Goldreich, Dana Ron

Algorithmic Aspects of Property Testing in the Dense Graphs Model

In this paper we consider two refined questions regarding the query complexity of testing graph properties in the adjacency matrix model. The first question refers to the relation between adaptive and non-adaptive testers, whereas the second question refers to testability within complexity that is inversely proportional to the proximity parameter, ... more >>>

TR09-147 | 30th December 2009
Stephan Kreutzer

Algorithmic Meta-Theorems

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a structural component, that is they are results of the form: "every computational problem that can be formalised in a given logic L ... more >>>

TR05-033 | 5th March 2005
Martin Furer, Shiva Prasad Kasiviswanathan

Algorithms for Counting 2-SAT Solutions and Colorings with Applications

An algorithm is presented for counting the number of maximum weight satisfying assignments of a 2SAT formula. The worst case running time of $O(\mbox{poly($n$)} \cdot 1.2461^n)$ for formulas with $n$ variables improves on the previous bound of $O(\mbox{poly($n$)} \cdot 1.2561^n)$ by Dahll\"of, Jonsson, and Wahlstr\"om . The weighted 2SAT counting ... more >>>

TR07-059 | 6th July 2007
Shankar Kalyanaraman, Chris Umans

Algorithms for Playing Games with Limited Randomness

We study multiplayer games in which the participants have access to only limited randomness. This constrains both the algorithms used to compute equilibria (they should use little or no randomness) as well as the mixed strategies that the participants are capable of playing (these should be sparse). We frame algorithmic ... more >>>

TR01-012 | 4th January 2001
Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

Algorithms for SAT and Upper Bounds on Their Complexity

We survey recent algorithms for the propositional satisfiability problem, in particular algorithms that have the best current worst-case upper bounds on their complexity. We also discuss some related issues: the derandomization of the algorithm of Paturi, Pudlak, Saks and Zane, the Valiant-Vazirani Lemma, and random walk algorithms with the "back ... more >>>

TR03-072 | 15th September 2003
Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

Algorithms for SAT based on search in Hamming balls

We present a simple randomized algorithm for SAT and prove an upper bound on its running time. Given a Boolean formula F in conjunctive normal form, the algorithm finds a satisfying assignment for F (if any) by repeating the following: Choose an assignment A at random and search for a ... more >>>

TR06-122 | 20th September 2006
Noam Livne

All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

In 1984 Levin put forward a suggestion for a theory of {\em average case complexity}. In this theory a problem, called a {\em distributional problem}, is defined as a pair consisting of a decision problem and a probability distribution over the instances. Introducing adequate notions of simple distributions and average ... more >>>

TR97-040 | 17th September 1997
Dorit Dor, Shay Halperin, Uri Zwick

All Pairs Almost Shortest Paths

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth, Chekuri and Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time ... more >>>

TR00-060 | 17th August 2000
Uri Zwick

All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

We present two new algorithms for solving the {\em All Pairs Shortest Paths\/} (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in $\Ot(n^{2+\mu})$ ... more >>>

TR99-004 | 3rd February 1999
Valentine Kabanets

Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

Revisions: 1

Andreev et al.~\cite{ABCR97} give constructions of Boolean functions (computable by polynomial-size circuits) that require large read-once branching program (1-b.p.'s): a function in P that requires 1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a function in LINSPACE ... more >>>

TR02-048 | 31st July 2002
Noga Alon, Oded Goldreich, Yishay Mansour

Almost $k$-wise independence versus $k$-wise independence

We say that a distribution over $\{0,1\}^n$ is almost $k$-wise independent if its restriction to every $k$ coordinates results in a distribution that is close to the uniform distribution. A natural question regarding almost $k$-wise independent distributions is how close they are to some $k$-wise independent distribution. We show that ... more >>>

TR05-010 | 8th December 2004
Olivier Powell

Almost Completeness in Small Complexity Classes

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... more >>>

TR07-012 | 22nd January 2007
Shachar Lovett, Sasha Sodin

Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

It is well known that $\R^N$ has subspaces of dimension proportional to $N$ on which the $\ell_1$ norm is equivalent to the $\ell_2$ norm; however, no explicit constructions are known. Extending earlier work by Artstein--Avidan and Milman, we prove that such a subspace can be generated using $O(N)$ random bits. more >>>

TR07-086 | 7th September 2007
Venkatesan Guruswami, James R. Lee, Alexander Razborov

Almost Euclidean subspaces of $\ell_1^N$ via expander codes

We give an explicit (in particular, deterministic polynomial time) construction of subspaces $X \subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$, $$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$ If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits and $\dim(X) \geq (1-\eta)N$ ... more >>>

TR09-120 | 18th November 2009
Charanjit Jutla

Almost Optimal Bounds for Direct Product Threshold Theorem

Revisions: 1

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel. Canetti et al ... more >>>

TR03-066 | 2nd September 2003
Daniele Micciancio

Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... 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 >>>

TR96-010 | 9th February 1996
Christoph Meinel, Anna Slobodova

An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams

Revisions: 1

Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem P is reducible to a problem S if P can be computed using a program or device for S as a subroutine. However, in the case of such restricted models as ordered binary decision diagrams ... more >>>

TR08-108 | 19th November 2008
Nitin Saxena, C. Seshadhri

An Almost Optimal Rank Bound for Depth-3 Identities

We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most O(k^3\log d). The previous best rank bound known was 2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005). This almost resolves the rank question first posed by Dvir and Shpilka ... more >>>

TR00-018 | 16th February 2000
Oliver Kullmann

An application of matroid theory to the SAT problem

A basic property of minimally unsatisfiable clause-sets F is that c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and n(F) the number of variables. Let MUSAT(k) be the class of minimally unsatisfiable clause-sets F with c(F) <= n(F) + k. Poly-time decision algorithms are known ... more >>>

TR04-110 | 24th November 2004
Tomoyuki Yamakami, Harumichi Nishimura

An Application of Quantum Finite Automata to Interactive Proof Systems

Quantum finite automata have been studied intensively since their introduction in late 1990s as a natural model of a quantum computer with finite-dimensional quantum memory space. This paper seeks their direct application to interactive proof systems in which a mighty quantum prover communicates with a quantum-automaton verifier through a common ... more >>>

TR09-085 | 14th September 2009
Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

An Approach to characterize the Regular Languages in TC0 with Linear Wires

Revisions: 1

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires. We present a simple proof to show that parity cannot be computed by such circuits. Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ... more >>>

TR97-017 | 5th May 1997
Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

The bandwidth problem is the problem of numbering the vertices of a given graph $G$ such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and is known to be NP-complete Papadimitriou [Pa76]. Only few special cases of this problem are ... more >>>

TR04-048 | 21st April 2004
André Lanka, Andreas Goerdt

An approximation hardness result for bipartite Clique

Assuming 3-SAT formulas are hard to refute on average, Feige showed some approximation hardness results for several problems like min bisection, dense $k$-subgraph, max bipartite clique and the 2-catalog segmentation problem. We show a similar result for max bipartite clique, but under the assumption, 4-SAT formulas are hard to refute ... more >>>

TR98-069 | 7th December 1998
Rüdiger Reischuk, Thomas Zeugmann

An Average-Case Optimal One-Variable Pattern Language Learner

A new algorithm for learning one-variable pattern languages from positive data is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all operations till convergence to a correct hypothesis is achieved. For almost all meaningful distributions defining how the pattern ... more >>>

TR95-038 | 2nd July 1995
Joe Kilian, Erez Petrank

An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions

We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum, Feldman and Micali \cite{bfm}. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for {\sf NP} based on general complexity assumptions \cite{fls} versus those based on specific algebraic assumptions \cite{Da}. Recently, ... more >>>

TR06-119 | 13th September 2006
Noga Alon, Oded Schwartz, Asaf Shapira

An Elementary Construction of Constant-Degree Expanders

We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement-product, which we analyze using an elementary combinatorial argument. The construction applies the replacement product (only twice!) to turn the Cayley expanders of \cite{AR}, whose degree is polylog n, into constant degree expanders. more >>>

TR01-083 | 29th October 2001
Nikolai K. Vereshchagin

An enumerable undecidable set with low prefix complexity: a simplified proof

Revisions: 1

We present a simplified proof of Solovay-Calude-Coles theorem stating that there is an enumerable undecidable set with the following property: prefix complexity of its initial segment of length n is bounded by prefix complexity of n (up to an additive constant). more >>>

TR03-013 | 7th March 2003
Luca Trevisan

An epsilon-Biased Generator in NC0

Comments: 1

Cryan and Miltersen recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator such that every bit of the output depends on a constant number k of bits of the seed. They show that for k=3 there is always a distinguisher; ... more >>>

TR07-007 | 17th January 2007
Jan Krajicek

An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams

We prove an exponential lower bound on the size of proofs in the proof system operating with ordered binary decision diagrams introduced by Atserias, Kolaitis and Vardi. In fact, the lower bound applies to semantic derivations operating with sets defined by OBDDs. We do not assume any particular format of ... more >>>

TR95-057 | 24th November 1995
Dima Grigoriev, Marek Karpinski, A. C. Yao

An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

We prove an exponential lower bound on the size of any fixed-degree algebraic decision tree for solving MAX, the problem of finding the maximum of $n$ real numbers. This complements the $n-1$ lower bound of Rabin \cite{R72} on the depth of algebraic decision trees for this problem. The proof in ... more >>>

TR94-018 | 12th December 1994
Jan Krajicek, Pavel Pudlak, Alan Woods

An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

We prove lower bounds of the form $exp\left(n^{\epsilon_d}\right),$ $\epsilon_d>0,$ on the length of proofs of an explicit sequence of tautologies, based on the Pigeonhole Principle, in proof systems using formulas of depth $d,$ for any constant $d.$ This is the largest lower bound for the strongest proof system, for which ... more >>>

TR01-056 | 6th August 2001
Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

An Exponential Separation between Regular and General Resolution

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

TR07-046 | 23rd April 2007
Philipp Hertel

An Exponential Time/Space Speedup For Resolution

Comments: 1

Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and diagnosis problems. The main reason for the success is due to highly optimized algorithms for SAT based on resolution. The most successful of these ... more >>>

TR07-034 | 29th March 2007
Anup Rao

An Exposition of Bourgain's 2-Source Extractor

A construction of Bourgain gave the first 2-source extractor to break the min-entropy rate 1/2 barrier. In this note, we write an exposition of his result, giving a high level way to view his extractor construction. We also include a proof of a generalization of Vazirani's XOR lemma that seems ... more >>>

TR05-067 | 28th June 2005
Zeev Dvir, Amir Shpilka

An Improved Analysis of Mergers

Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate $\delta$ then the output has min-entropy rate close to $\delta$. Mergers have proven to be a very useful tool in ... more >>>

TR06-107 | 26th August 2006
Arkadev Chattopadhyay

An improved bound on correlation between polynomials over Z_m and MOD_q

Revisions: 1

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... 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 >>>

TR05-030 | 12th February 2005
Evgeny Dantsin, Alexander Wolpert

An Improved Upper Bound for SAT

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

TR07-117 | 8th November 2007
Edward Hirsch, Dmitry M. Itsykson

An infinitely-often one-way function based on an average-case assumption

We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, ... more >>>

TR09-144 | 24th December 2009
Prahladh Harsha, Adam Klivans, Raghu Meka

An Invariance Principle for Polytopes

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$ formed by the intersection of $k$ halfspaces, we prove that $$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k \cdot \Delta,$$ where $\Delta$ is ... more >>>

TR06-011 | 2nd January 2006
Yijia Chen, Martin Grohe

An Isomorphism between Subexponential and Parameterized Complexity Theory

We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories. more >>>

TR96-002 | 10th January 1996
Manindra Agrawal, Eric Allender

An Isomorphism Theorem for Circuit Complexity

We show that all sets complete for NC$^1$ under AC$^0$ reductions are isomorphic under AC$^0$-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC$^1$-computable many-one reductions, the sets complete for C under NC$^0$ reductions are ... more >>>

TR04-114 | 21st November 2004
Vladimir Trifonov

An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity

We present a deterministic O(log n log log n) space algorithm for undirected s,t-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam (SODA 93) and uses the universal exploration sequences for trees constructed by Kouck\'y (CCC 01). Our result improves the O(log^{4/3} n) bound of Armoni ... more >>>

TR06-050 | 18th April 2006
Alexander Razborov, Sergey Yekhanin

An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

A two server private information retrieval (PIR) scheme allows a user U to retrieve the i-th bit of an n-bit string x replicated between two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the ... 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 >>>

TR96-020 | 6th March 1996
C.P. Schnorr, Carsten Rössner

An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension

more >>>

TR06-056 | 27th April 2006
Salil Vadhan

An Unconditional Study of Computational Zero Knowledge

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. We establish several new characterizations of ZK, and use these characterizations to ... more >>>

TR95-010 | 16th February 1995
Pavel Pudlak, Jiri Sgall

An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

We prove an unexpected upper bound on a communication game proposed by Jeff Edmonds and Russell Impagliazzo as an approach for proving lower bounds for time-space tradeoffs for branching programs. Our result is based on a generalization of a construction of Erdos, Frankl and Rodl of a large 3-hypergraph with ... more >>>

TR01-079 | 6th September 2001
Michele Zito

An Upper Bound on the Space Complexity of Random Formulae in Resolution

We prove that, with high probability, the space complexity of refuting a random unsatisfiable boolean formula in $k$-CNF on $n$ variables and $m = \Delta n$ clauses is $O(n \cdot \Delta^{-\frac{1}{k-2}})$. more >>>

TR97-052 | 11th November 1997
Eduardo D. Sontag

Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages

We consider recurrent analog neural nets where the output of each gate is subject to Gaussian noise, or any other common noise distribution that is nonzero on a large set. We show that many regular languages cannot be recognized by networks of this type, and we give a precise characterization ... more >>>

TR95-025 | 8th May 1995
Günter Hotz, Gero Vierke, Bjoern Schieffer

Analytic Machines

Comments: 1

In this paper the $R$-machines defined by Blum, Shub and Smale are generalized by allowing infinite convergent computations. The description of real numbers is infinite. Therefore, considering arithmetic operations on real numbers should also imply infinite computations on {\em analytic machines}. We prove that $\R$-computable functions are $\Q$-analytic. We show ... more >>>

TR05-025 | 20th February 2005
Zeev Dvir, Ran Raz

Analyzing Linear Mergers

TR97-045 | 29th September 1997
Oded Goldreich, David Zuckerman

Another proof that BPP subseteq PH (and more).

Comments: 1

We provide another proof of the Sipser--Lautemann Theorem by which $BPP\subseteq MA$ ($\subseteq PH$). The current proof is based on strong results regarding the amplification of $BPP$, due to Zuckerman. Given these results, the current proof is even simpler than previous ones. Furthermore, extending the proof leads to two results ... more >>>

TR06-143 | 15th November 2006
Frank Neumann, Carsten Witt

Ant Colony Optimization and the Minimum Spanning Tree Problem

Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>>

TR00-052 | 3rd July 2000
Beate Bollig, Ingo Wegener

Approximability and Nonapproximability by Binary Decision Diagrams

Many BDD (binary decision diagram) models are motivated by CAD applications and have led to complexity theoretical problems and results. Motivated by applications in genetic programming Krause, Savick\'y, and Wegener (1999) have shown that for the inner product function IP$_n$ and the direct storage access function DSA$_n$ all functions which ... 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 >>>

TR03-056 | 29th July 2003
Piotr Berman, Marek Karpinski

Approximability of Hypergraph Minimum Bisection

We prove that the problems of minimum bisection on k-uniform hypergraphs are almost exactly as hard to approximate, up to the factor k/3, as the problem of minimum bisection on graphs. On a positive side, our argument gives also the first approximation algorithms for the problem of minimum bisection on ... more >>>

TR06-045 | 13th March 2006
Jan Arpe, Bodo Manthey

Approximability of Minimum AND-Circuits

Revisions: 1

Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not polynomial time approximable within a factor of less than 1.0051 unless P = NP, even if ... more >>>

TR02-031 | 30th April 2002
Vikraman Arvind, Venkatesh Raman

Approximate Counting small subgraphs of bounded treewidth and related problems

Revisions: 1

We give a randomized approximation algorithm taking $O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a $k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph $G$ with approximation ratio $1/k^{O(k)}$ and error probability inverse exponential in $n$. This algorithm is based on the Karp-Luby approximate counting ... more >>>

TR07-116 | 25th September 2007
Alexander A. Sherstov

Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

Comments: 1

Let A_1,...,A_n be events in a probability space. The approximate inclusion-exclusion problem, due to Linial and Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve this problem optimally for each k. We study the following more general question: ... more >>>

TR10-032 | 19th January 2010
Jack H. Lutz, Brad Shutters

Approximate Self-Assembly of the Sierpinski Triangle

The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex (typically aperiodic) DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in ... more >>>

TR05-073 | 14th July 2005
Oded Goldreich, Dana Ron

Approximating Average Parameters of Graphs.

Inspired by Feige ({\em 36th STOC}, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these ... 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 >>>

TR06-007 | 23rd November 2005
MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

Approximating Buy-at-Bulk $k$-Steiner trees

In the buy-at-bulk $k$-Steiner tree (or rent-or-buy $k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set of terminals $T\subseteq V$ including a particular vertex $s$ called the root, and an integer $k\leq |T|$. There are two cost functions on the edges of $G$, a buy cost $b:E\longrightarrow ... more >>>

TR07-027 | 2nd February 2007
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject. We consider the approximation ability of randomized search for the class of covering ... more >>>

TR98-048 | 6th July 1998
Irit Dinur, Guy Kindler, Shmuel Safra

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

This paper shows finding the closest vector in a lattice to be NP-hard to approximate to within any factor up to $2^{(\log{n})^{1-\epsilon}}$ where $\epsilon = (\log\log{n})^{-\alpha}$ and $\alpha$ is any positive constant $<{1\over 2}$. more >>>

TR97-004 | 19th February 1997
Marek Karpinski, Alexander Zelikovsky

Approximating Dense Cases of Covering Problems

Comments: 1

We study dense instances of several covering problems. An instance of the set cover problem with $m$ sets is dense if there is $\epsilon>0$ such that any element belongs to at least $\epsilon m$ sets. We show that the dense set cover problem can be approximated with the performance ratio ... more >>>

TR02-018 | 22nd March 2002
Piotr Berman, Marek Karpinski, Yakov Nekrich

Approximating Huffman Codes in Parallel

In this paper we present some new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our ... more >>>

TR00-072 | 14th July 2000
Peter Auer, Philip M. Long, Aravind Srinivasan

Approximating Hyper-Rectangles: Learning and Pseudo-random Sets

The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles have been actively studied recently because (i) they are a subproblem common to the derandomization of depth-2 (DNF) circuits and derandomizing Randomized ... more >>>

TR03-032 | 16th April 2003
Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

Approximating Longest Directed Path

We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on $n$ vertices. We show that neither of these two problems can be polynomial time approximated within $n^{1-\epsilon}$ for any $\epsilon>0$ unless $\text{P}=\text{NP}$. In particular, the result holds for digraphs of constant bounded outdegree ... 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-038 | 14th May 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

Approximating Schedules for Dynamic Graphs Efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very ... more >>>

TR99-002 | 22nd January 1999
Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

We show that given oracle access to a subroutine which returns approximate closest vectors in a lattice, one may find in polynomial-time approximate shortest vectors in a lattice. The level of approximation is maintained; that is, for any function $f$, the following holds: Suppose that the subroutine, on input a ... more >>>

TR99-016 | 25th April 1999
Irit Dinur

Approximating SVP_\infty to within Almost-Polynomial Factors is NP-hard

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate to within any factor up to $n^{1/\log\log n}$. This improves on the best previous result \cite{ABSS} that showed quasi-NP-hardness for smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant $\epsilon>0$. We show a direct reduction from SAT to these problems, that ... more >>>

TR05-084 | 31st July 2005
Mickey Brautbar, Alex Samorodnitsky

Approximating the entropy of large alphabets

We consider the problem of approximating the entropy of a discrete distribution P on a domain of size q, given access to n independent samples from the distribution. It is known that n > q is necessary, in general, for a good additive estimate of the entropy. A problem of ... more >>>

TR07-092 | 10th July 2007
Piotr Berman, Bhaskar DasGupta

Approximating the Online Set Multicover Problems Via Randomized Winnowing

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family SS of subsets of V with a positive real cost for every S\in SS, and a ``coverage factor'' (positive integer) k. A subset \{i_0,i_1,\ldots\ \subseteq V of ... more >>>

TR97-059 | 22nd December 1997
Jin-Yi Cai, Ajay Nerurkar

Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

Recently Ajtai showed that to approximate the shortest lattice vector in the $l_2$-norm within a factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large constant $k$, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor $(1+ \mbox{dim}^{-\epsilon})$, for any $\epsilon>0$, ... more >>>

TR07-119 | 5th December 2007
Piotr Berman, Bhaskar DasGupta, Marek Karpinski

Approximating Transitive Reductions for Directed Networks

We consider minimum equivalent digraph (directed network) problem (also known as the strong transitive reduction), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>>

TR06-063 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Approximation Algorithm for the Max k-CSP Problem

We present a c.k/2^k approximation algorithm for the Max k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Omega(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up ... more >>>

TR00-051 | 14th July 2000
Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree $k$-regular graphs for $3\le k\le 8,$ ... more >>>

TR05-034 | 5th April 2005
Luca Trevisan

Approximation Algorithms for Unique Games

Revisions: 1 , Comments: 1

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an ... more >>>

TR06-101 | 22nd August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Approximation Complexity of Nondense Instances of MAX-CUT

We prove existence of approximation schemes for instances of MAX-CUT with $\Omega(\frac{n^2}{\Delta})$ edges which work in $2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$ time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with $\Omega(\frac{n^2}{\operatorname{polylog} n})$ edges. The result depends on new sampling method for smoothed linear programs that ... more >>>

TR96-030 | 31st March 1996
Meera Sitharam

Approximation from linear spaces and applications to complexity

We develop an analytic framework based on linear approximation and point out how a number of complexity related questions -- on circuit and communication complexity lower bounds, as well as pseudorandomness, learnability, and general combinatorics of Boolean functions -- fit neatly into this framework. This isolates the analytic content of ... 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 >>>

TR02-073 | 12th December 2002
Janka Chlebíková, Miroslav Chlebík

Approximation Hardness for Small Occurrence Instances of NP-Hard Problem

The paper contributes to the systematic study (started by Berman and Karpinski) of explicit approximability lower bounds for small occurrence optimization problems. We present parametrized reductions for some packing and covering problems, including 3-Dimensional Matching, and prove the best known inapproximability results even for highly restricted versions of them. For ... 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 >>>

TR03-049 | 25th June 2003
Piotr Berman, Marek Karpinski, Alexander D. Scott

Approximation Hardness of Short Symmetric Instances of MAX-3SAT

We prove approximation hardness of short symmetric instances of MAX-3SAT in which each literal occurs exactly twice, and each clause is exactly of size 3. We display also an explicit approximation lower bound for that problem. The bound two on the number of occurrences of literals in symmetric MAX-3SAT is ... 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-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 >>>

TR06-124 | 25th September 2006
Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Approximation of Global MAX-CSP Problems

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

TR08-009 | 7th December 2007
Per Austrin, Elchanan Mossel

Approximation Resistant Predicates From Pairwise Independence

We study the approximability of predicates on $k$ variables from a domain $[q]$, and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate $P$ is approximation resistant if there exists a balanced pairwise independent distribution over ... more >>>

TR01-065 | 10th August 2001
Chandra Chekuri, Sanjeev Khanna

Approximation Schemes for Preemptive Weighted Flow Time

We present the first approximation schemes for minimizing weighted flow time on a single machine with preemption. Our first result is an algorithm that computes a $(1+\eps)$-approximate solution for any instance of weighted flow time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio of maximum job processing ... more >>>

TR06-074 | 24th April 2006
Shahar Dobzinski, Noam Nisan

Approximations by Computationally-Efficient VCG-Based Mechanisms

We consider computationally-efficient incentive-compatible mechanisms that use the VCG payment scheme, and study how well they can approximate the social welfare in auction settings. We obtain a $2$-approximation for multi-unit auctions, and show that this is best possible, even though from a purely computational perspective an FPTAS exists. For combinatorial ... more >>>

TR99-011 | 14th April 1999
Matthias Krause, Petr Savicky, Ingo Wegener

Approximations by OBDDs and the variable ordering problem

Ordered binary decision diagrams (OBDDs) and their variants are motivated by the need to represent Boolean functions in applications. Research concerning these applications leads also to problems and results interesting from theoretical point of view. In this paper, methods from communication complexity and information theory are combined to prove that ... more >>>

TR09-114 | 13th November 2009
Emanuele Viola

Are all distributions easy?

Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits. Our main results are: \begin{itemize} \item There are explicit $AC^0$ circuits of ... more >>>

TR09-089 | 26th September 2009
Guy Rothblum, Salil Vadhan

Are PCPs Inherent in Efficient Arguments?

Starting with Kilian (STOC `92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs ... more >>>

TR09-057 | 23rd June 2009
Yonatan Bilu, Nathan Linial

Are stable instances easy?

We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then arises whether stable instances of NP--hard problems are easier to solve. In particular, whether there exist algorithms that solve correctly ... more >>>

TR09-026 | 17th February 2009
Vikraman Arvind, Pushkar Joglekar

Arithmetic Circuit Size, Identity Testing, and Finite Automata

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial ring over a field $\F$, where the $x_i$'s are free noncommuting formal variables. Given a finite automaton $\A$ with the $x_i$'s as alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$ obtained by natural operations that we call \emph{intersecting} and \emph{quotienting} the ... more >>>

TR08-048 | 8th April 2008
Meena Mahajan, B. V. Raghavendra Rao

Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae

Functions in arithmetic NC1 are known to have equivalent constant width polynomial degree circuits, but the converse containment is unknown. In a partial answer to this question, we show that syntactic multilinear circuits of constant width and polynomial degree can be depth-reduced, though the resulting circuits need not be syntactic ... 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 >>>

TR99-008 | 19th March 1999
Eric Allender, Vikraman Arvind, Meena Mahajan

Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1

The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC^1 and GapL. More precisely, we apply the Kleene closure of languages and the formal power series operations of inversion and root extraction to these complexity classes. ... 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 >>>

TR07-087 | 11th July 2007
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Arithmetizing classes around NC^1 and L

The parallel complexity class NC^1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. \cite{CMTV} considered arithmetizations of two of these classes, #NC^1 and #BWBP. We further this study to include arithmetization of other classes. In particular, we show that counting paths ... more >>>

TR09-055 | 10th June 2009
Venkatesan Chakaravarthy, Sambuddha Roy

Arthur and Merlin as Oracles

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class. Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ... more >>>

TR97-054 | 17th November 1997
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin

Arthur-Merlin Games in Boolean Decision Trees

It is well known that probabilistic boolean decision trees cannot be much more powerful than deterministic ones (N.~Nisan, SIAM Journal on Computing, 20(6):999--1007, 1991). Motivated by a question if randomization can significantly speed up a nondeterministic computation via a boolean decision tree, we address structural properties of Arthur-Merlin games in ... more >>>

TR09-001 | 26th November 2008
Venkatesan Guruswami

Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes

Algebraic codes that achieve list decoding capacity were recently constructed by a careful ``folding'' of the Reed-Solomon code. The ``low-degree'' nature of this folding operation was crucial to the list decoding algorithm. We show how such folding schemes conducive to list decoding arise out of the Artin-Frobenius automorphism at primes ... more >>>

TR03-038 | 15th May 2003
Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

Asymmetric k-center is log^*n-hard to Approximate

We show that the asymmetric $k$-center problem is $\Omega(\log^* n)$-hard to approximate unless ${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$. Since an $O(\log^* n)$-approximation algorithm is known for this problem, this essentially resolves the approximability of this problem. This is the first natural problem whose approximability threshold does not polynomially ... 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 >>>

TR95-026 | 7th June 1995
Claus-Peter Schnorr, Horst Helmut Hoerner

Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

We introduce new algorithms for lattice basis reduction that are improvements of the LLL-algorithm. We demonstrate the power of these algorithms by solving random subset sum problems of arbitrary density with 74 and 82 many weights, by breaking the Chor-Rivest cryptoscheme in dimensions 103 and 151 and by breaking Damgard's ... more >>>

TR98-076 | 13th November 1998
Nader H. Bshouty, Jeffrey J. Jackson, Christino Tamon

Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

We study attribute efficient learning in the PAC learning model with membership queries. First, we give an {\it attribute efficient} PAC-learning algorithm for DNF with membership queries under the uniform distribution. Previous algorithms for DNF have sample size polynomial in the number of attributes $n$. Our algorithm is the first ... more >>>

TR05-011 | 21st December 2004
Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

Autoreducibility, Mitoticity, and Immunity

We show the following results regarding complete sets: NP-complete sets and PSPACE-complete sets are many-one autoreducible. Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are many-one autoreducible. EXP-complete sets are many-one mitotic. NEXP-complete sets are weakly many-one mitotic. PSPACE-complete sets are weakly Turing-mitotic. If ... more >>>

TR95-019 | 14th April 1995
Jin-Yi Cai, Alan L. Selman

Average time complexity classes

more >>>

TR06-073 | 8th June 2006
Andrej Bogdanov, Luca Trevisan

Average-Case Complexity

Revisions: 1

We survey the theory of average-case complexity, with a focus on problems in NP. more >>>

TR03-031 | 8th April 2003
Birgit Schelm

Average-Case Complexity Theory of Approximation Problems

Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>>

TR98-037 | 29th June 1998
Johannes Köbler, Rainer Schuler

Average-Case Intractability vs. Worst-Case Intractability

We use the assumption that all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms to derive collapse consequences for MA, AM, and various subclasses of P/poly. As a further consequence we show for C in {P(PP), PSPACE} that C is not tractable in the ... more >>>

ISSN 1433-8092 | Imprint