All reports in year 2003:

__
TR03-001
| 8th January 2003
__

Vince Grolmusz#### Near Quadratic Matrix Multiplication Modulo Composites

Comments: 1

__
TR03-002
| 13th December 2002
__

Stefan Szeider#### Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

Revisions: 1

__
TR03-003
| 19th December 2002
__

Fahiem Bacchus, Shannon Dalmao#### DPLL with Caching: A new algorithm for #SAT and Bayesian Inference

__
TR03-004
| 24th December 2002
__

Eli Ben-Sasson, Prahladh Harsha#### Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

__
TR03-005
| 28th December 2002
__

Scott Aaronson#### Quantum Certificate Complexity

__
TR03-006
| 23rd January 2003
__

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova#### 3CNF Properties are Hard to Test

__
TR03-007
| 15th January 2003
__

Olivier Dubois, Yacine Boufkhad, Jacques Mandler#### Typical random 3-SAT formulae and the satisfiability threshold

__
TR03-008
| 11th February 2003
__

Piotr Berman, Marek Karpinski#### Improved Approximation Lower Bounds on Small Occurrence Optimization

__
TR03-009
| 3rd February 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

__
TR03-010
| 13th February 2003
__

Sven Baumer, Rainer Schuler#### Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs

__
TR03-011
| 17th February 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang#### Disjoint NP-Pairs

__
TR03-012
| 21st January 2003
__

Edward Hirsch, Arist Kojevnikov#### Several notes on the power of Gomory-Chvatal cuts

__
TR03-013
| 7th March 2003
__

Luca Trevisan#### An epsilon-Biased Generator in NC0

Comments: 1

__
TR03-014
| 28th February 2003
__

Avrim Blum, Ke Yang#### On Statistical Query Sampling and NMR Quantum Computing

__
TR03-015
| 20th March 2003
__

Yael Tauman Kalai#### On the (In)security of the Fiat-Shamir Paradigm

__
TR03-016
| 15th January 2003
__

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis#### FIFO is Unstable at Arbitrarily Low Rates

Revisions: 1

__
TR03-017
| 27th March 2003
__

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener#### On Converting CNF to DNF

__
TR03-018
| 28th March 2003
__

Matthias Galota, Heribert Vollmer#### Functions Computable in Polynomial Space

__
TR03-019
| 3rd April 2003
__

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan#### Bounds on 2-Query Codeword Testing.

Revisions: 1

__
TR03-020
| 27th March 2003
__

Elad Hazan, Shmuel Safra, Oded Schwartz#### On the Hardness of Approximating k-Dimensional Matching

__
TR03-021
| 4th April 2003
__

Mikhail Vyalyi#### QMA=PP implies that PP contains PH

__
TR03-022
| 11th April 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

__
TR03-023
| 12th February 2003
__

Anna Palbom#### On Spanning Cacti and Asymmetric TSP

__
TR03-024
| 25th February 2003
__

Till Tantau#### Weak Cardinality Theorems for First-Order Logic

__
TR03-025
| 14th April 2003
__

Kristoffer Arnsfelt Hansen#### Constant width planar computation characterizes ACC0

__
TR03-026
| 20th February 2003
__

Janka Chlebíková, Miroslav Chlebík#### Inapproximability results for bounded variants of optimization problems

__
TR03-027
| 21st April 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta#### Reductions between Disjoint NP-Pairs

__
TR03-028
| 28th February 2003
__

Olivier Powell#### PSPACE contains almost complete problems

__
TR03-029
| 1st April 2003
__

Philippe Moser#### BPP has effective dimension at most 1/2 unless BPP=EXP

__
TR03-030
| 27th February 2003
__

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich#### Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques

__
TR03-031
| 8th April 2003
__

Birgit Schelm#### Average-Case Complexity Theory of Approximation Problems

__
TR03-032
| 16th April 2003
__

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna#### Approximating Longest Directed Path

__
TR03-033
| 6th May 2003
__

Meir Feder, Dana Ron, Ami Tavory#### Bounds on Linear Codes for Network Multicast

Comments: 1

__
TR03-034
| 17th March 2003
__

Arnold Beckmann#### Height restricted constant depth LK

__
TR03-035
| 21st May 2003
__

Eran Halperin, Guy Kortsarz, Robert Krauthgamer#### Tight lower bounds for the asymmetric k-center problem

__
TR03-036
| 27th April 2003
__

Bruce Edward Litow#### Polynomial equation elimination via Tarski Algebra

__
TR03-037
| 30th April 2003
__

Ziv Bar-Yossef#### Sampling Lower Bounds via Information Theory

__
TR03-038
| 15th May 2003
__

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor#### Asymmetric k-center is log^*n-hard to Approximate

__
TR03-039
| 19th May 2003
__

Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán#### Theory Revision with Queries: Horn, Read-once, and Parity Formulas

__
TR03-040
| 3rd June 2003
__

Philippe Moser#### RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

__
TR03-041
| 29th May 2003
__

Albert Atserias, Maria Luisa Bonet, Jordi Levy#### On Chvatal Rank and Cutting Planes Proofs

__
TR03-042
| 15th May 2003
__

Luca Trevisan#### List Decoding Using the XOR Lemma

__
TR03-043
| 14th May 2003
__

Elchanan Mossel, Amir Shpilka, Luca Trevisan#### On epsilon-Biased Generators in NC0

__
TR03-044
| 12th May 2003
__

Juan Luis Esteban, Jacobo Toran#### A Combinatorial Characterization of Treelike Resolution Space

__
TR03-045
| 8th June 2003
__

Oded Goldreich, Asaf Nussboim#### On the Implementation of Huge Random Objects

Revisions: 1

__
TR03-046
| 11th June 2003
__

Philippe Moser#### Locally Computed Baire's Categories on Small Complexity Classes

__
TR03-047
| 22nd June 2003
__

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton#### Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

__
TR03-048
| 24th June 2003
__

Stefan Droste, Thomas Jansen, Ingo Wegener#### Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

__
TR03-049
| 25th June 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness of Short Symmetric Instances of MAX-3SAT

__
TR03-050
| 16th June 2003
__

Daniel Král#### Locally satisfiable formulas

__
TR03-051
| 20th June 2003
__

Tsuyoshi Morioka#### The Relative Complexity of Local Search Heuristics and the Iteration Principle

__
TR03-052
| 13th May 2003
__

Stanislav Busygin, Dmitrii V. Pasechnik#### On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds

__
TR03-053
| 8th July 2003
__

Kazuo Iwama, Suguru Tamaki#### Improved Upper Bounds for 3-SAT

__
TR03-054
| 2nd July 2003
__

Daniel Rolf#### 3-SAT in RTIME(O(1.32793^n)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses

__
TR03-055
| 20th July 2003
__

Jan Krajicek#### Implicit proofs

__
TR03-056
| 29th July 2003
__

Piotr Berman, Marek Karpinski#### Approximability of Hypergraph Minimum Bisection

__
TR03-057
| 21st July 2003
__

Scott Aaronson#### Lower Bounds for Local Search by Quantum Arguments

__
TR03-058
| 22nd July 2003
__

Vince Grolmusz#### Defying Dimensions Modulo 6

Revisions: 2

__
TR03-059
| 18th May 2003
__

Harumichi Nishimura, Tomoyuki Yamakami#### Polynomial time quantum computation with advice

Revisions: 2

__
TR03-060
| 7th September 2003
__

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen#### Completeness in Two-Party Secure Computation - A Computational View

__
TR03-061
| 29th August 2003
__

Jan Kára, Daniel Král#### Free Binary Decision Diagrams for Computation of EAR_n

__
TR03-062
| 10th July 2003
__

Andrei Krokhin, Peter Jonsson#### Recognizing Frozen Variables in Constraint Satisfaction Problems

__
TR03-063
| 2nd July 2003
__

John Hitchcock#### The Size of SPP

__
TR03-064
| 23rd June 2003
__

Vikraman Arvind, Piyush Kurur#### Upper Bounds on the Complexity of some Galois Theory Problems

__
TR03-065
| 19th June 2003
__

Wee, Hoeteck#### Compressibility Lower Bounds in Oracle Settings

__
TR03-066
| 2nd September 2003
__

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

__
TR03-067
| 14th August 2003
__

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

__
TR03-068
| 30th July 2003
__

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

__
TR03-069
| 13th August 2003
__

Elmar Böhler, Christian Glaßer, Daniel Meister#### Small Bounded-Error Computations and Completeness

__
TR03-070
| 19th August 2003
__

Amit Chakrabarti, Oded Regev#### An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

__
TR03-071
| 18th August 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Privacy in Non-Private Environments

Revisions: 1

__
TR03-072
| 15th September 2003
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Algorithms for SAT based on search in Hamming balls

__
TR03-073
| 11th June 2003
__

Amin Coja-Oghlan#### The Lovasz number of random graph

__
TR03-074
| 24th June 2003
__

Vince Grolmusz#### Sixtors and Mod 6 Computations

__
TR03-075
| 7th September 2003
__

Agostino Capponi#### A tutorial on the Deterministic two-party Communication Complexity

__
TR03-076
| 8th September 2003
__

Michael Langberg#### Testing the independence number of hypergraphs

__
TR03-077
| 4th September 2003
__

Till Tantau#### Logspace Optimisation Problems and their Approximation Properties

__
TR03-078
| 23rd October 2003
__

Fan Chung, Ron Graham, Jia Mao, Andrew Chi-Chih Yao#### Finding Favorites

Comments: 2

__
TR03-079
| 8th November 2003
__

Scott Aaronson#### Multilinear Formulas and Skepticism of Quantum Computing

__
TR03-080
| 12th November 2003
__

Venkatesan Guruswami#### Better Extractors for Better Codes?

__
TR03-081
| 10th October 2003
__

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini#### Computation of the Lov\'asz Theta Function for Circulant Graphs

__
TR03-082
| 22nd November 2003
__

Andris Ambainis, Ke Yang#### Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

__
TR03-083
| 21st November 2003
__

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz#### One-Way Communication Complexity of Symmetric Boolean Functions

__
TR03-084
| 27th November 2003
__

Joshua Buresh-Oppenheim, Tsuyoshi Morioka#### Relativized NP Search Problems and Propositional Proof Systems

__
TR03-085
| 28th November 2003
__

Ke Yang#### On the (Im)possibility of Non-interactive Correlation Distillation

__
TR03-086
| 1st December 2003
__

Amos Beimel, Tal Malkin#### A Quantitative Approach to Reductions in Secure Computation

__
TR03-087
| 10th December 2003
__

Richard Beigel, Lance Fortnow, William Gasarch#### A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

Vince Grolmusz

We show how one can use non-prime-power, composite moduli for

computing representations of the product of two $n\times n$ matrices

using only $n^{2+o(1)}$ multiplications.

Stefan Szeider

The deficiency of a propositional formula F in CNF with n variables

and m clauses is defined as m-n. It is known that minimal

unsatisfiable formulas (unsatisfiable formulas which become

satisfiable by removing any clause) have positive deficiency.

Recognition of minimal unsatisfiable formulas is NP-hard, and it was

shown recently ...
more >>>

Fahiem Bacchus, Shannon Dalmao

Bayesian inference and counting satisfying assignments are important

problems with numerous applications in probabilistic reasoning. In this

paper, we show that plain old DPLL equipped with memoization can solve

both of these problems with time complexity that is at least as

good as all known algorithms. Furthermore, DPLL with memoization

more >>>

Eli Ben-Sasson, Prahladh Harsha

We present a simple proof of the bounded-depth Frege lower bounds of

Pitassi et. al. and Krajicek et. al. for the pigeonhole

principle. Our method uses the interpretation of proofs as two player

games given by Pudlak and Buss. Our lower bound is conceptually

simpler than previous ones, and relies ...
more >>>

Scott Aaronson

Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation ... more >>>

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

For a boolean formula \phi on n variables, the associated property

P_\phi is the collection of n-bit strings that satisfy \phi. We prove

that there are 3CNF properties that require a linear number of queries,

even for adaptive tests. This contrasts with 2CNF properties

that are testable with O(\sqrt{n}) ...
more >>>

Olivier Dubois, Yacine Boufkhad, Jacques Mandler

$k$-SAT is one of the best known among a wide class of random

constraint satisfaction problems believed to exhibit a threshold

phenomenon where the control parameter is the ratio, number of

constraints to number of variables. There has been a large amount of

work towards estimating ...
more >>>

Piotr Berman, Marek Karpinski

We improve a number of approximation lower bounds for

bounded occurrence optimization problems like MAX-2SAT,

E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching.

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study the role of connectivity of communication networks in private

computations under information theoretic settings. It will be shown that

some functions can be computed by private protocols even if the

underlying network is 1-connected but not 2-connected. Then we give a

complete characterisation of non-degenerate functions that can ...
more >>>

Sven Baumer, Rainer Schuler

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT)

is a well known NP-complete problem and the development of faster

(moderately exponential time) algorithms has received much interest

in recent years. We show that the 3-SAT problem can be solved by a

probabilistic algorithm in expected time O(1,3290^n).

more >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

We study the question of whether the class DisNP of

disjoint pairs (A, B) of NP-sets contains a complete pair.

The question relates to the question of whether optimal

proof systems exist, and we relate it to the previously

studied question of whether there exists ...
more >>>

Edward Hirsch, Arist Kojevnikov

We prove that the Cutting Plane proof system based on

Gomory-Chvatal cuts polynomially simulates the

lift-and-project system with integer coefficients

written in unary. The restriction on coefficients can be

omitted when using Krajicek's cut-free Gentzen-style extension

of both systems. We also prove that Tseitin tautologies

have short proofs in ...
more >>>

Luca Trevisan

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

Avrim Blum, Ke Yang

We introduce a ``Statistical Query Sampling'' model, in which

the goal of an algorithm is to produce an element in a hidden set

$S\subseteq\bit^n$ with reasonable probability. The algorithm

gains information about $S$ through oracle calls (statistical

queries), where the algorithm submits a query function $g(\cdot)$

and receives ...
more >>>

Yael Tauman Kalai

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>>

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

In this work, we study the stability of the {\sf FIFO} ({\sf

First-In-First-Out}) protocol in the context of Adversarial

Queueing Theory. As an important intermediate step, we consider

{\em dynamic capacities}, where each network link capacity may

arbitrarily take on values in the two-valued set of integers

$\{1,C\}$ for $C>1$ ...
more >>>

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener

The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>>

Matthias Galota, Heribert Vollmer

We show that the class of integer-valued functions computable by

polynomial-space Turing machines is exactly the class of functions f

for which there is a nondeterministic polynomial-time Turing

machine with a certain order on its paths that on input x outputs a 3x3

matrix with entries from {-1,0,1} on each ...
more >>>

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

We present upper bounds on the size of codes that are locally

testable by querying only two input symbols. For linear codes, we

show that any $2$-locally testable code with minimal distance

$\delta n$ over a finite field $F$ cannot have more than

$|F|^{3/\delta}$ codewords. This result holds even ...
more >>>

Elad Hazan, Shmuel Safra, Oded Schwartz

We study bounded degree graph problems, mainly the problem of

k-Dimensional Matching \emph{(k-DM)}, namely, the problem of

finding a maximal matching in a k-partite k-uniform balanced

hyper-graph. We prove that k-DM cannot be efficiently approximated

to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.

This ...
more >>>

Mikhail Vyalyi

We consider possible equality QMA=PP and give an argument

against it. Namely, this equality implies that PP contains PH. The argument is based on the strong form of Toda's theorem and

the strengthening of the proof for inclusion $QMA\subseteq PP$ due to Kitaev and Watrous.

Piotr Berman, Marek Karpinski, Alexander D. Scott

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

Anna Palbom

In an attempt to generalize Christofides algorithm for metric TSP to the asymmetric TSP with triangle inequality we have studied various properties of directed spanning cacti. In this paper we first observe that finding the TSP in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to ... more >>>

Till Tantau

Kummer's cardinality theorem states that a language is recursive

if a Turing machine can exclude for any n words one of the

n + 1 possibilities for the number of words in the language. It

is known that this theorem does not hold for polynomial-time

computations, but there ...
more >>>

Kristoffer Arnsfelt Hansen

We obtain a characterization of ACC0 in terms of a natural class of

constant width circuits, namely in terms of constant width polynomial

size planar circuits. This is shown via a characterization of the

class of acyclic digraphs which can be embedded on a cylinder surface

in such a way ...
more >>>

Janka Chlebíková, Miroslav Chlebík

We study small degree graph problems such as Maximum Independent Set

and Minimum Node Cover and improve approximation lower bounds for

them and for a number of related problems, like Max-B-Set Packing,

Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.

For example, we prove NP-hardness factor of 95/94

more >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta

We prove that all of the following assertions are equivalent:

There is a many-one complete disjoint NP-pair;

there is a strongly many-one complete disjoint NP-pair;

there is a Turing complete disjoint NP-pair such that all reductions

are smart reductions;

there is a complete disjoint NP-pair for one-to-one, invertible ...
more >>>

Olivier Powell

An almost complete set A for a complexity class C is a language of C which is not complete, but that has the property that ``many'' languages of C reduce to A, where the term ``many'' is used in reference to Lutz's resource bounded measure (rbm). The question of the ... more >>>

Philippe Moser

We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP.

Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP

on infinitely many input lengths.

We also prove that BPP has measure zero in the smaller complexity

class ...
more >>>

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

Abstract. It is known that random k-SAT formulas with at least

(2^k*ln2)*n random clauses are unsatisfiable with high probability. This

result is simply obtained by bounding the expected number of satisfy-

ing assignments of a random k-SAT instance by an expression tending

to 0 when n, the number of variables ...
more >>>

Birgit Schelm

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

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

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

more >>>

Meir Feder, Dana Ron, Ami Tavory

Traditionally, communication networks are composed of

routing nodes, which relay and duplicate data. Work in

recent years has shown that for the case of multicast, an

improvement in both rate and code-construction complexity can be

gained by replacing these routing nodes by linear coding

nodes. These nodes transmit linear combinations ...
more >>>

Arnold Beckmann

Height restricted constant depth LK is a natural restriction of

Gentzen's propositional proof system LK. A sequence of LK-formulas

has polylogarithmic-height restricted depth-d-LK proofs iff the

n-th formula in the sequence possesses LK-proofs where cut-formulas

are of depth d+1 with small bottom fanin

and of ...
more >>>

Eran Halperin, Guy Kortsarz, Robert Krauthgamer

In the {\sc $k$-center} problem, the input is a bound $k$

and $n$ points with the distance between every two of them,

such that the distances obey the triangle inequality.

The goal is to choose a set of $k$ points to serve as centers,

so that the maximum distance ...
more >>>

Bruce Edward Litow

The elimination

problem is classical:

implicitly express one of the variables occurring in a finite

system of polynomial equations as an algebraic function of a

designated subset of the remaining variables. Solutions to this

problem by resultants, or more comprehensively by

use of Gr\"{o}bner basis methods are available. In this ...
more >>>

Ziv Bar-Yossef

We present a novel technique, based on the Jensen-Shannon divergence

from information theory, to prove lower bounds on the query complexity

of sampling algorithms that approximate functions over arbitrary

domain and range. Unlike previous methods, our technique does not

use a reduction from a binary decision problem, but rather ...
more >>>

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

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

Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

A theory, in this context, is a Boolean formula; it is

used to classify instances, or truth assignments. Theories

can model real-world phenomena, and can do so more or less

correctly.

The theory revision, or concept revision, problem is to

correct a given, roughly correct concept.

This problem is ...
more >>>

Philippe Moser

We use recent results on the hardness of resource-bounded

Kolmogorov random strings, to prove that RP is small in SUBEXP

else ZPP=PSPACE and NP=EXP.

We also prove that if NP is not small in SUBEXP, then

NP=AM, improving a former result which held for the measure ...
more >>>

Albert Atserias, Maria Luisa Bonet, Jordi Levy

We study the Chv\'atal rank of polytopes as a complexity measure of

unsatisfiable sets of clauses. Our first result establishes a

connection between the Chv\'atal rank and the minimum refutation

length in the cutting planes proof system. The result implies that

length lower bounds for cutting planes, or even for ...
more >>>

Luca Trevisan

We show that Yao's XOR Lemma, and its essentially equivalent

rephrasing as a Direct Product Lemma, can be

re-interpreted as a way of obtaining error-correcting

codes with good list-decoding algorithms from error-correcting

codes having weak unique-decoding algorithms. To get codes

with good rate and efficient list decoding algorithms

one needs ...
more >>>

Elchanan Mossel, Amir Shpilka, Luca Trevisan

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

Juan Luis Esteban, Jacobo Toran

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

Oded Goldreich, Asaf Nussboim

We initiate a general study of pseudo-random implementations

of huge random objects, and apply it to a few areas

in which random objects occur naturally.

For example, a random object being considered may be

a random connected graph, a random bounded-degree graph,

or a random error-correcting code with good ...
more >>>

Philippe Moser

We strengthen an earlier notion of

resource-bounded Baire's categories, and define

resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP

and on probabilistic complexity classes such as BPP.

We give an alternative characterization of meager sets via resource-bounded

Banach Mazur games.

We show that the class ...
more >>>

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such

representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ...
more >>>

Stefan Droste, Thomas Jansen, Ingo Wegener

Randomized search heuristics like local search, simulated annealing or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics.

Here a framework called black-box ... more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott

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

Daniel Král

A CNF formula is k-satisfiable if each k clauses of it can be satisfied

simultaneously. Let \pi_k be the largest real number such that for each

k-satisfiable formula with variables x_i, there are probabilities p_i

with the following property: If each variable x_i is chosen randomly and

independently to be ...
more >>>

Tsuyoshi Morioka

Johnson, Papadimitriou and Yannakakis introduce the class $\PLS$

consisting of optimization problems for which efficient local-

search heuristics exist. We formulate a type-2 problem $\iter$

that characterizes $\PLS$ in style of Beame et al., and prove

a criterion for type-2 problems to be nonreducible to $\iter$.

As a corollary, ...
more >>>

Stanislav Busygin, Dmitrii V. Pasechnik

We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute.

To establish this ... more >>>

Kazuo Iwama, Suguru Tamaki

This paper presents a new upper bound for the

$k$-satisfiability problem. For small $k$'s, especially for $k=3$,

there have been a lot of algorithms which run significantly faster

than the trivial $2^n$ bound. The following list summarizes those

algorithms where a constant $c$ means that the algorithm runs in time

more >>>

Daniel Rolf

This paper establishes a randomized algorithm that finds a satisfying assignment for a satisfiable formula $F$ in 3-CNF in $O(1.32793^n)$ expected running time. The algorithms is based on the analysis of so-called strings, which are sequences of 3-clauses where non-succeeding clauses do not share a variable and succeeding clauses share ... more >>>

Jan Krajicek

We describe a general method how to construct from

a propositional proof system P a possibly much stronger

proof system iP. The system iP operates with

exponentially long P-proofs described ``implicitly''

by polynomial size circuits.

As an example we prove that proof system iEF, implicit EF,

corresponds to bounded ...
more >>>

Piotr Berman, Marek Karpinski

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

Scott Aaronson

The problem of finding a local minimum of a black-box function is central

for understanding local search as well as quantum adiabatic algorithms.

For functions on the Boolean hypercube {0,1}^n, we show a lower bound of

Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to

solve this ...
more >>>

Vince Grolmusz

We show that a certain representation of the matrix-product can be computed with $n^{o(1)}$ multiplications. We also show, that similar representations of matrices can be compressed enormously with the help of simple linear transforms.

more >>>Harumichi Nishimura, Tomoyuki Yamakami

Advice is supplementary information that enhances the computational

power of an underlying computation. This paper focuses on advice that

is given in the form of a pure quantum state. The notion of advised

quantum computation has a direct connection to non-uniform quantum

circuits and tally languages. The paper examines the ...
more >>>

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

A Secure Function Evaluation (SFE) of a two-variable function f(.,.) is a protocol that allows two parties with inputs x and y to evaluate

f(x,y) in a manner where neither party learns ``more than is necessary". A rich body of work deals with the study of completeness for secure ...
more >>>

Jan Kára, Daniel Král

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined

for n x n Boolean matrices: EAR_n(M)=1 iff the matrix ...
more >>>

Andrei Krokhin, Peter Jonsson

In constraint satisfaction problems over finite domains, some variables

can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the

instances. We show that the complexity of ...
more >>>

John Hitchcock

Derandomization techniques are used to show that at least one of the

following holds regarding the size of the counting complexity class

SPP.

1. SPP has p-measure 0.

2. PH is contained in SPP.

In other words, SPP is small by being a negligible subset of

exponential time or large ...
more >>>

Vikraman Arvind, Piyush Kurur

Given a polynomial f(X) with rational coefficients as input

we study the problem of (a) finding the order of the Galois group of

f(X), and (b) determining the Galois group of f(X) by finding a small

generator set. Assuming the generalized Riemann hypothesis, we prove

the following complexity bounds:

1. ... more >>>

Wee, Hoeteck

A source is compressible if we can efficiently compute short

descriptions of strings in the support and efficiently

recover the strings from the descriptions. In this paper, we

present a technique for proving lower bounds on

compressibility in an oracle setting, which yields the

following results:

- We ...
more >>>

Daniele Micciancio

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

Ran Raz

An arithmetic formula is multi-linear if the polynomial computed

by each of its sub-formulas is multi-linear. We prove that any

multi-linear arithmetic formula for the permanent or the

determinant of an $n \times n$ matrix is of size super-polynomial

in $n$.

Matthias Homeister

We prove the first lower bound for restricted read-once parity branching

programs with unlimited parity nondeterminism where for each input the

variables may be tested according to several orderings.

Proving a superpolynomial lower bound for read-once parity branching

programs is still a challenging open problem. The following variant ...
more >>>

Elmar Böhler, Christian Glaßer, Daniel Meister

SBP is a probabilistic promise class located

between MA and AM \cap BPPpath. The first

part of the paper studies the question of whether

SBP has many-one complete sets. We relate

this question to the existence of uniform

enumerations. We construct an oracle relative to

which SBP and AM do ...
more >>>

Amit Chakrabarti, Oded Regev

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

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study private computations in information-theoretical settings on

networks that are not 2-connected. Non-2-connected networks are

``non-private'' in the sense that most functions cannot privately be

computed on such networks. We relax the notion of privacy by

introducing lossy private protocols, which generalize private

protocols. We measure the information each ...
more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

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

Amin Coja-Oghlan

We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$

of the independence number and the corresponding relaxations of the

chromatic number on random graphs G(n,p). We prove that \theta is

concentrated about its mean, and that the relaxations of the chromatic

number in the case ...
more >>>

Vince Grolmusz

We consider the following phenomenon: with just one multiplication

we can compute (3u+2v)(3x+2y)= 3ux+4vy mod 6, while computing the same polynomial modulo 5 needs 2 multiplications. We generalize this observation and we define some vectors, called sixtors, with remarkable zero-divisor properties. Using sixtors, we also generalize our earlier result ...
more >>>

Agostino Capponi

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

Michael Langberg

A $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, ... more >>>

Till Tantau

This paper introduces logspace optimisation problems as

analogues of the well-studied polynomial-time optimisation

problems. Similarly to them, logspace

optimisation problems can have vastly different approximation

properties, even though the underlying existence and budget problems

have the same computational complexity. Numerous natural problems

are presented that exhibit such a varying ...
more >>>

Fan Chung, Ron Graham, Jia Mao, Andrew Chi-Chih Yao

We investigate a new type of information-theoretic identification problem, suggested to us by Alan Taylor. In this problem we are given a set of items, more than half of which share a common ``good" value. The other items have various other values which are called ``bad". The only method we ... more >>>

Scott Aaronson

Several researchers, including Leonid Levin, Gerard 't Hooft, and

Stephen Wolfram, have argued that quantum mechanics will break down

before the factoring of large numbers becomes possible. If this is

true, then there should be a natural "Sure/Shor separator" -- that is,

a set of quantum ...
more >>>

Venkatesan Guruswami

We present an explicit construction of codes that can be list decoded

from a fraction $(1-\eps)$ of errors in sub-exponential time and which

have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal

rate of $\Omega(\eps)$, and is the first sub-exponential complexity

construction to beat the rate of $O(\eps^2)$ achieved by ...
more >>>

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>

Andris Ambainis, Ke Yang

Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the ... more >>>

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

We study deterministic one-way communication complexity

of functions with Hankel communication matrices.

Some structural properties of such matrices are established

and applied to the one-way two-party communication complexity

of symmetric Boolean functions.

It is shown that the number of required communication bits

does not depend on ...
more >>>

Joshua Buresh-Oppenheim, Tsuyoshi Morioka

We consider Total Functional $\NP$ ($\TFNP$) search problems. Such problems are based on combinatorial principles that guarantee, through locally checkable conditions, that a solution to the problem exists in an exponentially-large domain, and have the property that any solution has a polynomial-size witness that can be verified in polynomial time. ... more >>>

Ke Yang

We study the problem of non-interactive correlation distillation

(NICD). Suppose Alice and Bob each has a string, denoted by

$A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$,

respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is

independently drawn from a distribution $\noise$, known as the ``noise

mode''. Alice and Bob wish to ``distill'' the correlation

more >>>

Amos Beimel, Tal Malkin

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

Richard Beigel, Lance Fortnow, William Gasarch

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