Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2005:
All reports in year 2005:
TR05-001 | 1st January 2005
Mario Szegedy

#### Near optimality of the priority sampling procedure

Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured
that the variance of their highly successful priority sampling procedure
is not larger than the variance of the threshold sampling procedure with sample size one smaller.
The conjecture's significance is that the latter procedure is provably optimal ... more >>>

TR05-002 | 6th January 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

#### Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

We give a new method for analysing the mixing time of a Markov chain using
path coupling with stopping times. We apply this approach to two hypergraph
problems. We show that the Glauber dynamics for independent sets in a
hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ... more >>>

TR05-003 | 23rd December 2004
Scott Aaronson

#### Quantum Computing, Postselection, and Probabilistic Polynomial-Time

I study the class of problems efficiently solvable by a quantum computer, given the ability to "postselect" on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or Probabilistic Polynomial-Time. Using this result, I show that several simple changes to the axioms ... more >>>

TR05-004 | 3rd January 2005
Leslie G. Valiant

#### Memorization and Association on a Realistic Neural Model

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This paper addresses the simultaneous challenges of realizing these two distinct tasks with the same data ... more >>>

TR05-005 | 20th December 2004
Tomas Feder

#### Constraint Satisfaction on Finite Groups with Near Subgroups

Constraint satisfaction on finite groups, with subgroups and their cosets
described by generators, has a polynomial time algorithm. For any given
group, a single additional constraint type that is not a coset of a near
subgroup makes the problem NP-complete. We consider constraint satisfaction on
groups with subgroups, near subgroups, ... more >>>

TR05-006 | 28th December 2004
Edward Hirsch, Sergey I. Nikolenko

#### Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Goerdt (1991) considered a weakened version of the Cutting Plane proof system with a restriction on the degree of falsity of intermediate inequalities. (The degree of falsity of an inequality written in the form $\sum a_ix_i+\sum b_i(1-x_i)\ge c,\ a_i,b_i\ge0$ is its constant term $c$.) He proved a superpolynomial lower bound ... more >>>

TR05-007 | 15th December 2004

#### On Random High Density Subset Sums

In the Subset Sum problem, we are given n integers a_1,...,a_n
and a target number t, and are asked to find the subset of the
a_i's such that the sum is t. A version of the subset sum
problem is the Random Modular Subset Sum problem. In this version,
the ... more >>>

TR05-008 | 11th December 2004
Neeraj Kayal

#### Recognizing permutation functions in polynomial time.

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.
The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on
the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map
$f : \mathbb{F}_q ... 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 >>> 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 >>> 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. ... more >>> TR05-012 | 17th January 2005 Luca Trevisan, Salil Vadhan, David Zuckerman #### Compression of Samplable Sources We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n). 1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1). Our next ... more >>> TR05-013 | 22nd December 2004 Bin Fu #### Theory and Application of Width Bounded Geometric Separator We introduce the notion of width bounded geometric separator, develop the techniques for its existence as well as algorithm, and apply it to obtain a$2^{O(\sqrt{n})}$time exact algorithm for the disk covering problem, which seeks to determine the minimal number of fixed size disks to cover$n$points on ... more >>> TR05-014 | 30th January 2005 Oded Goldreich #### Short Locally Testable Codes and Proofs (Survey) We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Locally testability refers to approximately testing large objects based on a very small number of probes, each retrieving a single bit in the ... more >>> TR05-015 | 27th January 2005 Andrej Bogdanov, Luca Trevisan #### On Worst-Case to Average-Case Reductions for NP Problems We show that if an NP-complete problem has a non-adaptive self-corrector with respect to a samplable distribution then coNP is contained in NP/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion under the stronger assumption that an more >>> TR05-016 | 13th January 2005 Tomas Feder, Daniel Ford #### Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection Matroid intersection has a known polynomial time algorithm using an oracle. We generalize this result to delta-matroids that do not have equality as a restriction, and give a polynomial time algorithm for delta-matroid intersection on delta-matroids without equality using an oracle. We note that when equality is present, delta-matroid intersection more >>> TR05-017 | 28th January 2005 Phong Nguyen #### Two-Sorted Theories for L, SL, NL and P We introduce minimal'' two--sorted first--order theories VL, VSL, VNL and VP that characterize the classes L, SL, NL and P in the same way that Buss's$S^i_2$hierarchy characterizes the polynomial time hierarchy. Our theories arise from natural combinatorial problems, namely the st-Connectivity Problem and the Circuit Value Problem. It ... more >>> TR05-018 | 6th February 2005 Oded Goldreich #### On Promise Problems (a survey in memory of Shimon Even [1935-2004]) The notion of promise problems was introduced and initially studied by Even, Selman and Yacobi (Information and Control, Vol.~61, pages 159-173, 1984). In this article we survey some of the applications that this notion has found in the twenty years that elapsed. These include the notion ... more >>> TR05-019 | 9th February 2005 Venkatesan Guruswami, Atri Rudra #### Tolerant Locally Testable Codes An error-correcting code is said to be {\em locally testable} if it has an efficient spot-checking procedure that can distinguish codewords from strings that are far from every codeword, looking at very few locations of the input in doing so. Locally testable codes (LTCs) have generated ... more >>> TR05-020 | 22nd November 2004 Sourav Chakraborty #### On the Sensitivity of Cyclically-Invariant Boolean Functions In this paper we construct a cyclically invariant Boolean function whose sensitivity is$\Theta(n^{1/3})$. This result answers two previously published questions. Tur\'an (1984) asked if any Boolean function, invariant under some transitive group of permutations, has sensitivity$\Omega(\sqrt{n})$. Kenyon and Kutin (2004) asked whether for a nice'' function the product ... more >>> TR05-021 | 14th February 2005 Stasys Jukna #### Disproving the single level conjecture Revisions: 2 , Comments: 1 We consider the minimal number of AND and OR gates in monotone circuits for quadratic boolean functions, i.e. disjunctions of length-$2$monomials. The single level conjecture claims that monotone single level circuits, i.e. circuits which have only one level of AND gates, for quadratic functions ... more >>> TR05-022 | 19th February 2005 Omer Reingold, Luca Trevisan, Salil Vadhan #### Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results. 1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>> TR05-023 | 16th February 2005 Robert H. Sloan, Balázs Szörényi, György Turán #### On k-term DNF with largest number of prime implicants It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>> TR05-024 | 8th February 2005 Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer #### Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>> TR05-025 | 20th February 2005 Zeev Dvir, Ran Raz #### Analyzing Linear 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 >>> TR05-026 | 15th February 2005 Scott Aaronson #### NP-complete Problems and Physical Reality Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The ... more >>> TR05-027 | 19th February 2005 Daniel Rolf #### Derandomization of PPSZ for Unique-$k$-SAT The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable$3$-SAT formulas can be found in expected running time at most$\Oc(1.3071^n).$Using the technique of limited independence, we can derandomize this algorithm yielding$\Oc(1.3071^n)$... more >>> TR05-028 | 12th February 2005 Elmar Böhler #### On the Lattice of Clones Below the Polynomial Time Functions A clone is a set of functions that is closed under generalized substitution. The set FP of functions being computable deterministically in polynomial time is such a clone. It is well-known that the set of subclones of every clone forms a lattice. We study the lattice below FP, which ... more >>> TR05-029 | 2nd March 2005 Frank Neumann, Marco Laumanns #### Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization Revisions: 1 We give faster approximation algorithms for the generalization of two NP-hard spanning tree problems. First, we investigate the problem of minimizing the degree of minimum spanning forests. The task is to compute for each number of connected components a minimum spanning forest whose degree is as small as possible. Fischer 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 >>> TR05-031 | 1st March 2005 Carme Alvarez, Joaquim Gabarro, Maria Serna #### Pure Nash equilibria in games with a large number of actions We study the computational complexity of deciding the existence of a Pure Nash Equilibrium in multi-player strategic games. We address two fundamental questions: how can we represent a game?, and how can we represent a game with polynomial pay-off functions? Our results show that the computational complexity of deciding ... more >>> TR05-032 | 16th March 2005 Gudmund Skovbjerg Frandsen, Peter Bro Miltersen #### Reviewing Bounds on the Circuit Size of the Hardest Functions In this paper we review the known bounds for$L(n)$, the circuit size complexity of the hardest Boolean function on$n$input bits. The best known bounds appear to be $$\frac{2^n}{n}(1+\frac{\log n}{n}-O(\frac{1}{n})) \leq L(n) \leq\frac{2^n}{n}(1+3\frac{\log n}{n}+O(\frac{1}{n}))$$ However, the bounds do not seem to be explicitly stated in the literature. We ... 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 >>> 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 >>> 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$. ... more >>> TR05-036 | 28th March 2005 Hubie Chen #### Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the quantified constraint satisfaction problem (QCSP), ... more >>> TR05-037 | 8th April 2005 Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen #### On the Complexity of Numerical Analysis Revisions: 1 , Comments: 1 We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis. We show that both hinge on the question of understanding the complexity of the following problem, which we call PosSLP: Given a division-free straight-line program producing an integer N, decide whether N>0. more >>> TR05-038 | 10th April 2005 Ran Raz #### Quantum Information and the PCP Theorem We show how to encode$2^n$(classical) bits$a_1,...,a_{2^n}$by a single quantum state$|\Psi \rangle$of size$O(n)$qubits, such that: for any constant$k$and any$i_1,...,i_k \in \{1,...,2^n\}$, the values of the bits$a_{i_1},...,a_{i_k}$can be retrieved from$|\Psi \rangle$by a one-round Arthur-Merlin interactive ... more >>> TR05-039 | 13th April 2005 Irit Dinur, Elchanan Mossel, Oded Regev #### Conditional Hardness for Approximate Coloring We study the approximate-coloring(q,Q) problem: Given a graph G, decide whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional hardness for this problem for any constant 3\le q < Q. For q \ge 4, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For q=3, we base our hardness ... more >>> TR05-040 | 13th April 2005 Scott Aaronson #### Oracles Are Subtle But Not Malicious Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper illustrates both that oracles can give us nontrivial insights about the barrier problems in circuit complexity, and that they need not prevent us from trying to solve those problems. First, we ... more >>> TR05-041 | 12th April 2005 Shengyu Zhang #### (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids Revisions: 2 The Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to many areas in computer science and natural sciences. In this paper, we show that for the Boolean hypercube$\B^n$, the randomized query complexity of Local more >>> TR05-042 | 15th April 2005 Lance Fortnow, Adam Klivans #### Linear Advice for Randomized Logarithmic Space Revisions: 1 We show that RL is contained in L/O(n), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To prove our result we show how to take an ultra-low space walk on the Gabber-Galil expander graph. more >>> TR05-043 | 5th April 2005 Emanuele Viola #### Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates We exhibit an explicitly computable pseudorandom' generator stretching$l$bits into$m(l) = l^{\Omega(\log l)}$bits that look random to constant-depth circuits of size$m(l)$with$\log m(l)$arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>> TR05-044 | 6th April 2005 Zeev Dvir, Amir Shpilka #### Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>> TR05-045 | 12th April 2005 Philippe Moser #### Martingale Families and Dimension in P Revisions: 1 We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families, that get rid of some drawbacks of previous measure notions: martingale families can make money on all strings, and yield random sequences with an equal frequency of 0's and 1's. As applications to F-measure, more >>> TR05-046 | 17th April 2005 Irit Dinur #### The PCP theorem by gap amplification Revisions: 1 , Comments: 3 Let C={c_1,...,c_n} be a set of constraints over a set of variables. The {\em satisfiability-gap} of C is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the variables. We prove a new combinatorial amplification lemma that doubles the satisfiability-gap of a constraint-system, with only a linear ... more >>> TR05-047 | 10th April 2005 Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri #### Weak Composite Diffie-Hellman is not Weaker than Factoring In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. ... more >>> TR05-048 | 11th April 2005 Moti Yung, Yunlei Zhao #### Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model Revisions: 3 We present constant-round concurrently secure (sound) resettable zero-knowledge (rZK-CS) arguments in the bare public-key (BPK) model. Our constructions deal with general NP ZK-arguments as well as with highly efficient ZK-arguments for number-theoretic languages, most relevant to identification scenarios. These are the first constant-round protocols of ... more >>> TR05-049 | 1st April 2005 Joan Boyar, rene peralta #### The Exact Multiplicative Complexity of the Hamming Weight Function We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>> TR05-050 | 18th April 2005 Uriel Feige, Eran Ofek #### Finding a Maximum Independent Set in a Sparse Random Graph Revisions: 1 We consider the problem of finding a maximum independent set in a random graph. The random graph$G$is modelled as follows. Every edge is included independently with probability$\frac{d}{n}$, where$d$is some sufficiently large constant. Thereafter, for some constant$\alpha$, a subset$I$of$\alpha n$vertices is ... more >>> TR05-051 | 18th March 2005 Predrag Tosic #### On Complexity of Counting Fixed Points in Certain Classes of Graph Automata Revisions: 2 We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>> TR05-052 | 5th May 2005 Grant Schoenebeck, Salil Vadhan #### The Computational Complexity of Nash Equilibria in Concisely Represented Games Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number ... more >>> TR05-053 | 4th May 2005 Paul Beame, Nathan Segerlind #### Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>> TR05-054 | 19th May 2005 Konstantin Pervyshev #### Time Hierarchies for Computations with a Bit of Advice A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1. The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>> TR05-055 | 19th May 2005 Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye #### Leontief Economies Encode Nonzero Sum Two-Player Games We give a reduction from any two-player game to a special case of the Leontief exchange economy, with the property that the Nash equilibria of the game and the equilibria of the market are in one-to-one correspondence. Our reduction exposes a potential hurdle inherent in solving certain families of market ... more >>> TR05-056 | 25th April 2005 Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis #### The Price of Optimum in Stackelberg Games Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>> TR05-057 | 19th May 2005 Venkatesan Guruswami, Valentine Kabanets #### Hardness amplification via space-efficient direct products We prove a version of the derandomized Direct Product Lemma for deterministic space-bounded algorithms. Suppose a Boolean function$g:\{0,1\}^n\to\{0,1\}$cannot be computed on more than$1-\delta$fraction of inputs by any deterministic time$T$and space$S$algorithm, where$\delta\leq 1/t$for some$t$. Then, for$t$-step walks$w=(v_1,\dots, v_t)$... more >>> TR05-058 | 24th May 2005 Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra #### On Non-Approximability for Quadratic Programs This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find$x \in \{-1,+1\}^n$that maximizes$x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ... more >>> TR05-059 | 9th May 2005 Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien #### Tractable Clones of Polynomials over Semigroups It is well known that coset-generating relations lead to tractable constraint satisfaction problems. These are precisely the relations closed under the operation$xy^{-1}z$where the multiplication is taken in some finite group. Bulatov et al. have on the other hand shown that any clone containing the multiplication of some block-group'' ... more >>> TR05-060 | 30th May 2005 Philippe Moser #### Generic Density and Small Span Theorem We refine the genericity concept of Ambos-Spies et al, by assigning a real number in$[0,1]$to every generic set, called its generic density. We construct sets of generic density any E-computable real in$[0,1]$. We also introduce strong generic density, and show that it is related to packing ... more >>> TR05-061 | 15th June 2005 Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma #### On the Error Parameter of Dispersers Optimal dispersers have better dependence on the error than optimal extractors. In this paper we give explicit disperser constructions that beat the best possible extractors in some parameters. Our constructions are not strong, but we show that having such explicit strong constructions implies a solution to the Ramsey graph construction ... more >>> TR05-062 | 17th June 2005 A. Pavan, Vinodchandran Variyam #### 2-Local Random Reductions to 3-Valued Functions Yao (in a lecture at DIMACS Workshop on structural complexity and cryptography) showed that if a language L is 2-locally-random reducible to a Boolean functio, then L is in PSPACE/poly. Fortnow and Szegedy quantitatively improved Yao's result to show that such languages are in fact in NP/poly (Information Processing Letters, ... more >>> TR05-063 | 24th June 2005 Bodo Manthey, Rüdiger Reischuk #### Smoothed Analysis of the Height of Binary Search Trees Revisions: 2 Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average case ... more >>> TR05-064 | 26th June 2005 Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani #### On earthmover distance, metric labeling, and 0-extension We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>> TR05-065 | 26th June 2005 Alexander Barvinok, Alex Samorodnitsky #### Random Weighting, Asymptotic Counting, and Inverse Isoperimetry For a family X of k-subsets of the set 1...n, let |X| be the cardinality of X and let Gamma(X, mu) be the expected maximum weight of a subset from X when the weights of 1...n are chosen independently at random from a symmetric probability distribution mu on R. We ... more >>> TR05-066 | 4th June 2005 Jakob Nordström #### Narrow Proofs May Be Spacious: Separating Space and Width in Resolution Revisions: 2 , Comments: 1 The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>> 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 >>> TR05-068 | 7th July 2005 Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang #### Redundancy in Complete Sets We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>> TR05-069 | 11th July 2005 Piotr Berman, Marek Karpinski #### 8/7-Approximation Algorithm for (1,2)-TSP Revisions: 2 We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor of 7/6 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarily ... more >>> TR05-070 | 6th July 2005 Mahdi Cheraghchi #### On Matrix Rigidity and the Complexity of Linear Forms The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>> TR05-071 | 29th June 2005 Marius Zimand #### Simple extractors via constructions of cryptographic pseudo-random generators Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) can be used for building extractors as well. Using this new technique we build extractors that ... more >>> TR05-072 | 11th July 2005 Christian Glaßer, Alan L. Selman, Liyu Zhang #### Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus. 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, ... more >>> TR05-074 | 8th June 2005 Li-Sha Huang, Xiaotie Deng #### On Complexity of Market Equilibria with Maximum Social Welfare We consider the computational complexity of the market equilibrium problem by exploring the structural properties of the Leontief exchange economy. We prove that, for economies guaranteed to have a market equilibrium, finding one with maximum social welfare or maximum individual welfare is NP-hard. In addition, we prove that counting the ... more >>> TR05-075 | 4th July 2005 Martin Dyer, Leslie Ann Goldberg, Mark Jerrum #### Dobrushin conditions and Systematic Scan Revisions: 1 We consider Glauber dynamics on finite spin systems. The mixing time of Glauber dynamics can be bounded in terms of the influences of sites on each other. We consider three parameters bounding these influences ---$\alpha$, the total influence on a site, as studied by Dobrushin;$\alpha'$, the total influence ... more >>> TR05-076 | 2nd July 2005 Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev #### Time hierarchies for cryptographic function inversion with advice We prove a time hierarchy theorem for inverting functions computable in polynomial time with one bit of advice. In particular, we prove that if there is a strongly one-way function, then for any k and for any polynomial p, there is a function f computable in linear time with one ... more >>> TR05-077 | 15th July 2005 Zenon Sadowski #### On a D-N-optimal acceptor for TAUT The notion of an optimal acceptor for TAUT (the optimality property is stated only for input strings from TAUT) comes from the line of research aimed at resolving the question of whether optimal propositional proof systems exist. In this paper we introduce two new types of optimal acceptors, a D-N-optimal ... 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 >>> TR05-079 | 25th July 2005 Stasys Jukna #### Expanders and time-restricted branching programs The \emph{replication number} of a branching program is the minimum number R such that along every accepting computation at most R variables are tested more than once. Hence 0\leq R\leq n for every branching program in n variables. The best results so far were exponential ... more >>> TR05-080 | 21st July 2005 Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider #### Proving NP-hardness for clique-width I: non-approximability of sequential clique-width Revisions: 1 Clique-width is a graph parameter, defined by a composition mechanism for vertex-labeled graphs, which measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic, that includes NP-hard problems) can be solved efficiently for graphs of certified small clique-width. It ... more >>> TR05-081 | 21st July 2005 Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider #### Proving NP-hardness for clique-width II: non-approximability of clique-width Revisions: 1 Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) can be solved efficiently for graphs of certified small clique-width. It is widely ... more >>> TR05-082 | 3rd June 2005 Jorge Castro #### On the Query Complexity of Quantum Learners This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general ... more >>> TR05-083 | 24th July 2005 Olaf Beyersdorff #### Disjoint NP-Pairs from Propositional Proof Systems For a proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make the previously defined canonical NP-pairs of these proof systems hard ... 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 >>> TR05-085 | 5th August 2005 Asaf Shapira, Noga Alon #### Homomorphisms in Graph Property Testing - A Survey Property-testers are fast randomized algorithms for distinguishing between graphs (and other combinatorial structures) satisfying a certain property, from those that are far from satisfying it. In many cases one can design property-testers whose running time is in fact {\em independent} of the size of the input. In this paper we more >>> TR05-086 | 14th August 2005 Dana Moshkovitz, Ran Raz #### Sub-Constant Error Low Degree Test of Almost Linear Size Revisions: 1 Given a function f:F^m \rightarrow F over a finite field F, a low degree tester tests its proximity to an m-variate polynomial of total degree at most d over F. The tester is usually given access to an oracle A providing the supposed restrictions of f to affine subspaces of ... more >>> TR05-087 | 9th August 2005 Alexander Healy, Emanuele Viola #### Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two We study the complexity of arithmetic in finite fields of characteristic two,$\F_{2^n}$. We concentrate on the following two problems: Iterated Multiplication: Given$\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute$\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$. Exponentiation: Given$\alpha \in \F_{2^n}$and a$t$-bit integer$k$, compute$\alpha^k \in \F_{2^n}$. ... more >>> TR05-088 | 3rd August 2005 Jan Arpe #### Learning Juntas in the Presence of Noise The combination of two major challenges in machine learning is investigated: dealing with large amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that depend on a small number of variables---so-called juntas---can be learned efficiently from random examples corrupted by random ... more >>> TR05-089 | 30th July 2005 Xiaoyang Gu, Jack H. Lutz, Philippe Moser #### Dimensions of Copeland-Erdos Sequences The base-$k${\em Copeland-Erd\"os sequence} given by an infinite set$A$of positive integers is the infinite sequence$\CE_k(A)$formed by concatenating the base-$k$representations of the elements of$A$in numerical order. This paper concerns the following four quantities. \begin{enumerate}[$\bullet$] \item The {\em finite-state dimension}$\dimfs (\CE_k(A))$, a finite-state ... more >>> TR05-090 | 17th August 2005 Paul Goldberg, Christos H. Papadimitriou #### Reducibility Among Equilibrium Problems We address the fundamental question of whether the Nash equilibria of a game can be computed in polynomial time. We describe certain efficient reductions between this problem for normal form games with a fixed number of players and graphical games with fixed degree. Our main result is that ... more >>> TR05-091 | 11th August 2005 Predrag Tosic #### Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs Revisions: 1 We study counting various types of con gurations in certain classes of graph automata viewed as discrete dynamical systems. The graph automata models of our interest are Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively). These models have been proposed as a mathematical foun- dation for a theory of ... more >>> TR05-092 | 23rd August 2005 Eyal Rozenman, Salil Vadhan #### Derandomized Squaring of Graphs We introduce a "derandomized" analogue of graph squaring. This operation increases the connectivity of the graph (as measured by the second eigenvalue) almost as well as squaring the graph does, yet only increases the degree of the graph by a constant factor, instead of squaring the degree. One application of ... more >>> TR05-093 | 24th August 2005 Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan #### Concurrent Zero Knowledge without Complexity Assumptions We provide <i>unconditional</i> constructions of <i>concurrent</i> statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (<b>coNP</b> forms of the) Shortest Vector ... more >>> TR05-094 | 9th August 2005 Michal Parnas, Dana Ron #### On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms Revisions: 1 We consider the problem of estimating the size,$VC(G)$, of a minimum vertex cover of a graph$G$, in sublinear time, by querying the incidence relation of the graph. We say that an algorithm is an$(\alpha,\eps)$-approximation algorithm if it outputs with high probability an estimate$\widehat{VC}$such that ... more >>> TR05-095 | 26th August 2005 Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin #### Partitioning multi-dimensional sets in a small number of uniform'' parts Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>> TR05-096 | 26th August 2005 Boaz Barak, Amit Sahai #### How To Play Almost Any Mental Game Over The Net --- Concurrent Composition via Super-Polynomial Simulation We construct a secure protocol for any multi-party functionality that remains secure (under a relaxed definition of security) when executed concurrently with multiple copies of itself and other protocols. We stress that we do *not* use any assumptions on existence of trusted parties, common reference string, honest majority or synchronicity ... more >>> TR05-097 | 31st August 2005 Jens Groth, Rafail Ostrovsky, Amit Sahai #### Perfect Non-Interactive Zero Knowledge for NP Non-interactive zero-knowledge (NIZK) systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various cryptographic protocols. What makes them especially attractive, is that they work equally well in a concurrent setting, which is notoriously hard for interactive zero-knowledge protocols. However, while for interactive zero-knowledge we ... more >>> TR05-098 | 4th September 2005 Oded Goldreich #### Bravely, Moderately: A Common Theme in Four Recent Results We highlight a common theme in four relatively recent works that establish remarkable results by an iterative approach. Starting from a trivial construct, each of these works applies an ingeniously designed sequence of iterations that yields the desired result, which is highly non-trivial. Furthermore, in each iteration, more >>> TR05-099 | 9th September 2005 Leslie G. Valiant #### Holographic Algorithms Complexity theory is built fundamentally on the notion of efficient reduction among computational problems. Classical reductions involve gadgets that map solution fragments of one problem to solution fragments of another in one-to-one, or possibly one-to-many, fashion. In this paper we propose a new kind of reduction that allows for gadgets ... more >>> TR05-100 | 30th August 2005 David Zuckerman #### Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>> TR05-101 | 20th September 2005 Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel #### Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of$\GW + \eps$, for all$\eps > 0$; here$\GW \approx .878567$denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>> TR05-102 | 13th September 2005 Evgeny Dantsin, Edward Hirsch, Alexander Wolpert #### Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... 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 >>> TR05-104 | 16th September 2005 Don Coppersmith, Atri Rudra #### On the Robust Testability of Product of Codes Ben-Sasson and Sudan in~\cite{BS04} asked if the following test is robust for the tensor product of a code with another code-- pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that ... more >>> TR05-105 | 24th September 2005 Lance Fortnow, John Hitchcock, A. Pavan, Vinodchandran Variyam, Fengming Wang #### Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws We apply recent results on extracting randomness from independent sources to extract'' Kolmogorov complexity. For any$\alpha,
\epsilon > 0$, given a string$x$with$K(x) > \alpha|x|$, we show how to use a constant number of advice bits to efficiently compute another string$y$,$|y|=\Omega(|x|)$, with$K(y) >
\ar \B^m$which on ... more >>> TR05-110 | 3rd October 2005 Saurabh Sanghvi, Salil Vadhan #### The Round Complexity of Two-Party Random Selection We study the round complexity of two-party protocols for generating a random$n$-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's ... 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 ... more >>> TR05-112 | 12th September 2005 Eran Ofek #### On the expansion of the giant component in percolated$(n,d,\lambda)$graphs Revisions: 1 Let$d \geq d_0$be a sufficiently large constant. A$(n,d,c
\sqrt{d})$graph$G$is a$d$regular graph over$n$vertices whose second largest eigenvalue (in absolute value) is at most$c
a_i \cdot x_i$, where$\a = (a_1, \ldots, a_m)$consists of$m$elements from some ring$R$, and$\x = (x_1, \ldots, x_m)$consists of$m$coefficients from a specified subset$S \subseteq R$. Micciancio ... more >>> TR05-159 | 14th November 2005 Daniel Rolf #### Improved Bound for the PPSZ/Schöning-Algorithm for$3$-SAT The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable$3$-SAT formula can be found in expected running time at most$O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, Schöning proved ... more >>> TR05-160 | 10th December 2005 Xiaoyang Gu, Jack H. Lutz #### Dimension Characterizations of Complexity Classes We use derandomization to show that sequences of positive$\pspace$-dimension -- in fact, even positive$\Delta^\p_k$-dimension for suitable$k$-- have, for many purposes, the full power of random oracles. For example, we show that, if$S$is any binary sequence whose$\Delta^p_3$-dimension is positive, then$\BPP\subseteq \P^S\$ and, moreover, ... more >>>

TR05-161 | 13th December 2005
John Hitchcock

#### Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one ... more >>>

TR05-162 | 23rd December 2005
Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Feng Dengguo

#### Generic yet Practical ZK Arguments from any Public-Coin HVZK

Revisions: 1

In this work, we present a generic yet practical transformation from any public-coin honest-verifier zero-knowledge (HVZK) protocols to normal zero-knowledge (ZK) arguments. By generic", we mean that the transformation is applicable to any public-coin HVZK protocol under any one-way function (OWF) admitting Sigma-protocols. By practical" we mean that the transformation ... more >>>

TR05-163 | 19th December 2005
Dvir Falik, Alex Samorodnitsky

#### Edge-isoperimetric inequalities and influences

We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least Omega(log(n)/n).The methods of the proof are then used to recover additional isoperimetric results for the cube, with ... more >>>

ISSN 1433-8092 | Imprint