Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Luca Trevisan:

TR14-109 | 14th August 2014
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Quantum lower bound for inverting a permutation with advice

Revisions: 1

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>

TR12-175 | 13th December 2012
James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>>

TR12-123 | 28th September 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

Better pseudorandom generators from milder pseudorandom restrictions

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

TR12-116 | 13th September 2012
Luca Trevisan

A Derandomized Switching Lemma and an Improved Derandomization of AC0

Revisions: 1

We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$.
A seed length of ... more >>>

TR10-034 | 7th March 2010
Luca Trevisan

The Program-Enumeration Bottleneck in Average-Case Complexity Theory

Three fundamental results of Levin involve algorithms or reductions
whose running time is exponential in the length of certain programs. We study the
question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly
than any other fixed ... more >>>

TR09-141 | 19th December 2009
Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

Improved Pseudorandom Generators for Depth 2 Circuits

We prove the existence of a $poly(n,m)$-time computable
pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables
and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.
Previously, the best pseudorandom generator for depth-2 circuits had seed
length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It ... more >>>

TR09-113 | 9th November 2009
Anindya De, Luca Trevisan, Madhur Tulsiani

Non-uniform attacks against one-way functions and PRGs

We study the power of non-uniform attacks against one-way
functions and pseudorandom generators.

Fiat and Naor show that for every function
$f: [N]\to [N]$
there is an algorithm that inverts $f$ everywhere using
(ignoring lower order factors)
time, space and advice at most $N^{3/4}$.

We show that ... more >>>

TR08-103 | 22nd November 2008
Luca Trevisan, Madhur Tulsiani, Salil Vadhan

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

We show that every high-entropy distribution is indistinguishable from an
efficiently samplable distribution of the same entropy. Specifically, we prove
that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,
then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most
$S\cdot ... more >>>

TR08-045 | 23rd April 2008
Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

Dense Subsets of Pseudorandom Sets

A theorem of Green, Tao, and Ziegler can be stated (roughly)
as follows: if R is a pseudorandom set, and D is a dense subset of R,
then D may
be modeled by a set M that is dense in the entire domain such that D and
more >>>

TR06-132 | 17th October 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

Revisions: 1

We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least $2-\epsilon$ after
$\Omega_\epsilon(\log n)$ ... more >>>

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

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

We study semidefinite programming relaxations of Vertex Cover arising from
repeated applications of the LS+ ``lift-and-project'' method of Lovasz and
Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality
gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>

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

Average-Case Complexity

Revisions: 1

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

more >>>

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

TR05-116 | 12th October 2005
Alex Samorodnitsky, Luca Trevisan

Gowers Uniformity, Influence of Variables, and PCPs

Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f)
of a function f: G -> \C, where G is a finite abelian group and \C are the
complex numbers. Roughly speaking, if a function has small Gowers uniformity
of dimension d, then it ``looks random'' on ... 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-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-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-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 >>>

TR04-098 | 5th November 2004
Lance Fortnow, Rahul Santhanam, Luca Trevisan

Promise Hierarchies

We show that for any constant a, ZPP/b(n) strictly contains
ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques
are very general and give the same hierarchy for all the common
promise time classes including RTIME, NTIME \cap coNTIME, UTIME,

We show a ... more >>>

TR04-093 | 9th November 2004
Oded Goldreich, Madhu Sudan, Luca Trevisan

From logarithmic advice to single-bit advice

Building on Barak's work (Random'02),
Fortnow and Santhanam (FOCS'04) proved a time hierarchy
for probabilistic machines with one bit of advice.
Their argument is based on an implicit translation technique,
which allow to translate separation results for short (say logarithmic)
advice (as shown by Barak) into separations for ... more >>>

TR04-065 | 28th July 2004
Luca Trevisan

Inapproximability of Combinatorial Optimization Problems

Revisions: 1

We survey results on the hardness of approximating combinatorial
optimization problems.

more >>>

TR04-043 | 20th May 2004
Luca Trevisan

Some Applications of Coding Theory in Computational Complexity

Error-correcting codes and related combinatorial constructs
play an important role in several recent (and old) results
in computational complexity theory. In this paper we survey
results on locally-testable and locally-decodable error-correcting
codes, and their applications to complexity theory and to

Locally decodable codes are error-correcting codes ... more >>>

TR03-043 | 14th May 2003
Elchanan Mossel, Amir Shpilka, Luca Trevisan

On epsilon-Biased Generators in NC0

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

TR03-042 | 15th May 2003
Luca Trevisan

List Decoding Using the XOR Lemma

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

TR03-013 | 7th March 2003
Luca Trevisan

An epsilon-Biased Generator in NC0

Comments: 1

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

TR02-069 | 14th November 2002
Luca Trevisan

A Note on Deterministic Approximate Counting for k-DNF

Revisions: 1

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

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

Lower Bounds for Testing Bipartiteness in Dense Graphs

We consider the problem of testing bipartiteness in the adjacency
matrix model. The best known algorithm, due to Alon and Krivelevich,
distinguishes between bipartite graphs and graphs that are
$\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$
queries. We show that this is optimal for non-adaptive algorithms,
up to the ... more >>>

TR01-080 | 14th November 2001
Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

We prove that if a linear error correcting code
$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then $m = 2^{\Omega(n)}$. We also present
several extensions of this result.

We show a reduction from the ... more >>>

TR01-010 | 25th January 2001
Oded Goldreich, Luca Trevisan

Three Theorems regarding Testing Graph Properties.

Revisions: 1

Property testing is a relaxation of decision problems
in which it is required to distinguish {\sc yes}-instances
(i.e., objects having a predetermined property) from instances
that are far from any {\sc yes}-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation. ... more >>>

TR00-022 | 2nd May 2000
Rosario Gennaro, Luca Trevisan

Lower bounds on the efficiency of generic cryptographic constructions

We present lower bounds on the efficiency of
constructions for Pseudo-Random Generators (PRGs) and
Universal One-Way Hash Functions (UOWHFs) based on
black-box access to one-way permutations. Our lower bounds are tight as
they match the efficiency of known constructions.

A PRG (resp. UOWHF) construction based on black-box access is
a ... more >>>

TR98-074 | 16th December 1998
Madhu Sudan, Luca Trevisan, Salil Vadhan

Pseudorandom generators without the XOR Lemma

Revisions: 2

Impagliazzo and Wigderson have recently shown that
if there exists a decision problem solvable in time $2^{O(n)}$
and having circuit complexity $2^{\Omega(n)}$
(for all but finitely many $n$) then $\p=\bpp$. This result
is a culmination of a series of works showing
connections between the existence of hard predicates
and ... more >>>

TR98-055 | 4th September 1998
Luca Trevisan

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

Comments: 1

We introduce a new approach to construct extractors -- combinatorial
objects akin to expander graphs that have several applications.
Our approach is based on error correcting codes and on the Nisan-Wigderson
pseudorandom generator. An application of our approach yields a
construction that is simple to ... more >>>

TR98-040 | 24th July 1998
Madhu Sudan, Luca Trevisan

Probabilistically checkable proofs with low amortized query complexity

The error probability of Probabilistically Checkable Proof (PCP)
systems can be made exponentially small in the number of queries
by using sequential repetition. In this paper we are interested
in determining the precise rate at which the error goes down in
an optimal protocol, and we make substantial progress toward ... more >>>

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

A tight characterization of NP with 3 query PCPs

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

TR98-007 | 12th January 1998
Luca Trevisan

Recycling Queries in PCPs and in Linearity Tests

We study query-efficient Probabilistically Checkable
Proofs (PCPs) and linearity tests. We focus on the number
of amortized query bits. A testing algorithm uses $q$ amortized
query bits if, for some constant $k$, it reads $qk$ bits and has
error probability at most $2^{-k}$. The best known ... more >>>

TR97-039 | 11th September 1997
Pierluigi Crescenzi, Luca Trevisan

MAX NP-Completeness Made Easy

We introduce a simple technique to obtain reductions
between optimization constraint satisfaction problems. The
technique uses the probabilistic method to reduce the size of
disjunctions. As a first application, we prove the
MAX NP-completeness of MAX 3SAT without using the PCP theorem
(thus solving an open ... more >>>

TR97-012 | 19th March 1997
Luca Trevisan

On Local versus Global Satisfiability

We prove an extremal combinatorial result regarding
the fraction of satisfiable clauses in boolean CNF
formulae enjoying a locally checkable property, thus
solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint
satisfaction ... more >>>

TR97-001 | 8th January 1997
Marco Cesati, Luca Trevisan

On the Efficiency of Polynomial Time Approximation Schemes

A polynomial time approximation scheme (PTAS) for an optimization
problem $A$ is an algorithm that on input an instance of $A$ and
$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time
that is polynomial for each fixed $\epsilon$. Typical running times
are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ... more >>>

TR96-066 | 21st November 1996
Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

Structure in Approximation Classes

The study of the approximability properties of NP-hard
optimization problems has recently made great advances mainly due
to the results obtained in the field of proof checking. In a
recent breakthrough the APX-completeness of several important
optimization problems is proved, thus reconciling `two distinct
views of ... more >>>

TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

Constraint satisfaction: The approximability of minimization problems.

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F ... more >>>

TR96-046 | 27th August 1996
Luca Trevisan

On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

We consider the Traveling Salesperson Problem (TSP) restricted
to Euclidean spaces of dimension at most k(n), where n is the number of
cities. We are interested in the relation between the asymptotic growth of
k(n) and the approximability of the problem. We show that the problem is ... more >>>

TR96-016 | 6th February 1996
Andrea E. F. Clementi, Luca Trevisan

Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

We provide new non-approximability results for the restrictions
of the min-VC problem to bounded-degree, sparse and dense graphs.
We show that for a sufficiently large B, the recent 16/15 lower
bound proved by Bellare et al. extends with negligible
loss to graphs with bounded ... more >>>

ISSN 1433-8092 | Imprint