Papers by Luca Trevisan

The papers are ordered by topic, and, for each topic, they are roughly in order of conception, most recent first.

Read acknowledgements of grants and disclaimers on copyright.

Also available: [List sorted BY YEAR]

Jump to: [Spectral Graph Theory] [Randomness] [Cryptography] [PCP] [Approximation] [Property Testing] [Other] [Surveys]

Some Recent Papers

Some Older Papers

Spectral Graph Theory

  1. Shayan Oveis Gharan, Luca Trevisan
    Partitioning into Expanders
    In Proc. of SODA 2014, pp. 1256-1266
    arXiv:1309.3223
  2. 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
  3. Shayan Oveis Gharan, Luca Trevisan
    A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
    Preprint, 2012
    arXiv:1212.2701
  4. Shayan Oveis Gharan, Luca Trevisan
    A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
    In Proc. APPROX-RANDOM 2013, pp. 303-316
    arXiv:1212.1831
  5. 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
  6. 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
  7. Luca Trevisan
    Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
    Preprint, 2011 (posted online in 2013)
    arXiv:1303.2730
  8. Luca Trevisan
    Max Cut and the Smallest Eigenvalue
    SIAM J. Comput. 41(6): 1769-1786 (2012)
    Earlier version in Proc. of 41st ACM STOC, 2009
    arXiv:0806.1978

Randomness

  1. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan
    Simple dynamics for plurality consensus
    In Proc. of SPAA 2014, pp. 247-256
    arXiv:1310.2858
  2. Luca Trevisan and TngKe Xue
    A Derandomized Switching Lemma and an Improved Derandomization of AC0
    In Proc. of CCC 2013
    ECCC TR12-116
  3. Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan
    Information spreading in dynamic graphs
    In Proc. of PODC 2012, pp. 37-46
    arXiv:1111.0583
  4. 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
  5. 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]
  6. Luca Trevisan
    The Program-Enumeration Bottleneck in Average-Case Complexity Theory
    IEEE Conference on Computational Complexity 2010, pp. 88-95
    ECCC TR10-034
  7. Anindya De and Luca Trevisan
    Extractors using hardness amplification
    In Proc. of Random-Approx, pp. 462-475, 2009
    [Conference proceedings]
  8. 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]
  9. 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, 2009
    ECCC TR08-103
  10. Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan
    Dense Subsets of Pseudorandom Sets
    In Proc. of 49th IEEE FOCS, 2008
    ECCC TR08-45
    (expository note:  arXiv:0806.0381)
  11. 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
  12. Luca Trevisan
    On Uniform Amplification of Hardness in NP
    In Proc. of 37th STOC, ACM, 2005
    Manuscript: [pdf]
  13. Lance Fortnow, Rahul Santhanam and Luca Trevisan
    Promise Hierarchies
    In Proc. of 37th STOC, ACM, 2005
    [Conference Proceedings]
  14. Andrej Bogdanov and Luca Trevisan
    On Worst-Case to Average-Case Reductions for NP Problems
    SIAM J. Comput. 36(4): 1119-1159 (2006)
    Earlier version in Proc. of 44th FOCS, IEEE, pp. 308-317, 2003
    [Draft full version: [ps] [pdf]] [Conference Proceedings] 
  15. Luca Trevisan
    List Decoding Using the XOR Lemma
    In Proc. of 44th FOCS, IEEE, pp. 126-135, 2003
    [Conference Proceedings]
  16. Elchanan Mossel, Amir Shpilka and Luca Trevisan
    On epsilon-Biased Generators in NC0
    Random Structures and Algorithms, 29(1):56-81, 2006 
    Also in Proc. of 44th FOCS, IEEE, pp. 136-145, 2003
    [Manuscript]
  17. 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]
  18. 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]
  19. Luca Trevisan and Salil Vadhan.
    Extracting Randomness from Samplable Distributions
    In Proc. of 41st FOCS, pages 32-42, IEEE, 2000
    [Conference Proceedings]
  20. 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]
  21. 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]
  22. 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]

Cryptography

  1. 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]
  2. 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]
  3. 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]
  4. 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]
  5. 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]
  6. 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]
  7. 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]

Probabilistically Checkable Proofs

  1. Alex Samorodnitsky and Luca Trevisan. 
    Gowers Uniformity, Influence of Variables, and PCPs
    In Proc. of 38th STOC, ACM, 2006.
    [Manuscript]
  2. Alex  Samorodnitsky and Luca Trevisan. 
    A PCP Characterization of NP with Optimal Amortized Query Complexity.

    In Proc. of 32nd STOC,  ACM, pp. 191-199, 2000.
    [Preliminary Version]
  3. 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]
  4. 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]
  5. 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]

Approximation

Non-approximability Results
  1. 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]
  2. L. Trevisan
    Non-approximability Results for Optimization Problems on Bounded Degree Instances.
    In Proc. of the 33rd ACM STOC, 2001
    [Conference Proceedings]
  3. 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]
  4. 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]
  5. 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]
  6. 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]
Integrality Gap Instances
  1. Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
    Unique Games on the Hypercube
    Unpublished manuscript, 2014
    arXiv:1405.1374
  2. 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]
  3. 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]
Algorithmic Results
  1. Luca Trevisan
    Approximation Algorithms for Unique Games
    Proc. of the 46th IEEE FOCS, 2005
    [Conference Proceedings] [Draft Full Version]
  2. Maria Serna, Luca Trevisan, and Fatos Xhafa.
    The Parallel Approximability of Non-Boolean Constraint Satisfaction and Restricted Integer Programming.
    Theoretical Computer Science 332(1-3):123-139, 2005
    Preliminary version In Proceedings of the 15th STACS, LNCS 1373, Springer-Verlag, pages 488-498, 1998.
    [Conference Proceedings]
  3. 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]
  4. 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]
Structural Results
  1. M. Cesati and L. Trevisan.
    On the Efficiency of Polynomial Time Approximation Schemes.
    Information Processing Letters, 64(4):165-171, 1997.
    [Journal Submission][Abstract]
  2. P. Crescenzi and L. Trevisan.
    MAXNP-completeness Made Easy.
    Theoretical Computer Science, 225(1-2):65-79, 1999.
    [Journal Submission][Abstract]
  3. Sanjeev Khanna, Madhu Sudan,  Luca Trevisan and David Williamson.
    The Approximability of Constraint Satisfaction Problems.
    SIAM J. of Computing, 30(6):1863-1920, 2001.
    [Journal Submission][Abstract]
  4. 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]
  5. 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]

Property Testing and Sub-linear Algorithms 

  1. A. Bogdanov and L. Trevisan
    Lower Bounds for Testing Bipartiteness in Dense Graphs
    In Proc. of 19th Computational Complexity Conference, IEEE, 2004
    [Manuscript]
  2. 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]
  3. 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]
  4. 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]
  5. 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]
  6. 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]

Miscellaneous

  1. Luca Trevisan, Salil Vadhan and David Zuckerman
    Compression of Samplable Sources
    In Proc. of 19th Computational Complexity Conference, IEEE, 2004
    [Conference Proceedings]
  2. L. Trevisan
    A Note on Deterministic Approximate Counting for k-DNF
    In Proc. of APPROX-RANDOM, pages 417-426,  2004
    [Preliminary version]
  3. Christian Schallhart, Luca Trevisan
    Approximating Succinct MaxSat
    J. Log. Comput. 15(4): 551-557, 2005
  4. J. Diaz, J. Petit, M. Serna and L. Trevisan
    Approximating Layout Problems on Random Graphs
    Discrete Mathematics, 235(1-3):245-253, 2001.
  5. L. Trevisan.
    On Local versus Global Satisfiability.
    SIAM Journal on Discrete Mathematics. 17(4):541-547, 2004
    [Preliminary Version][Abstract]
  6. L. Trevisan and F. Xhafa.
    The Parallel Complexity of Positive Linear Programming.
    Parallel Processing Letters, 8(4):527-533, 1998.
    [Journal Submission][Abstract]
  7. 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]
  8. L. Trevisan.
    A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees.
    Information Processing Letters, 57(5):231-236, 1996.
    [Journal Submission] [Abstract]
  9. 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]

Survey Papers

  1. Luca Trevisan
    Pseudorandomness and derandomization
    ACM Crossroads 18(3): 27-31 (2012)
    [ACM Digital Library]
  2. Luca Trevisan
    On Khot's Unique Games Conjecture
    Bulletin of the AMS 49(1): 91-111, 2012
    [pdf]
  3. Luca Trevisan
    Additive Combinatorics and Theoretical Computer Science
    SIGACT News Complexity Column Number 63, 2009
    [pdf]
  4. Andrej Bogdanov and Luca Trevisan
    Average-Case Complexity
    Foundations and Trends in Theoretical Computer Science 1(2), 2006
    arXiv:cs/0606037
  5. Luca Trevisan
    Pseudorandomness and Combinatorial Constructions
    In Proceedings of ICM 2006
    arXiv:cs/0601100
  6. 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]
  7. Luca Trevisan
    Some Applications of Coding Theory in Computational Complexity
    Survey Paper
    Quaderni di Matematica 13:347-424, 2004
    Final version: [ps] [pdf]
  8. Luca  Trevisan
    Error-Correcting Codes and Pseudorandom Projections
    Invited Talk
    Abstract in Proc. of RANDOM-APPROX, pp. 7-9, 2001
  9. Luca Trevisan
    A Survey of Optimal PCP Characterizations of NP
    Tutorial
    Abstract in Proc. of 15th IEEE Conference on Computational Complexity (CCC'00), pp. 146-148, 2000
  10. Luca  Trevisan.
    Interactive and probabilistic proof-checking
    Survey paper
    In Annals of Pure and Applied Logic, 104:325-342, 2000
    [Final version]
  11. 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]
  12. 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]

Grants and Copyright

Some of these papers were based upon work supported by the National Science Foundation under Grants No. CCF-0729137, CCF-9984703, CCF-1161812, CCF-1216642, by the Sloan Foundation, by the Okawa Foundation, and by the US-Israel Binational Science Foundation. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF) or of the Sloan Foundation, of the Okawa Foundation, or of the US-Israel BSF.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.  These works may not be reposted without the explicit permission of the copyright holder.  Also, some of these works have been submitted for publication. Copyright may be transferred without further notice and this version may no longer be accessible.