REPORTS > 2006:
All reports in year 2006:
TR06-001 | 1st January 2006
Ran Raz, Iddo Tzameret

#### The Strength of Multilinear Proofs

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

TR06-002 | 4th January 2006
Eyal Kaplan, Moni Naor, Omer Reingold

#### Derandomized Constructions of k-Wise (Almost) Independent Permutations

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>

TR06-003 | 8th January 2006
Joshua Buresh-Oppenheim, Rahul Santhanam

#### Making Hard Problems Harder

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

TR06-004 | 6th January 2006
Jesper Torp Kristensen, Peter Bro Miltersen

#### Finding small OBDDs for incompletely specified truth tables is hard

We present an efficient reduction mapping undirected graphs
G with n = 2^k vertices for integers k
to tables of partially specified Boolean functions
g: {0,1}^(4k+1) -> {0,1,*} so that for any integer m,
G has a vertex colouring using m colours if and only if g ... more >>>

TR06-005 | 13th December 2005
Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

#### Nash Equilibria in Graphical Games on Trees Revisited

Graphical games have been proposed as a game-theoretic model of large-scale
distributed networks of non-cooperative agents. When the number of players is
large, and the underlying graph has low degree, they provide a concise way to
represent the players' payoffs. It has recently been shown that the problem of
finding ... more >>>

TR06-006 | 16th December 2005
Alexander Shen

#### Multisource algorithmic information theory

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.

more >>>

TR06-007 | 23rd November 2005

#### 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 >>> TR06-008 | 23rd November 2005 MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour #### Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk We consider the non-uniform multicommodity buy-at-bulk network design problem. In this problem we are given a graph$G(V,E)$with two cost functions on the edges, a buy cost$b:E\longrightarrow \RR^+$and a rent cost$r:E\longrightarrow\RR^+$, and a set of source-sink pairs$s_i,t_i\in V$($1\leq i\leq \alpha$) with each pair$i$... more >>> TR06-009 | 10th January 2006 Nutan Limaye, Meena Mahajan, Jayalal Sarma #### Evaluating Monotone Circuits on Cylinders, Planes and Tori We re-examine the complexity of evaluating monotone planar circuits MPCVP, with special attention to circuits with cylindrical embeddings. MPCVP is known to be in NC^3, and for the special case of upward stratified circuits, it is known to be in LogDCFL. We characterize cylindricality, which ... more >>> TR06-010 | 1st December 2005 Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag #### Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs In this paper we consider the p-ary transitive reduction (TR<sub>p</sub>) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. ... 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 >>> TR06-012 | 17th January 2006 Bruno Codenotti, Mauro Leoncini, Giovanni Resta #### Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games It is known that finding a Nash equilibrium for win-lose bimatrix games, i.e., two-player games where the players' payoffs are zero and one, is complete for the class PPAD. We describe a linear time algorithm which computes a Nash equilibrium for win-lose bimatrix games where the number of winning positions ... more >>> TR06-013 | 24th January 2006 Luca Trevisan #### Pseudorandomness and Combinatorial Constructions In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science, probabilistic algorithms are sometimes simpler and more efficient than the best known ... more >>> TR06-014 | 20th December 2005 Argimiro Arratia, Carlos E. Ortiz #### On a syntactic approximation to logics that capture complexity classes We formulate a formal syntax of approximate formulas for the logic with counting quantifiers,$\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the following facts:$(i)$In the presence of a built--in (linear) order,$\mathcal{SOLP}$can describe {\bf NP}--complete problems and fragments of it capture classes like {\bf P} ... more >>> TR06-015 | 1st February 2006 Tomas Feder, Carlos Subi #### On Barnette's conjecture Barnette's conjecture is the statement that every 3-connected cubic planar bipartite graph is Hamiltonian. Goodey showed that the conjecture holds when all faces of the graph have either 4 or 6 sides. We generalize Goodey's result by showing that when the faces of such a graph are 3-colored, with adjacent ... more >>> TR06-016 | 1st February 2006 Tomas Feder, Carlos Subi #### Partition into$k$-vertex subgraphs of$k$-partite graphs The$H$-matching problem asks to partition the vertices of an input graph$G$into sets of size$k=|V(H)|$, each of which induces a subgraph of$G$isomorphic to$H$. The$H$-matching problem has been classified as polynomial or NP-complete depending on whether$k\leq 2$or not. We consider a variant more >>> TR06-017 | 12th January 2006 Toshiya Itoh #### Improved Lower Bounds for Families of$\varepsilon$-Approximate k$-Restricted Min-Wise Independent Permutations

A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer $n>0$, let $S_{n}$ be the family of al permutations on $[1,n]=\{1,2,\ldots, n\}$.
For any integer $k \in [1,n]$ and any real $\varepsilon >0$, we ... more >>>

TR06-018 | 8th February 2006
Jin-Yi Cai, Vinay Choudhary

#### On the Theory of Matchgate Computations

Valiant has proposed a new theory of algorithmic
computation based on perfect matchings and the Pfaffian.
We study the properties of {\it matchgates}---the basic
building blocks in this new theory. We give a set of
algebraic identities
which completely characterize these objects in terms of
the ... more >>>

TR06-019 | 24th November 2005
Janka Chlebíková, Miroslav Chlebík

#### Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)
proved that for
2-dimensional Orthogonal Rectangle
Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar
approximation hardness results hold for several rectangle packing and covering problems even if rotations by ninety
more >>>

TR06-020 | 10th February 2006
Akinori Kawachi, Tomoyuki Yamakami

#### Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Revisions: 1

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.
Our technical tool is ... more >>>

TR06-021 | 10th February 2006
Tomas Feder

#### Constraint satisfaction: a personal perspective

Attempts at classifying computational problems as polynomial time
solvable, NP-complete, or belonging to a higher level in the polynomial
hierarchy, face the difficulty of undecidability. These classes, including
NP, admit a logic formulation. By suitably restricting the formulation, one
finds the logic class MMSNP, or monotone monadic strict NP without
more >>>

TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

#### On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

We initiate the study of the compressibility of NP problems. We
consider NP problems that have long instances but relatively
short witnesses. The question is, can one efficiently compress an
instance and store a shorter representation that maintains the
information of whether the original input is in the language or
more >>>

TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

= O(\sqrt{\log n})$. The previously best known factor for any class of lattices was$\gamma(n) = \tilde{O}(n)$. To obtain our ... more >>> TR06-148 | 4th December 2006 Chris Peikert #### Limits on the Hardness of Lattice Problems in$\ell_p$Norms Revisions: 1 We show that for any$p \geq 2$, lattice problems in the$\ell_p$norm are subject to all the same limits on hardness as are known for the$\ell_2$norm. In particular, for lattices of dimension$n$: * Approximating the shortest and closest vector in ... more >>> TR06-149 | 7th December 2006 Lance Fortnow, Rakesh Vohra #### The Complexity of Forecast Testing Consider a weather forecaster predicting a probability of rain for the next day. We consider tests that given a finite sequence of forecast predictions and outcomes will either pass or fail the forecaster. Sandroni (2003) shows that any test which passes a forecaster who knows the distribution of nature, can ... more >>> TR06-150 | 4th December 2006 Patrick Briest #### Towards Hardness of Envy-Free Pricing We consider the envy-free pricing problem, in which we want to compute revenue maximizing prices for a set of products P assuming that each consumer from a set of consumer samples C will buy the product maximizing her personal utility, i.e., the difference between her respective budget and the product's ... more >>> TR06-151 | 10th December 2006 Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan #### The communication complexity of correlation We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate a value with distribution exactly D. Alice and Bob are allowed to share random bits generated ... more >>> TR06-152 | 6th December 2006 Konstantinos Georgiou, Avner Magen, Iannis Tourlakis #### Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1). more >>> TR06-153 | 19th October 2006 Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer #### The Complexity of Generalized Satisfiability for Linear Temporal Logic Revisions: 1 In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used If, in contrast, the set of propositional operators is restricted, the complexity may ... more >>> TR06-154 | 13th December 2006 Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam #### Uniform Hardness Amplification in NP via Monotone Codes We consider the problem of amplifying uniform average-case hardness of languages in$\NP$, where hardness is with respect to$\BPP$algorithms. We introduce the notion of \emph{monotone} error-correcting codes, and show that hardness amplification for$\NP$is essentially equivalent to constructing efficiently \emph{locally} encodable and \emph{locally} list-decodable monotone codes. The ... more >>> TR06-155 | 15th December 2006 Wenceslas Fernandez de la Vega, Marek Karpinski #### Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP Revisions: 1 We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any$r \ge 2$in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>> TR06-156 | 7th December 2006 Tomas Feder, Rajeev Motwani #### Finding large cycles in Hamiltonian graphs We show how to find in Hamiltonian graphs a cycle of length$n^{\Omega(1/\log\log n)}$. This is a consequence of a more general result in which we show that if$G$has maximum degree$d$and has a cycle with$k$vertices (or a 3-cyclable minor$H$with$k$vertices), then ... more >>> TR06-157 | 14th December 2006 Lance Fortnow, Rahul Santhanam #### Fixed-Polynomial Size Circuit Bounds We explore whether various complexity classes can have linear or more generally$n^k$-sized circuit families for some fixed$k$. We show 1) The following are equivalent, - NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k - P^NP|| is in SIZE(n^k) for some k - ONP/1 is in ... more >>> TR06-158 | 8th December 2006 Gyula Gyôr #### Representing Boolean OR function by quadratic polynomials modulo 6 We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to ... more >>> TR06-159 | 3rd October 2006 Predrag Tosic #### Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is ... more >>> TR06-160 | 17th December 2006 Tomas Feder, Phokion G. Kolaitis #### Closures and dichotomies for quantified constraints Quantified constraint satisfaction is the generalization of constraint satisfaction that allows for both universal and existential quantifiers over constrained variables, instead of just existential quantifiers. We study quantified constraint satisfaction problems${\rm CSP}(Q,S)$, where$Q\$ denotes
a pattern of quantifier alternation ending in exists or the set of all possible
more >>>

ISSN 1433-8092 | Imprint