Papers by Luca Trevisan

Unpublished

• Luca Trevisan
  Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
  Preprint, 2011 (posted online in 2013)
  arXiv:1303.2730
• Shayan Oveis Gharan, Luca Trevisan
  A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
  Preprint, 2012
  arXiv:1212.2701
• Shayan Oveis Gharan, Luca Trevisan
  A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
  Preprint, 2012
  arXiv:1212.1831

2013

• Luca Trevisan and TngKe Xue
  A Derandomized Switching Lemma and an Improved Derandomization of AC0
  In Proc. of CCC 2013
  ECCC TR12-116
• Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
  Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
  In Proc. of 45th ACM STOC, 2013
  arXiv:1301.5584

2012

• Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan
  Information spreading in dynamic graphs
  In Proc. of PODC 2012, pp. 37-46
  arXiv:1111.0583
• James R. Lee, Shayan Oveis Gharan, Luca Trevisan
  Multi-way spectral partitioning and higher-order Cheeger inequalities
  In Proc. of 44th ACM STOC, pp. 1117-1130, 2012
  arXiv:1111.1055
• Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan
  Better Pseudorandom Generators from Milder Pseudorandom Restrictions
  In Proc. of 53th IEEE FOCS, pp. 120-129, 2012
  arXiv:1210.0049
• Shayan Oveis Gharan, Luca Trevisan
  Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
  In Proc. of 53rd IEEE FOCS, pp. 187-196, 2012
  arXiv:1204.2021
• Luca Trevisan
  Pseudorandomness and derandomization
  ACM Crossroads 18(3): 27-31 (2012)
  [ACM Digital Library]

2010

• Luca Trevisan
  The Program-Enumeration Bottleneck in Average-Case Complexity Theory
  IEEE Conference on Computational Complexity 2010, pp. 88-95
  ECCC TR10-034
• Anindya De, Omid Etesami, Luca Trevisan and Madhur Tulsiani
  Improved Pseudorandom Generators for Depth 2 Circuits
  In Proc. of APPROX-RANDOM 2010, pp. 504-517 [pdf]
• Anindya De, Luca Trevisan and Madhur Tulsiani
  Time Space Tradeoffs for Attacks against One-Way Functions and PRGs.
  In Proc. of CRYPTO 2010, pp. 649-665
  [ECCC TR09-113]

2009

• Luca Trevisan
  Additive Combinatorics and Theoretical Computer Science
  SIGACT News Complexity Column Number 63, 2009
  [pdf]
• Anindya De and Luca Trevisan
  Extractors using hardness amplification
  In Proc. of Random-Approx, pp. 462-475, 2009
  [Conference proceedings]
• Shachar Lovett, Omer Reingold, Luca Trevisan and Salil Vadhan
  Pseudorandom Bit Generators That Fool Modular Sums
  In Proc. of Random-Approx, pp. 615-630, 2009
  [Conference proceedings]
• Luca Trevisan, Madhur Tulsiani and Salil Vadhan
  Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution
  In Proc. of 24th IEEE Conference on Computational Complexity, pp. 126-136, 2009
  ECCC TR08-103
  
• Luca Trevisan
  Max Cut and the Smallest Eigenvalue
  In Proc. of 41st ACM STOC, pp. 263-272, 2009
  arXiv:0806.1978
• James Cook, Omid Etesami, Rachel Miller, and Luca Trevisan
  Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms
  In Proc. of the 6th Theory of Cryptography Conference, Springer-Verlag, pp. 521-538, 2009
  [Conference Proceedings]

2008

• Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan
  Dense Subsets of Pseudorandom Sets
  Proc. of the 49th IEEE FOCS, 2008
  ECCC TR08-45
  (expository note:  arXiv:0806.0381)

2007

• Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, and Hoeteck Wee
  Amplifying Collision Resistance: A Complexity-Theoretic Treatment
  In Proc. of CRYPTO 2007, pp. 264-283
  [Conference Proceedings]
• Grant Schoenebeck, Luca Trevisan and Madhur Tulsiani
  Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
  In Proc. of 39th ACM STOC, 2007, pp. 302-310
  [Full version]
• Grant Schoenebeck, Luca Trevisan and Madhur Tulsiani
  A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
  In Proc. of IEEE Conference on Computational Complexity, 2007, pp.205-216
  [Full version]

2006

• Andrej Bogdanov and Luca Trevisan
  Average-Case Complexity
  Foundations and Trends in Theoretical Computer Science 1(2), 2006
  arXiv:cs/0606037
• Luca Trevisan
  Pseudorandomness and Combinatorial Constructions
  In Proceedings of ICM, 2006
  [Paper]
• Alex Samorodnitsky and Luca Trevisan. 
  Gowers Uniformity, Influence of Variables, and PCPs
  In Proc. of 38th STOC, ACM, 2006.
  [Manuscript]
• Omer Reingold, Luca Trevisan and Salil Vadhan
  Pseudorandom Walks in Directed Regular Graphs and the RL vs L Problem
  In Proc. of 38th STOC, ACM, 2006
  ECCC TR 05-22

2005

• Luca Trevisan
  Inapproximability of Combinatorial Optimization Problems
  French version (translation by Bruno Escoffier) appeared in Optimisation Combinatiore 2, (Vangelis Paschos, Editor), Hermes, 2005
  English version: [ps] [pdf]
• Luca Trevisan
  Approximation Algorithms for Unique Games
  Proc. of the 46th IEEE FOCS, 2005
  [Conference Proceedings] [Draft Full Version]
• Venkatesan  Guruswami and Luca Trevisan
  The Complexity of Making Unique Choices: Approximating 1-in-kSAT 
  In Proc. of APPROX-RANDOM, Springer-Verlag, 2005
  [Conference Proceedings]
• Luca Trevisan
  On Uniform Amplification of Hardness in NP
  In Proc. of 37th STOC, ACM, 2005
  Manuscript: [pdf]
• Lance Fortnow, Rahul Santhanam and Luca Trevisan
  Promise Hierarchies
  In Proc. of 37th STOC, ACM, 2005
  [Conference Proceedings]
• Henry Lin, Luca Trevisan and Hoeteck Wee
  On Hardness Amplification of One-Way Functions
  In Proc. of 2nd Theory of Cryptography Conference, Springer-Verlag, 2005
  [Conference Proceedings]

2004

• L. Trevisan
  A Note on Deterministic Approximate Counting for k-DNF
  In Proc. of APPROX-RANDOM, Springer-Verlag, page 417-426, 2004
  [Preliminary version]
• A. Bogdanov and L. Trevisan
  Lower Bounds for Testing Bipartiteness in Dense Graphs
  In Proc. of 19th Computational Complexity Conference, IEEE, 2004
  [Manuscript]
• Luca Trevisan, Salil Vadhan and David Zuckerman
  Compression of Samplable Sources
  In Proc. of 19th Computational Complexity Conference, IEEE, 2004
  [Conference Proceedings]
• Omer Reingold, Luca Trevisan and Salil Vadhan
  Notions of Reducibility between Cryptographic Primitives
  In Proc. of 1st Theory of Cryptography Conference, Springer-Verlag, pp. 1-20, 2004
  [Conference Proceedings]
• Cynthia Dwork, Ronen Shaltiel, Adam Smith and Luca Trevisan
  List Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument
  In Proc. of 1st Theory of Cryptography Conference, Springer-Verlag, pp. 101-120, 2004
  [Conference Proceedings]
• L. Trevisan.
  On Local versus Global Satisfiability.
  SIAM Journal on Discrete Mathematics. 17(4):541-547, 2004
  [Preliminary Version][Abstract]
• Luca Trevisan
  Some Applications of Coding Theory in Computational Complexity
  Survey Paper
  Quaderni di Matematica 13:347-424, 2004
  Final version: [ps] [pdf]

2003

• Andrej Bogdanov and Luca Trevisan
  On Worst-Case to Average-Case Reductions for NP Problems
  In Proc. of 44th FOCS, IEEE, pp. 308-317, 2003
  Draft full version: [ps] [pdf] Conference Proceedings: [ps]
  
• Luca Trevisan
  List Decoding Using the XOR Lemma
  In Proc. of 44th FOCS, IEEE, pp. 126-135, 2003
  [Conference Proceedings]
• Elchanan Mossel, Amir Shpilka and Luca Trevisan
  On epsilon-Biased Generators in NC0
  In Proc. of 44th FOCS, IEEE, pp. 136-145, 2003
  [Manuscript]

2002

• A. Bogdanov, K. Obata and L. Trevisan
  A Lower Bound for Testing 3-Colorability in Bounded-degree Graphs
  In Proc. of 43rd FOCS, pages 93-102, IEEE, 2002
  [Conference Proceedings]
• Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan
  Counting Distinct Elements in a Data Stream
  In Proc. of RANDOM'02, Springer-Verlag, pages 1-10, 2002
• Luca Trevisan and Salil Vadhan
  Pseudorandomness and Average-case Complexity via Uniform Reductions
  In Proc. of 17th  Computational Complexity Conference, pages 129-138, IEEE, 2002
  [Conference Proceedings]
• Z. Bar-Yossef, O. Reingold, R. Shaltiel and L. Trevisan
  Streaming Computation of Combinatorial Objects
  In Proc. of 17th  Computational Complexity Conference, pages165-174, IEEE, 2002
  [Conference Proceedings]
• O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan
  Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
  In Proc. of 17th  Computational Complexity Conference, pages 175-183, IEEE, 2002
  [Manuscript]

2001

• Oded Goldreich and Luca Trevisan
  Three Theorems Regarding Testing Graph Properties
  Random Structures and Algorithms, 23(1):23-57, 2003.
  Also in Proc. of 42nd FOCS, pages 460-469, IEEE, 2001.
  [Full version]
• L. Trevisan
  Non-approximability Results for Optimization Problems on Bounded Degree Instances.
  In Proc. of the 33rd ACM STOC, 2001
  [Conference Proceedings]
• Bernard Chazelle, Ronitt Rubinfeld and Luca Trevisan
  Approximating the Minimum Spanning Tree Weight in Sublinear Time
  SIAM J. on Computing 34(6):1370-1379, 2005.
  Preliminary version in Proc. of 28th ICALP, pages 190-200, Springer-Verlag, 2001.
  [Conference Proceedings]
• J. Diaz, J. Petit, M. Serna and L. Trevisan
  Approximating Layout Problems on Random Graphs
  Discrete Mathematics, 235(1-3):245-253, 2001.

2000

• Luca Trevisan and Salil Vadhan.
  Extracting Randomness from Samplable Distributions
  In Proc. of 41st FOCS, pages 32-42, IEEE, 2000
  [Conference Proceedings]
• Rosario Gennaro, Yael Gertner, Jonathan Katz, and Luca Trevisan.
  Bounds on the Efficiency of Generic Cryptographic Constructions
  SIAM J. on Computing, 35(1):217-246, 2005
  (Earlier version in Proc. of 41st FOCS, pages 305-313, IEEE, 2000)
  [Conference Proceedings] [Full version]
• J. Katz and L. Trevisan.
  On the efficiency of local decoding procedures for error-correcting codes.
  In Proc. of 32nd STOC, pages 80-86, ACM, 2000.
  [Conference proceedings]
• A. Samorodnitsky and L. Trevisan
  A PCP Characterization of NP with Optimal Amortized Query Complexity
  In Proc. of 32nd STOC,  ACM, pp. 191-199, 2000.
  [Preliminary Version]
• Luca Trevisan.
  Interactive and probabilistic proof-checking
  Survey paper
  In Annals of Pure and Applied Logic, 104:325-342, 2000
  [Final version]

1999

• Madhu Sudan, Luca Trevisan and Salil Vadhan
  Pseudorandom Generators Without the XOR Lemma
  J. of Computer and System Sciences, 62(2):236-266, 2001
  Preliminary version: Proc. of 31st ACM STOC,  1999.
  [Draft full version][Conference Proceedings]
• Luca Trevisan.
  Extractors and Pseudorandom Generators
  J. of the ACM, 48(4):860-879, 2001
  Preliminary version In Proc. of 31st ACM STOC, pp. 141-148, 1999.
  Full version [ps] [pdf]  [Conference Proceedings]
• P. Crescenzi and L. Trevisan
  MAXNP-completeness Made Easy.
  Theoretical Computer Science, 225(1-2):65-79, 1999.
  [Journal Submission][Abstract]

1998

• M. Sudan and L. Trevisan.
  Probabilistically Checkable Proofs with Low Amortized Query Complexity.
  In Proc. of the 39th Symposium on Foundations of Computer Science. IEEE, pp. 18-27, 1998
  [Preliminary Version]
• V. Guruswami, D. Lewin, M. Sudan and L. Trevisan.
  A Tight Characterization of NP with 3-Query PCPs.
  In Proc. of the 39th Symposium on Foundations of Computer Science. IEEE, pp. 8-17, 1998
  [Preliminary Version]
• L. Trevisan
  Recycling Queries in PCPs and in Linearity Tests.
  In Proceedings of the 30th Symposium on Theory of Computing. ACM, pp. 299-308, 1998
  [Conference Proceedings][Abstract]
• M. Serna, L. Trevisan, and F. Xhafa
  The Parallel Approximability of Non-Boolean Constraint Satisfaction and Restricted Integer Programming
  Theoretical Computer Science 332:123-139, 2005.
  Preliminary version in Proc. STACS'98, LNCS 1373, Springer-Verlag, pages 488-498, 1998
  [Conference Proceedings]
• L. Trevisan and F. Xhafa
  The Parallel Complexity of Positive Linear Programming.
  Parallel Processing Letters, 8(4):527-533, 1998.
  [Journal Submission][Abstract]
• Andrea E.F. Clementi, Jose D.P. Rolim and Luca Trevisan.
  Recent Advances Towards Proving P=BPP
  Survey paper
  Bulletin of the EATCS, 64:96-103, 1998.
  [Final version]
• Jose D.P. Rolim and Luca Trevisan.
  A Case Study of De-randomization Methods for Combinatorial Approximation Problems
  Survey paper
  Journal of Combinatorial Optimization, 2(3):219-236, 1998.
  [Final version]

1997

• Alexander E. Andreev, Andrea E.F. Clementi, Jose D.P. Rolim, and Luca Trevisan. 
  Weak Random Sources, Hitting Sets, and BPP Simulations
  SIAM Journal on Computing, 28(6):2103-2116, 1999.
  Preliminary version: Proc. of  38th IEEE FOCS, 1997.
  [Final version][Conference Proceedings][Abstract]
• L. Trevisan
  When Hamming Meets Euclid: the Approximability of Geometric TSP and MST.
  SIAM J. on Computing, 30(2):475-485, 2001.
  Preliminary version in Proc. of the 29th ACM STOC, 1997
  [Draft full version][Conference Proceedings] [Abstract]
• S. Khanna, M. Sudan,  L. Trevisan and D. Williamson
  The Approximability of Constraint Satisfaction Problems.
  SIAM J. of Computing, 30(6):1863-1920, 2001.
  [Journal Submission][Abstract]
• Luca Trevisan
  Approximating Satisfiable Satisfiability Problems.
  Algorithmica 28(1):145-172, 2000.
  Preliminary version in Proc. of the 5th ESA, 1997.
  [Full version (revised 2/1999)] [Conference Proceedings] [Abstract]
• M. Cesati and L. Trevisan
  On the Efficiency of Polynomial Time Approximation Schemes
  Information Processing Letters, 64(4):165-171, 1997.
  [Journal Submission][Abstract]

1996

• L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson.
  Gadgets, Approximation, and Linear Programming.
  SIAM J. on Computing, 29(6):2074-2097, 2000
  Preliminary version in Proc. of the 37th IEEE FOCS, 1996.
  [Full version (revised 10/98)] [Conference Proceedings] [Abstract]
• P. Crescenzi, R. Silvestri, and L. Trevisan.
  On Weighted vs Unweighted Versions of Combinatorial Optimization Problems
  Information and Computation, 167(1):10-26, 2001.
  Preliminary version in Proc. of the 4th IEEE ISTCS, 1996.
  [Full version (revised 2/99)] [Conference Proceedings] [Abstract]
• L. Trevisan
  Parallel Approximation Algorithms by Positive Linear Programming
  Algorithmica, 21:72-88, 1998
  Preliminary version in Proc. of the 4th ESA, 1996.
  [Journal Submission] [Conference Proceedings] [Abstract]
• A. Clementi and L. Trevisan.
  Improved Non-approximability Results for Vertex Cover Problems with Density Constraints.
  Theoretical Computer Science, 225(1-2):113-128, 1999.
  Preliminary version in Proc. of the 2nd COCOON, 1996.
  [Journal Submission] [Conference Proceedings] [Abstract]
• L. Trevisan.
  A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees.
  Information Processing Letters, 57(5):231-236, 1996.
  

1995

• P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan.
  Structure in Approximation Classes.
  SIAM J. on Computing, 28(5):1759-1782, 1999.
  Preliminary version in Proc. of the 1st COCOON, 1995.
  [Journal Submission] [Conference Proceedings] [Abstract]
• M. Boreale and L. Trevisan.
  A Complexity Analysis of Bisimilarity for Value-Passing Processes.
  Theoretical Computer Science 238(1-2):313-345, 2000
  Preliminary versions in  Proc. of the 21st MFCS, 1996, and in Proc. of the 15th FSTTCS, 1995.
  [Journal Submission]
• P. Crescenzi and L. Trevisan
  On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem.
  RAIRO, Theoretical Informatics and Applications, 30:431-441, 1996.
  Preliminary version in Proceedings of the 20th WG,1995.
  [Journal Submission] [Conference Proceedings ] [Abstract]

1994

• P. Crescenzi and L. Trevisan
  On Approximation Scheme Preserving Reducibility and its Applications.
  Theory of Computing Systems, 33(1):1-16, 2000.
  Preliminary version in Proc. of the 14th FSTTCS, 1994.
  [Journal Submission] [Conference Proceedings] [Abstract]