Bio


Professor Trevisan is interested in theoretical computer science.

Academic Appointments


Professional Education


  • PhD, Sapienza University, Rome (1997)

2013-14 Courses


Journal Articles


  • A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM Gharan, S. O., Trevisan, L. 2013: 303-316
  • Simple Dynamics for Majority Consensus. CoRR abs/1310.2858 Becchetti, L., Clementi, Andrea, E.F., Natale, E., Pasquale, F., Silvestri, R., Trevisan, L. 2013
  • Partitioning into Expanders. CoRR abs/1309.3223 Gharan, S. O., Trevisan, L. 2013
  • Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut? CoRR abs/1303.2730 Trevisan, L. 2013
  • Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank. CoRR abs/1304.2060 Gharan, S. O., Trevisan, L. 2013
  • Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap. CoRR abs/1301.5584 Kwok, T. C., Lau, L. C., Lee, Y. T., Gharan, S. O., Trevisan, L. 2013
  • Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. STOC Kwok, T. C., Lau, L. C., Lee, Y. T., Gharan, S. O., Trevisan, L. 2013: 20-Nov
  • A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues. CoRR abs/1212.2701 Gharan, S. O., Trevisan, L. 2012
  • ON KHOT'S UNIQUE GAMES CONJECTURE BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY Trevisan, L. 2012; 49 (1): 91-111
  • MAX CUT AND THE SMALLEST EIGENVALUE SIAM JOURNAL ON COMPUTING Trevisan, L. 2012; 41 (6): 1769-1786

    View details for DOI 10.1137/090773714

    View details for Web of Science ID 000312600700018

  • Approximating the Expansion Profile and Almost Optimal Local Graph Clustering 2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) Gharan, S. O., Trevisan, L. 2012: 187-196
  • Better Pseudorandom Generators from Milder Pseudorandom Restrictions. FOCS Gopalan, P., Meka, R., Reingold, O., Trevisan, L., Vadhan, Salil, P. 2012: 120-129
  • Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. CoRR abs/1204.2021 Gharan, S. O., Trevisan, L. 2012
  • Pseudorandomness and derandomization. ACM Crossroads Trevisan, L. 2012; 3 (18): 27-31
  • A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. CoRR abs/1212.1831 Gharan, S. O., Trevisan, L. 2012
  • Multi-way spectral partitioning and higher-order cheeger inequalities. STOC Lee, James, R., Gharan, S. O., Trevisan, L. 2012: 1117-1130
  • Information spreading in dynamic graphs. PODC Clementi, Andrea, E. F., Silvestri, R., Trevisan, L. 2012: 37-46
  • Better Pseudorandom Generators from Milder Pseudorandom Restrictions. CoRR abs/1210.0049 Gopalan, P., Meka, R., Reingold, O., Trevisan, L., Vadhan, Salil, P. 2012
  • Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. FOCS Gharan, S. O., Trevisan, L. 2012: 187-196
  • From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography Goldreich, O., Sudan, M., Trevisan, L. 2011: 109-113
  • Dense Model Theorems and Their Applications THEORY OF CRYPTOGRAPHY Trevisan, L. 2011; 6597: 55-57
  • Multi-way spectral partitioning and higher-order Cheeger inequalities. CoRR abs/1111.1055 James, R., Lee, Gharan, S. O., Trevisan, L. 2011
  • Information Spreading in Dynamic Graphs. CoRR abs/1111.0583 Clementi, Andrea, E.F., Silvestri, R., Trevisan, L. 2011
  • A Higher-Order Cheeger's Inequality. CoRR abs/1107.2686 Gharan, S. O., Trevisan, L. 2011
  • Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. CRYPTO De, A., Trevisan, L., Tulsiani, M. 2010: 649-665
  • The Program-Enumeration Bottleneck in Average-Case Complexity Theory 25TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY - CCC 2010 Trevisan, L. 2010: 88-95
  • Improved Pseudorandom Generators for Depth 2 Circuits. APPROX-RANDOM De, A., Etesami, O., Trevisan, L., Tulsiani, M. 2010: 504-517
  • Foreword. Algorithmica Chekuri, C., Trevisan, L. 2009; 1 (55): 111-112
  • Pseudorandom Bit Generators That Fool Modular Sums. APPROX-RANDOM Lovett, S., Reingold, O., Trevisan, L., Vadhan, Salil, P. 2009: 615-630
  • Max cut and the smallest eigenvalue. STOC Trevisan, L. 2009: 263-272
  • Guest column: additive combinatorics and theoretical computer science SIGACT News Trevisan, L. 2009; 2 (40): 50-66
  • Gowers Uniformity, Influence of Variables, and PCPs. SIAM J. Comput. Samorodnitsky, A., Trevisan, L. 2009; 1 (39): 323-360
  • Extractors Using Hardness Amplification. SIGACT News De, A., Trevisan, L. 2009: 462-475
  • Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms. TCC Cook, J., Etesami, O., Miller, R., Trevisan, L. 2009: 521-538
  • Average-case Complexity. FOCS Trevisan, L. 2008: 11
  • Max Cut and the Smallest Eigenvalue. CoRR abs/0806.1978 Trevisan, L. 2008
  • Learning Heavy Fourier Coefficients of Boolean Functions. Encyclopedia of Algorithms Trevisan, L. 2008
  • Approximation Algorithms for Unique Games. Theory of Computing Trevisan, L. 2008; 1 (4): 111-128
  • Dense Subsets of Pseudorandom Sets. FOCS Reingold, O., Trevisan, L., Tulsiani, M., Vadhan, Salil, P. 2008: 76-85
  • Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity Trevisan, L., Vadhan, Salil, P. 2007; 4 (16): 331-364
  • Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. STOC Schoenebeck, G., Trevisan, L., Tulsiani, M. 2007: 302-310
  • Fun with Sub-linear Time Algorithms. FUN Trevisan, L. 2007: 15
  • Amplifying Collision Resistance: A Complexity-Theoretic Treatment. CRYPTO Canetti, R., Rivest, Ronald, L., Sudan, M., Trevisan, L., Vanhan, Salil, P., Wee, H. 2007: 264-283
  • Gowers uniformity, influence of variables, and PCPs STOC Samorodnitsky, A., Trevisan, L. 2006: 11-20
  • Pseudorandomness and Combinatorial Constructions. CoRR abs/cs/0601100 Trevisan, L. 2006
  • Pseudorandom walks on regular digraphs and the RL vs. L problem. STOC Reingold, O., Trevisan, L., Vadhan, Salil, P. 2006: 457-466
  • Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity Goldreich, O., Karloff, Howard, J., Schulman, Leonard, J., Trevisan, L. 2006; 3 (15): 263-296
  • On epsilon-biased generators in NC0. Random Struct. Algorithms Mossel, E., Shpilka, A., Trevisan, L. 2006; 1 (29): 56-81
  • Average-Case Complexity. CoRR abs/cs/0606037 Bogdanov, A., Trevisan, L. 2006
  • Average-Case Complexity. Foundations and Trends in Theoretical Computer Science Bogdanov, A., Trevisan, L. 2006; 1 (2)
  • On Worst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput. Bogdanov, A., Trevisan, L. 2006; 4 (36): 1119-1159
  • Compression of Samplable Sources. Computational Complexity Trevisan, L., Vadhan, Salil, P., Zuckerman, D. 2005; 3 (14): 186-227
  • On uniform amplification of hardness in NP. STOC Trevisan, L. 2005: 31-38
  • Bounds on the Efficiency of Generic Cryptographic Constructions. SIAM J. Comput. Gennaro, R., Gertner, Y., Katz, J., Trevisan, L. 2005; 1 (35): 217-246
  • Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. Chazelle, B., Rubinfeld, R., Trevisan, L. 2005; 6 (34): 1370-1379
  • The Complexity of Making Unique Choices: Approximating 1-in-k SAT. APPROX-RANDOM Guruswami, V., Trevisan, L. 2005: 99-110
  • The approximability of non-Boolean satisfiability problems and restricted integer programming. Theor. Comput. Sci. Serna, Maria, J., Trevisan, L., Xhafa, F. 2005; 1-3 (332): 123-139
  • Approximating Succinct MaxSat. J. Log. Comput. Schallhart, C., Trevisan, L. 2005; 4 (15): 551-557
  • On Hardness Amplification of One-Way Functions. TCC Lin, Henry, C., Trevisan, L., Wee, H. 2005: 34-49
  • Hierarchies for semantic classes. STOC Fortnow, L., Santhanam, R., Trevisan, L. 2005: 348-355
  • Approximation Algorithms for Unique Games. FOCS Trevisan, L. 2005: 197-205
  • Gowers Uniformity, Influence of Variables, and PCPs. CoRR abs/math/0510264 Samorodnitsky, A., Trevisan, L. 2005
  • List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument. TCC Dwork, C., Shaltiel, R., Smith, A., Trevisan, L. 2004: 101-120
  • A Note on Approximate Counting for k-DNF. APPROX-RANDOM Trevisan, L. 2004: 417-426
  • Some Applications of Coding Theory in Computational Complexity. CoRR cs.CC/0409044 Trevisan, L. 2004
  • Inapproximability of Combinatorial Optimization Problems. CoRR cs.CC/0409043 Trevisan, L. 2004
  • On Local Versus Global Satisfiability SIAM J. Discrete Math. Trevisan, L. 2004; 4 (17): 541-547
  • Notions of Reducibility between Cryptographic Primitives. TCC Reingold, O., Trevisan, L., Vadhan, Salil, P. 2004: 1-20
  • On e-Biased Generators in NC0. FOCS Mossel, E., Shpilka, A., Trevisan, L. 2003: 136-145
  • Three theorems regarding testing graph properties. Random Struct. Algorithms Goldreich, O., Trevisan, L. 2003; 1 (23): 23-57
  • On Worst-Case to Average-Case Reductions for NP Problems. FOCS Bogdanov, A., Trevisan, L. 2003: 308-317
  • Error-Correcting Codes in Complexity Theory. CIAC Trevisan, L. 2003; 4
  • List-Decoding Using The XOR Lemma. FOCS Trevisan, L. 2003: 126-135
  • Counting Distinct Elements in a Data Stream. RANDOM Bar-Yossef, A., Jayram, T., S., Kumar, R., Sivakumar, D., Trevisan, L. 2002: 1-10
  • A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. FOCS Bogdanov, A., Obata, K., Trevisan, L. 2002: 93-102
  • Error-Correcting Codes and Pseudorandom Projections. RANDOM-APPROX Trevisan, L. 2001: 7-9
  • The approximability of constraint satisfaction problems SIAM JOURNAL ON COMPUTING Khanna, S., Sudan, M., Trevisan, L., Williamson, D. P. 2001; 30 (6): 1863-1920
  • Three Theorems Regarding Testing Graph Properties. FOCS Goldreich, O., Trevisan, L. 2001: 460-469
  • Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP Chazelle, B., Rubinfeld, R., Trevisan, L. 2001: 190-200
  • Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. Sudan, M., Trevisan, L., Vadhan, Salil, P. 2001; 2 (62): 236-266
  • On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. Inf. Comput. Crescenz, P., Silvestri, R., Trevisan, L. 2001; 1 (167): 10-26
  • Approximating layout problems on random graphs. Discrete Mathematics Díaz, J., Petit, J., Serna, Maria, J., Trevisan, L. 2001; 1-3 (235): 245-253
  • Non-approximability results for optimization problems on bounded degree instances. STOC Trevisan, L. 2001: 453-461
  • Extractors and pseudorandom generators. J. ACM Trevisan, L. 2001; 4 (48): 860-879
  • On Approximation Scheme Preserving Reducibility and Its Applications. Theory Comput. Syst. Crescenzi, P., Trevisan, L. 2000; 1 (33): 1-16
  • When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. SIAM J. Comput. Trevisan, L. 2000; 2 (30): 475-485
  • Extracting Randomness from Samplable Distributions. FOCS Trevisan, L., Vadhan, Salil, P. 2000: 32-42
  • A complexity analysis of bisimilarity for value-passing processes. Theor. Comput. Sci. Boreal, M., Trevisan, L. 2000; 1-2 (238): 313-345
  • Lower Bounds on the Efficiency of Generic Cryptographic Constructions. IACR Cryptology ePrint Archive Gennaro, R., Trevisan, L. 2000; 17
  • Lower Bounds on the Efficiency of Generic Cryptographic Constructions. Electronic Colloquium on Computational Complexity (ECCC) Gennaro, R., Trevisan, L. 2000; 22 (7)
  • Lower Bounds on the Efficiency of Generic Cryptographic Constructions. FOCS Gennaro, R., Trevisan, L. 2000: 305-313
  • Interactive and probabilistic proof-checking. Ann. Pure Appl. Logic Trevisan, L. 2000; 1-3 (104): 325-342
  • Gadgets, Approximation, and Linear Programming. SIAM J. Comput. Trevisan, L., Sorkin, Gregory, B., Sudan, M., Williamson, David, P. 2000; 6 (29): 2074-2097
  • Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming". Algorithmica Trevisan, L. 2000; 2 (27): 115-119
  • Approximating Satisfiable Satisfiability Problems. Algorithmica Trevisan, L. 2000; 1 (28): 145-172
  • A PCP characterization of NP with optimal amortized query complexity. STOC Samorodnitsky, A., Trevisan, L. 2000: 191-199
  • On the efficiency of local decoding procedures for error-correcting codes STOC Katz, J., Trevisan, L. 2000: 80-86
  • Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). STOC Trevisan, L. 1999: 141-148
  • Max NP-completeness Made Easy. Theor. Comput. Sci. Crescenzi, P., Trevisan, L. 1999; 1-2 (225): 65-79
  • Weak Random Sources, Hitting Sets, and BPP Simulations. SIAM J. Comput. Andreev, Alex, E., Clementi, Andrea, E. F., Rolim, José, D. P., Trevisan, L. 1999; 6 (28): 2103-2116
  • Structure in Approximation Classes. SIAM J. Comput. Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L. 1999; 5 (28): 1759-1782
  • Pseudorandom Generators Without the XOR Lemma (Extended Abstract). STOC Sudan, M., Trevisan, L., Vadhan, Salil, P. 1999: 537-546
  • Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints. Theor. Comput. Sci. Clementi, Andrea, E.F., Trevisan, L. 1999; 1-2 (225): 113-128
  • A Tight Characterization of NP with 3 Query PCPs. FOCS Guruswami, V., Lewin, D., Sudan, M., Trevisan, L. 1998: 8-17
  • The Parallel Complexity of Positive Linear Programming. Parallel Processing Letters Trevisan, L., Xhafa, F. 1998; 4 (8): 527-533
  • The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. STACS Serna, Maria, J., Trevisan, L., Xhafa, F. 1998: 488-498
  • Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). STOC Trevisan, L. 1998: 299-308
  • Recent Advances Towards Proving P = BPP. Bulletin of the EATCS Clementi, Andrea, E.F., Rolim, José, D. P., Trevisan, L. 1998; 64
  • Parallel Approximation Algorithms by Positive Linear Programming. Algorithmica Trevisan, L. 1998; 1 (21): 72-88
  • Probabilistically Checkable Proofs with Low Amortized Query Complexity. FOCS Sudan, M., Trevisan, L. 1998: 18-27
  • A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms. J. Comb. Optim. Rolim, Jose, D.P., Trevisan, L. 1998; 3 (2): 219-236
  • Approximating Satisfiable Satisfiability Problems (Extended Abstract). ESA Trevisan, L. 1997: 472-485
  • Weak Random Sources, Hitting Sets, and BPP Simulations. FOCS Andreev, Alexander, E., Clementi, Andrea, E.F., Rolim, José, D.P., Trevisan, L. 1997: 264-272
  • When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). STOC Trevisan, L. 1997: 21-29
  • On the Efficiency of Polynomial Time Approximation Schemes. Inf. Process. Lett. Cesati, M., Trevisan, L. 1997; 4 (64): 165-171
  • A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees. Inf. Process. Lett. Trevisan, L. 1996; 5 (57): 231-236
  • On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem. ITA Crescenzi, P., Trevisan, L. 1996; 5 (30): 431-441
  • Bisimilarity Problems Requiring Exponential Time. MFCS Boreale, M., Trevisan, L. 1996: 230-241
  • To Weight or Not to Weight: Where is the Question? ISTCS Crescenzi, P., Silvestri, R., Trevisan, L. 1996: 68-77
  • Positive Linear Programming, Parallel Approximation and PCP's. ESA Trevisan, L. 1996: 62-75
  • Improved Non-approximability Results for Vertex Cover with Density Constraints. COCOON Clementi, Andrea, E.F., Trevisan, L. 1996: 333-342
  • Gadgets, Approximation, and Linear Programming (extended abstract). FOCS Trevisan, L., Sorkin, Gregory, B., Sudan, M., Williamson, David, P. 1996: 617-626
  • Structure in Approximation Classes (Extended Abstract). COCOON Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L. 1995: 539-548
  • On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract). FSTTCS Boreale, M., Trevisan, L. 1995: 294-308
  • Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract). WG Crescenzi, P., Trevisan, L. 1994: 130-139
  • On Approximation Scheme Preserving Reducability and Its Applications. FSTTCS Crescenzi, P., Trevisan, L. 1994: 330-341

Conference Proceedings


  • Theory and Applications of Models of Computation, 10th International Conference, TAMC 2014, Hong Kong, China, May 20-22, 2014. edited by Chan, T.H., Hubert, Lau, L. C., Trevisan, L. 2014
  • On the One-Way Function Candidate Proposed by Goldreich Cook, J., Etesami, O., Miller, R., Trevisan, L. edited by Goemans, Michel, X., Jansen, K., Rolim, José D., P. 2012
  • Better pseudorandom generators from milder pseudorandom restrictions. Gopalan, P., Meka, R., Reingold, O., Trevisan, L., Vadhan, Salil, P. edited by Chekuri, C., Jansen, K., Rolim, José D., P. 2012
  • A Derandomized Switching Lemma and an Improved Derandomization of AC0. Trevisan, L. 2012
  • The Program-Enumeration Bottleneck in Average-Case Complexity Theory. Trevisan, L. 2010
  • Non-uniform attacks against one-way functions and PRGs. De, A., Trevisan, L., Tulsiani, M. 2009
  • Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Trevisan, L., Tulsiani, M., Vadhan, Salil, P. 2009
  • Improved Pseudorandom Generators for Depth 2 Circuits. De, A., Etesami, O., Trevisan, L., Tulsiani, M. 2009
  • Dense Subsets of Pseudorandom Sets. Reingold, O., Trevisan, L., Tulsiani, M., Vadhan, Salil, P. 2008
  • Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Trevisan, Tulsiani, M., Vadhan, Salil, P. 2008
  • A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Schoenebeck, G., Trevisan, L., Tulsiani, M. 2007
  • Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. Schoenebeck, G., Trevisan, L., Tulsian, M. 2006
  • Pseudorandomness and Combinatorial Constructions. Trevisan, L. 2006
  • A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Schoenebeck, G., Trevisan, L., Tulsian, M. 2006
  • Average-Case Complexity. Bogdanov, G., Trevisan, L. 2006
  • Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA edited by Chekuri, C., Jansen, K., Rolim, José, D. P. 2005
  • Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem. Reingold, O., Trevisan, L. 2005
  • On Worst-Case to Average-Case Reductions for NP Problems. Bogdanov, A., Trevisan, L. 2005
  • Gowers Uniformity, Influence of Variables, and PCPs. Samorodnitsky, A., Trevisan, L. 2005
  • Compression of Samplable Sources. Trevisan, L., Vadhan, Salil, P., Zuckerman, D. 2005
  • Approximation Algorithms for Unique Games. Trevisan, L. 2005
  • From logarithmic advice to single-bit advice. Goldreich, O., Sudan, M., Trevisan, L. 2004
  • Some Applications of Coding Theory in Computational Complexity. Trevisan, L. 2004
  • Promise Hierarchies. Fortnow, L., Santhanam, R., Trevisan, L. 2004
  • Lower Bounds for Testing Bipartiteness in Dense Graphs. Bogdanov, A., Trevisan, L. 2004
  • Inapproximability of Combinatorial Optimization Problems. Trevisan, L. 2004
  • Compression of Samplable Sources. Trevisan, L., Vadhan, Salil, P., Zuckerman, D. 2004
  • On epsilon-Biased Generators in NC0. Mossel, E., Shpilkab, A., Trevisan, L. 2003
  • List Decoding Using the XOR Lemma. Trevisan, L. 2003
  • An epsilon-Biased Generator in NC0. Trevisan, L. 2003
  • A Note on Deterministic Approximate Counting for k-DNF. Trevisan, L. 2002
  • Lower Bounds for Testing Bipartiteness in Dense Graphs. Bogdanov, A., Trevisan, L. 2002
  • Three Theorems regarding Testing Graph Properties. Goldreich, O., Trevisan, L. 2001
  • Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. Goldreich, O., Karloff, Howard, J., Schulman, Leonard, J., Trevisan, L. 2001
  • Pseudorandom Generators without the XOR Lemma (Abstract). Sudan, M., Trevisan, L., Vadhan, Salil, P. 1999
  • Probabilistically checkable proofs with low amortized query complexity. Sudan, M., Trevisan, L. 1998
  • Pseudorandom generators without the XOR Lemma. Sudan, M., Trevisan, L., Vadhan, Salil, P. 1998
  • Constructions of Near-Optimal Extractors Using Pseudo-Random Generators. Trevisan, L. 1998
  • A tight characterization of NP with 3 query PCPs. Guruswami, V., Lewin, D., Sudan, M., Trevisan, L. 1998
  • Recycling Queries in PCPs and in Linearity Tests. Trevisan, L. 1998
  • Weak Random Sources, Hitting Sets, and BPP Simulations. Andreev, Alexander, E., Clementi, Andrea, E.F., Rolim, José, D.P., Trevisan, L. 1997
  • MAX NP-Completeness Made Easy. Crescenzi, P., Trevisan, L. 1997
  • Constraint Satisfaction: The Approximability of Minimization Problems. Khanna, S., Sudan, M., Trevisan, L. 1997
  • On the Efficiency of Polynomial Time Approximation Schemes. Cesati, M., Trevisan, L. 1997
  • On Local versus Global Satisfiability. Trevisan, L. 1997
  • Structure in Approximation Classes. Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L. 1996
  • On the Approximability of the Multi-dimensional Euclidean TSP. Trevisan, L. 1996
  • Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints. Clementi, Andrea, E.F., Trevisan, L. 1996
  • Constraint satisfaction: The approximability of minimization problems. Khanna, S., Sudan, M., Trevisan, L. 1996