Papers by Luca Trevisan

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] [Distributed Computing] [Other] [Surveys]

Some Recent Papers

• The Minority Dynamics and the Power of Synchronicity (SODA 2024)
• New SDP Roundings and Certifiable Approximation for Cubic Optimization (SODA 2024)
• A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs (CCC 2023)
• Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models (AISTATS'22)
• Percolation and Epidemic Processes in One-Dimensional Small-World Networks (LATIN'22)
• Cut Sparsification of the Clique Beyond the Ramanujan Bound (SODA'22)
• Expansion and Flooding in Dynamic Random Networks with Node Churn (ICDCS'21)
• Subexponential LPs Approximate Max Cut (FOCS'20)
• Consensus vs Broadcast, with and w/o Noise (ITCS'20)
• Finding a Bounded-Degree Expander Inside a Dense One (SODA'20)
• A New Algorithm for the Robust Semi-random Independent Set Problem (SODA'20)
• New Notions and Constructions of Sparsification for Graphs and Hypergraphs (FOCS'19)
• Optimal Lower Bounds for Sketching Graph Cuts (SODA'19)

Some Older Papers

• Improved Cheeger inequality... (STOC'13)
• Approximating the Expansion Profile and Almost Optimal Local Graph Clustering (FOCS'12/ JACM '16')
• Multi-way spectral partitioning and higher-order Cheeger inequalities (STOC'12/ JACM '14)
• On Khot's Unique Games Conjecture (AMS Bulletin'11)
• Max Cut and the Smallest Eigenvalue (STOC'09/ SICOMP'11)
• Average-Case Complexity (Foundations and Trends in TCS 2006)
• Pseudorandomness and Combinatorial Constructions (ICM'06)
• Gowers Uniformity, Influence of Variables, and PCPs (STOC'06/SICOMP'09)
• On Worst-Case to Average-Case Reductions for NP Problems (FOCS'03/ SICOMP '06)
• Counting Distinct Elements in a Data Stream (Random '02)
• Approximating the Minimum Spanning Tree Weight in Sublinear Time (ICALP'01/ SICOMP '05)
• Extracting Randomness from Samplable Distributions(FOCS'00)
• A PCP Characterization of NP with Optimal Amortized Query Complexity (STOC'00)
• Pseudorandom Generators Without the XOR Lemma (STOC'99/JCSS 2001)
• Extractors and Pseudorandom Generators (STOC'99/JACM 2001)
• When Hamming Meets Euclid: the Approximability of Geometric TSP and MST (STOC'97/SICOMP 2001)
• The Approximability of Constraint Satisfaction Problems (CCC'97/SICOMP 2000)
• Gadgets, Approximation, and Linear Programming (FOCS'96/SICOMP 2000)

Spectral Graph Theory

1. Tommaso D'Orsi and Luca Trevisan
   A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
   Preprint, 2022, arXiv:2204.10881
2. Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, and Luca Trevisan
   Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models
   In Proc. of AISTATS 2022, pages 10852-10880, arXiv:2108.04729
3. Antares Chen, Jonathan Shi and Luca Trevisan
   Cut Sparsification of the Clique Beyond the Ramanujan Bound
   In Proc. of SODA 2022, arXiv:2008.05648
4. Jess Banks and Luca Trevisan
   Vector Colorings of Random, Ramanujan, and Large-Girth Graphs
   arXiv:1907.02539
5. Nikhil Bansal, Ola Svensson and Luca Trevisan
   New Notions and Constructions of Sparsification for Graphs and Hypergraphs
   In FOCS 2019, arXiv:1905.01495
6. Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan
   Optimal Lower Bounds for Sketching Graph Cuts
   In Proc. of SODA 2019, pp. 2565-2569
   arXiv:1712.10261
7. Nikhil Srivastava, Luca Trevisan
   An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
   In Proc. of SODA 2018, pp. 1306-1315
   arXiv:1707.06364
8. Shayan Oveis Gharan, Luca Trevisan
   Partitioning into Expanders
   In Proc. of SODA 2014, pp. 1256-1266
   arXiv:1309.3223
9. 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
10. Shayan Oveis Gharan, Luca Trevisan
    A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
    Preprint, 2012
    arXiv:1212.2701
11. 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
12. 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
13. James R. Lee, Shayan Oveis Gharan, Luca Trevisan
    Multi-way spectral partitioning and higher-order Cheeger inequalities
    J. ACM 61(6): 37:1-37:30 (2014)
    Also in Proc. of 44th ACM STOC, pp. 1117-1130, 2012
    arXiv:1111.1055
14. Luca Trevisan
    Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
    Preprint, 2011 (posted online in 2013)
    arXiv:1303.2730
15. 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 Trevisan and TngKe Xue
   A Derandomized Switching Lemma and an Improved Derandomization of AC0
   In Proc. of CCC 2013
   ECCC TR12-116
2. 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
3. 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]
4. Luca Trevisan
   The Program-Enumeration Bottleneck in Average-Case Complexity Theory
   IEEE Conference on Computational Complexity 2010, pp. 88-95
   ECCC TR10-034
5. Anindya De and Luca Trevisan
   Extractors using hardness amplification
   In Proc. of Random-Approx, pp. 462-475, 2009
   [Conference proceedings]
6. 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]
7. 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
   
8. 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)
9. 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
10. Luca Trevisan
    On Uniform Amplification of Hardness in NP
    In Proc. of 37th STOC, ACM, 2005
    Manuscript: [pdf]
11. Lance Fortnow, Rahul Santhanam and Luca Trevisan
    Promise Hierarchies
    In Proc. of 37th STOC, ACM, 2005
    [Conference Proceedings]
12. 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: [pdf]] [Conference Proceedings] 
13. Luca Trevisan
    List Decoding Using the XOR Lemma
    In Proc. of 44th FOCS, IEEE, pp. 126-135, 2003
    [Conference Proceedings]
14. Elchanan Mossel, Amir Shpilka and Luca Trevisan
    On epsilon-Biased Generators in NC0
    In Proc. of 44th FOCS, IEEE, pp. 136-145, 2003
    [ECCC TR 03-043]
15. 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]
16. 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]
17. Luca Trevisan and Salil Vadhan.
    Extracting Randomness from Samplable Distributions
    In Proc. of 41st FOCS, pages 32-42, IEEE, 2000
    [Conference Proceedings]
18. 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]
19. 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]  [Conference Proceedings]
20. 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]

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
   Siam J. on Computing 39(1): 323-360, 2009
   Preliminary version in Proc. of 38th STOC, ACM, 2006.
   [Preprint]
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]

Approximation

1. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
   From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
   In Proc. of FOCS 2017, pp. 743-754
   arXiv:1708.04218
2. Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
   Near-Optimal UGC-hardness of Approximating Max k-CSP_R
   In Proc. of Random-Approx pp. 15:1-15:28, 2016
   arXiv:1511.06558
3. 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]
4. L. Trevisan
   Non-approximability Results for Optimization Problems on Bounded Degree Instances.
   In Proc. of the 33rd ACM STOC, 2001
   [Conference Proceedings]
5. 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]
6. 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]
7. 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]
8. 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]

1. Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
   Unique Games on the Hypercube
   Chicago J. Theor. Comput. Sci. (2015)
   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]

1. Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, and Luca Trevisan
   New SDP Roundings and Certifiable Approximation for Cubic Optimization
   In Proc. of SODA 2024, arXiv:2310.00393
2. Sam Hopkins, Tselil Schramm and Luca Trevisan
   Subexponential LPs Approximate Max Cut
   In Proc. of FOCS 2020, arXiv:1911.10304
3. Theo McKenzie, Hermish Mehta, Luca Trevisan
   A New Algorithm for the Robust Semi-random Independent Set Problem
   In Proc. of SODA 2020, arXiv:1808.03633
4. Pasin Manurangsi, Luca Trevisan
   Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
   In Proc. of APPROX-RANDOM 2018, pp. 20:1-20:17
   arXiv:1807.09898
5. Guy Kindler, Alexandra Kolla, Luca Trevisan
   Approximation of non-boolean 2CSP
   In Proc. of SODA 2016, pp. 1705-1714
   arXiv:1504.00681
6. Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
   Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree
   In Proc. of APPROX-RANDOM 2015, pp. 110-123
   arXiv:1505.03424
7. Luca Trevisan
   Approximation Algorithms for Unique Games
   Proc. of the 46th IEEE FOCS, 2005
   [Conference Proceedings] [Draft Full Version]
8. 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]
9. 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]
10. 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]

1. M. Cesati and L. Trevisan.
   On the Efficiency of Polynomial Time Approximation Schemes.
   Information Processing Letters, 64(4):165-171, 1997.
   [Journal Submission]
2. P. Crescenzi and L. Trevisan.
   MAXNP-completeness Made Easy.
   Theoretical Computer Science, 225(1-2):65-79, 1999.
   [Journal Submission]
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]
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]
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]

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]

Distributed Computing

1. Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi
   The Minority Dynamics and the Power of Synchronicity
   In Proc. of SODA 2024, 4155-4176, arXiv:2310.13558
2. Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi
   Percolation and Epidemic Processes in One-Dimensional Small-World Networks
   In Proc. of LATIN 2022, arXiv:2103.16398
3. Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan and Isabella Ziccardi
   Expansion and Flooding in Dynamic Random Networks with Node Churn
   In Proc. of ICDCS 2021, arXiv:2007.14681
4. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan
   Finding a Bounded-Degree Expander Inside a Dense One
   To appear in SODA 2020
   arXiv:1811.10316
5. Andrea E. F. Clementi, Luciano Guala', Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan
   Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise
   To appear in ITCS 2020
   arXiv:1807.05626
6. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
   Average whenever you meet: Opportunistic protocols for community detection
   In Proc. of ESA 2018, pp. 7:1-7:13
   arXiv:1703.05045
7. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
   Find Your Place: Simple Distributed Algorithms for Community Detection
   In Proc. of SODA 2017
   arXiv:1511.03927
8. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
   Stabilizing Consensus with Many Opinions
   In Proc. of SODA 2016, pp. 620-635
   arXiv:1508.06782
9. 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
10. Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan
    Information spreading in dynamic graphs
    Distributed Computing 28(1): 55-73 (2015)
    Also, in Proc. of PODC 2012, pp. 37-46
    arXiv:1111.0583

Miscellaneous

1. Charles Carlson, Alexandra Kolla, and Luca Trevisan
   A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs
   arXiv:1810.10044
2. Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
   An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
   In Proc. of SODA'17
   arXiv:1604.01445`
3. Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
   Quantum lower bound for inverting a permutation with advice
   Quantum Information and Computation 15(11-12): 901-913 (2015)
4. Luca Trevisan, Salil Vadhan and David Zuckerman
   Compression of Samplable Sources
   In Proc. of 19th Computational Complexity Conference, IEEE, 2004
   [Conference Proceedings]
5. L. Trevisan
   A Note on Deterministic Approximate Counting for k-DNF
   In Proc. of APPROX-RANDOM, pages 417-426,  2004
   [Preliminary version]
6. Christian Schallhart, Luca Trevisan
   Approximating Succinct MaxSat
   J. Log. Comput. 15(4): 551-557, 2005
7. 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
   [Springer Digital Library]
8. J. Diaz, J. Petit, M. Serna and L. Trevisan
   Approximating Layout Problems on Random Graphs
   Discrete Mathematics, 235(1-3):245-253, 2001.
9. L. Trevisan.
   On Local versus Global Satisfiability.
   SIAM Journal on Discrete Mathematics. 17(4):541-547, 2004
   [Preliminary Version]
10. L. Trevisan and F. Xhafa.
    The Parallel Complexity of Positive Linear Programming.
    Parallel Processing Letters, 8(4):527-533, 1998.
    [Journal Submission]
11. 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]
12. L. Trevisan.
    A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees.
    Information Processing Letters, 57(5):231-236, 1996.
    [Journal Submission]
13. 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 ]

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: [pdf]
7. Luca Trevisan
   Some Applications of Coding Theory in Computational Complexity
   Survey Paper
   Quaderni di Matematica 13:347-424, 2004
   Final version: href="codingsurvey.pdf">[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

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.