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

__
TR12-175
| 13th December 2012
__

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan#### On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

__
TR12-123
| 28th September 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan#### Better pseudorandom generators from milder pseudorandom restrictions

__
TR12-116
| 13th September 2012
__

Luca Trevisan#### A Derandomized Switching Lemma and an Improved Derandomization of AC0

Revisions: 1

__
TR10-034
| 7th March 2010
__

Luca Trevisan#### The Program-Enumeration Bottleneck in Average-Case Complexity Theory

__
TR09-141
| 19th December 2009
__

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani#### Improved Pseudorandom Generators for Depth 2 Circuits

__
TR09-113
| 9th November 2009
__

Anindya De, Luca Trevisan, Madhur Tulsiani#### Non-uniform attacks against one-way functions and PRGs

__
TR08-103
| 22nd November 2008
__

Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

__
TR08-045
| 23rd April 2008
__

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Dense Subsets of Pseudorandom Sets

__
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

__
TR06-098
| 17th August 2006
__

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani#### A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

__
TR06-073
| 8th June 2006
__

Andrej Bogdanov, Luca Trevisan#### Average-Case Complexity

Revisions: 1

__
TR06-013
| 24th January 2006
__

Luca Trevisan#### Pseudorandomness and Combinatorial Constructions

__
TR05-116
| 12th October 2005
__

Alex Samorodnitsky, Luca Trevisan#### Gowers Uniformity, Influence of Variables, and PCPs

__
TR05-034
| 5th April 2005
__

Luca Trevisan#### Approximation Algorithms for Unique Games

Revisions: 1
,
Comments: 1

__
TR05-022
| 19th February 2005
__

Omer Reingold, Luca Trevisan, Salil Vadhan#### Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

__
TR05-015
| 27th January 2005
__

Andrej Bogdanov, Luca Trevisan#### On Worst-Case to Average-Case Reductions for NP Problems

__
TR05-012
| 17th January 2005
__

Luca Trevisan, Salil Vadhan, David Zuckerman#### Compression of Samplable Sources

__
TR04-098
| 5th November 2004
__

Lance Fortnow, Rahul Santhanam, Luca Trevisan#### Promise Hierarchies

__
TR04-093
| 9th November 2004
__

Oded Goldreich, Madhu Sudan, Luca Trevisan#### From logarithmic advice to single-bit advice

__
TR04-065
| 28th July 2004
__

Luca Trevisan#### Inapproximability of Combinatorial Optimization Problems

Revisions: 1

__
TR04-043
| 20th May 2004
__

Luca Trevisan#### Some Applications of Coding Theory in Computational Complexity

__
TR03-043
| 14th May 2003
__

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

__
TR03-042
| 15th May 2003
__

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

__
TR03-013
| 7th March 2003
__

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

Comments: 1

__
TR02-069
| 14th November 2002
__

Luca Trevisan#### A Note on Deterministic Approximate Counting for k-DNF

Revisions: 1

__
TR02-064
| 14th November 2002
__

Andrej Bogdanov, Luca Trevisan#### Lower Bounds for Testing Bipartiteness in Dense Graphs

__
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

__
TR01-010
| 25th January 2001
__

Oded Goldreich, Luca Trevisan#### Three Theorems regarding Testing Graph Properties.

Revisions: 1

__
TR00-022
| 2nd May 2000
__

Rosario Gennaro, Luca Trevisan#### Lower bounds on the efficiency of generic cryptographic constructions

__
TR98-074
| 16th December 1998
__

Madhu Sudan, Luca Trevisan, Salil Vadhan#### Pseudorandom generators without the XOR Lemma

Revisions: 2

__
TR98-055
| 4th September 1998
__

Luca Trevisan#### Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

Comments: 1

__
TR98-040
| 24th July 1998
__

Madhu Sudan, Luca Trevisan#### Probabilistically checkable proofs with low amortized query complexity

__
TR98-034
| 23rd June 1998
__

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan#### A tight characterization of NP with 3 query PCPs

__
TR98-007
| 12th January 1998
__

Luca Trevisan#### Recycling Queries in PCPs and in Linearity Tests

__
TR97-039
| 11th September 1997
__

Pierluigi Crescenzi, Luca Trevisan#### MAX NP-Completeness Made Easy

__
TR97-012
| 19th March 1997
__

Luca Trevisan#### On Local versus Global Satisfiability

__
TR97-001
| 8th January 1997
__

Marco Cesati, Luca Trevisan#### On the Efficiency of Polynomial Time Approximation Schemes

__
TR96-066
| 21st November 1996
__

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan#### Structure in Approximation Classes

__
TR96-064
| 11th December 1996
__

Sanjeev Khanna, Madhu Sudan, Luca Trevisan#### Constraint satisfaction: The approximability of minimization problems.

__
TR96-046
| 27th August 1996
__

Luca Trevisan#### On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

__
TR96-016
| 6th February 1996
__

Andrea E. F. Clementi, Luca Trevisan#### Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

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

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

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

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

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

Luca Trevisan

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

Luca Trevisan

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

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

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

Anindya De, Luca Trevisan, Madhur Tulsiani

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

Luca Trevisan, Madhur Tulsiani, Salil Vadhan

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

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

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

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

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

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

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

Andrej Bogdanov, Luca Trevisan

We survey the theory of average-case complexity, with a

focus on problems in NP.

Luca Trevisan

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

Alex Samorodnitsky, Luca Trevisan

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

Luca Trevisan

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

Omer Reingold, Luca Trevisan, Salil Vadhan

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

Andrej Bogdanov, Luca Trevisan

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

Luca Trevisan, Salil Vadhan, David Zuckerman

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

Lance Fortnow, Rahul Santhanam, Luca Trevisan

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,

MATIME, AMTIME and BQTIME.

We show a ... more >>>

Oded Goldreich, Madhu Sudan, Luca Trevisan

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

Luca Trevisan

We survey results on the hardness of approximating combinatorial

optimization problems.

Luca Trevisan

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

cryptography.

Locally decodable codes are error-correcting codes ... 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 >>>

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

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

Luca Trevisan

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

Andrej Bogdanov, Luca Trevisan

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

Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan

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

Oded Goldreich, Luca Trevisan

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

Rosario Gennaro, Luca Trevisan

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

Madhu Sudan, Luca Trevisan, Salil Vadhan

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

Luca Trevisan

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

Madhu Sudan, Luca Trevisan

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

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

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

Luca Trevisan

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

Pierluigi Crescenzi, Luca Trevisan

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

Luca Trevisan

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

Marco Cesati, Luca Trevisan

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

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

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

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

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

Luca Trevisan

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

Andrea E. F. Clementi, Luca Trevisan

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