Luca Trevisan

T.-H. Hubert Chan, Lap Chi Lau, Luca Trevisan (Eds.): Theory and Applications of Models of Computation, 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. Lecture Notes in Computer Science 7876, Springer 2013, isbn 978-3-642-38235-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. CoRR abs/1301.5584 (2013)

Luca Trevisan: Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut? CoRR abs/1303.2730 (2013)

Shayan Oveis Gharan, Luca Trevisan: Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank. CoRR abs/1304.2060 (2013)

Luca Trevisan: Pseudorandomness and derandomization. ACM Crossroads 18(3): 27-31 (2012)

Luca Trevisan: Max Cut and the Smallest Eigenvalue. SIAM J. Comput. 41(6): 1769-1786 (2012)

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan: Better Pseudorandom Generators from Milder Pseudorandom Restrictions. FOCS 2012: 120-129

Shayan Oveis Gharan, Luca Trevisan: Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. FOCS 2012: 187-196

Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan: Information spreading in dynamic graphs. PODC 2012: 37-46

James R. Lee, Shayan Oveis Gharan, Luca Trevisan: Multi-way spectral partitioning and higher-order cheeger inequalities. STOC 2012: 1117-1130

Shayan Oveis Gharan, Luca Trevisan: Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. CoRR abs/1204.2021 (2012)

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan: Better Pseudorandom Generators from Milder Pseudorandom Restrictions. CoRR abs/1210.0049 (2012)

Shayan Oveis Gharan, Luca Trevisan: A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. CoRR abs/1212.1831 (2012)

Shayan Oveis Gharan, Luca Trevisan: A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues. CoRR abs/1212.2701 (2012)

Luca Trevisan: A Derandomized Switching Lemma and an Improved Derandomization of AC0. Electronic Colloquium on Computational Complexity (ECCC) 19: 116 (2012)

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan: Better pseudorandom generators from milder pseudorandom restrictions. Electronic Colloquium on Computational Complexity (ECCC) 19: 123 (2012)

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan: On the One-Way Function Candidate Proposed by Goldreich. Electronic Colloquium on Computational Complexity (ECCC) 19: 175 (2012)

Oded Goldreich, Madhu Sudan, Luca Trevisan: From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography 2011: 109-113

Luca Trevisan: Dense Model Theorems and Their Applications. TCC 2011: 55-57

Shayan Oveis Gharan, Luca Trevisan: A Higher-Order Cheeger's Inequality. CoRR abs/1107.2686 (2011)

Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan: Information Spreading in Dynamic Graphs. CoRR abs/1111.0583 (2011)

James R. Lee, Shayan Oveis Gharan, Luca Trevisan: Multi-way spectral partitioning and higher-order Cheeger inequalities. CoRR abs/1111.1055 (2011)

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani: Improved Pseudorandom Generators for Depth 2 Circuits. APPROX-RANDOM 2010: 504-517

Luca Trevisan: The Program-Enumeration Bottleneck in Average-Case Complexity Theory. IEEE Conference on Computational Complexity 2010: 88-95

Anindya De, Luca Trevisan, Madhur Tulsiani: Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. CRYPTO 2010: 649-665

Luca Trevisan: The Program-Enumeration Bottleneck in Average-Case Complexity Theory. Electronic Colloquium on Computational Complexity (ECCC) 17: 34 (2010)

Chandra Chekuri, Luca Trevisan: Foreword. Algorithmica 55(1): 111-112 (2009)

Alex Samorodnitsky, Luca Trevisan: Gowers Uniformity, Influence of Variables, and PCPs. SIAM J. Comput. 39(1): 323-360 (2009)

Luca Trevisan: Guest column: additive combinatorics and theoretical computer science. SIGACT News 40(2): 50-66 (2009)

Anindya De, Luca Trevisan: Extractors Using Hardness Amplification. APPROX-RANDOM 2009: 462-475

Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan: Pseudorandom Bit Generators That Fool Modular Sums. APPROX-RANDOM 2009: 615-630

Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. IEEE Conference on Computational Complexity 2009: 126-136

Luca Trevisan: Max cut and the smallest eigenvalue. STOC 2009: 263-272

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan: Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms. TCC 2009: 521-538

Anindya De, Luca Trevisan, Madhur Tulsiani: Non-uniform attacks against one-way functions and PRGs. Electronic Colloquium on Computational Complexity (ECCC) 16: 113 (2009)

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani: Improved Pseudorandom Generators for Depth 2 Circuits. Electronic Colloquium on Computational Complexity (ECCC) 16: 141 (2009)

Luca Trevisan: Approximation Algorithms for Unique Games. Theory of Computing 4(1): 111-128 (2008)

Luca Trevisan: Average-case Complexity. FOCS 2008: 11

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Dense Subsets of Pseudorandom Sets. FOCS 2008: 76-85

Luca Trevisan: Learning Heavy Fourier Coefficients of Boolean Functions. Encyclopedia of Algorithms 2008

Luca Trevisan: Max Cut and the Smallest Eigenvalue. CoRR abs/0806.1978 (2008)

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Dense Subsets of Pseudorandom Sets. Electronic Colloquium on Computational Complexity (ECCC) 15(045) (2008)

Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan: Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Electronic Colloquium on Computational Complexity (ECCC) 15(103) (2008)

Luca Trevisan, Salil P. Vadhan: Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Computational Complexity 16(4): 331-364 (2007)

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani: A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. IEEE Conference on Computational Complexity 2007: 205-216

Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee: Amplifying Collision Resistance: A Complexity-Theoretic Treatment. CRYPTO 2007: 264-283

Luca Trevisan: Fun with Sub-linear Time Algorithms. FUN 2007: 15

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani: Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. STOC 2007: 302-310

Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan: Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity 15(3): 263-296 (2006)

Andrej Bogdanov, Luca Trevisan: Average-Case Complexity. Foundations and Trends in Theoretical Computer Science 2(1) (2006)

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On epsilon-biased generators in NC⁰. Random Struct. Algorithms 29(1): 56-81 (2006)

Andrej Bogdanov, Luca Trevisan: On Worst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput. 36(4): 1119-1159 (2006)

Alex Samorodnitsky, Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. STOC 2006: 11-20

Omer Reingold, Luca Trevisan, Salil P. Vadhan: Pseudorandom walks on regular digraphs and the RL vs. L problem. STOC 2006: 457-466

Luca Trevisan: Pseudorandomness and Combinatorial Constructions. CoRR abs/cs/0601100 (2006)

Andrej Bogdanov, Luca Trevisan: Average-Case Complexity. CoRR abs/cs/0606037 (2006)

Luca Trevisan: Pseudorandomness and Combinatorial Constructions. Electronic Colloquium on Computational Complexity (ECCC)(013) (2006)

Andrej Bogdanov, Luca Trevisan: Average-Case Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(073) (2006)

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani: A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Electronic Colloquium on Computational Complexity (ECCC) 13(098) (2006)

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani: Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. Electronic Colloquium on Computational Complexity (ECCC) 13(132) (2006)

Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. Computational Complexity 14(3): 186-227 (2005)

Christian Schallhart, Luca Trevisan: Approximating Succinct MaxSat. J. Log. Comput. 15(4): 551-557 (2005)

Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. 34(6): 1370-1379 (2005)

Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan: Bounds on the Efficiency of Generic Cryptographic Constructions. SIAM J. Comput. 35(1): 217-246 (2005)

Maria J. Serna, Luca Trevisan, Fatos Xhafa: The approximability of non-Boolean satisfiability problems and restricted integer programming. Theor. Comput. Sci. 332(1-3): 123-139 (2005)

Venkatesan Guruswami, Luca Trevisan: The Complexity of Making Unique Choices: Approximating 1-in- k SAT. APPROX-RANDOM 2005: 99-110

Luca Trevisan: Approximation Algorithms for Unique Games. FOCS 2005: 197-205

Luca Trevisan: On uniform amplification of hardness in NP. STOC 2005: 31-38

Lance Fortnow, Rahul Santhanam, Luca Trevisan: Hierarchies for semantic classes. STOC 2005: 348-355

Henry C. Lin, Luca Trevisan, Hoeteck Wee: On Hardness Amplification of One-Way Functions. TCC 2005: 34-49

Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan (Eds.): 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, August 22-24, 2005, Proceedings. Lecture Notes in Computer Science 3624, Springer 2005, isbn 3-540-28239-4

Alex Samorodnitsky, Luca Trevisan: Gowers Uniformity, Influence of Variables, and PCPs. CoRR abs/math/0510264 (2005)

Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. Electronic Colloquium on Computational Complexity (ECCC)(012) (2005)

Andrej Bogdanov, Luca Trevisan: On Worst-Case to Average-Case Reductions for NP Problems. Electronic Colloquium on Computational Complexity (ECCC)(015) (2005)

Omer Reingold, Luca Trevisan, Salil P. Vadhan: Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem. Electronic Colloquium on Computational Complexity (ECCC)(022) (2005)

Luca Trevisan: Approximation Algorithms for Unique Games. Electronic Colloquium on Computational Complexity (ECCC)(034) (2005)

Alex Samorodnitsky, Luca Trevisan: Gowers Uniformity, Influence of Variables, and PCPs. Electronic Colloquium on Computational Complexity (ECCC)(116) (2005)

Luca Trevisan: On Local Versus Global Satisfiability. SIAM J. Discrete Math. 17(4): 541-547 (2004)

Luca Trevisan: A Note on Approximate Counting for k-DNF. APPROX-RANDOM 2004: 417-426

Luca Trevisan, Salil P. Vadhan, David Zuckerman: Compression of Samplable Sources. IEEE Conference on Computational Complexity 2004: 1-14

Andrej Bogdanov, Luca Trevisan: Lower Bounds for Testing Bipartiteness in Dense Graphs. IEEE Conference on Computational Complexity 2004: 75-81

Omer Reingold, Luca Trevisan, Salil P. Vadhan: Notions of Reducibility between Cryptographic Primitives. TCC 2004: 1-20

Cynthia Dwork, Ronen Shaltiel, Adam Smith, Luca Trevisan: List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument. TCC 2004: 101-120

Luca Trevisan: Inapproximability of Combinatorial Optimization Problems. CoRR cs.CC/0409043 (2004)

Luca Trevisan: Some Applications of Coding Theory in Computational Complexity. CoRR cs.CC/0409044 (2004)

Luca Trevisan: Some Applications of Coding Theory in Computational Complexity. Electronic Colloquium on Computational Complexity (ECCC)(043) (2004)

Luca Trevisan: Inapproximability of Combinatorial Optimization Problems. Electronic Colloquium on Computational Complexity (ECCC)(065) (2004)

Oded Goldreich, Madhu Sudan, Luca Trevisan: From logarithmic advice to single-bit advice. Electronic Colloquium on Computational Complexity (ECCC)(093) (2004)

Lance Fortnow, Rahul Santhanam, Luca Trevisan: Promise Hierarchies. Electronic Colloquium on Computational Complexity (ECCC)(098) (2004)

Oded Goldreich, Luca Trevisan: Three theorems regarding testing graph properties. Random Struct. Algorithms 23(1): 23-57 (2003)

Luca Trevisan: Error-Correcting Codes in Complexity Theory. CIAC 2003: 4

Luca Trevisan: List-Decoding Using The XOR Lemma. FOCS 2003: 126-135

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On e-Biased Generators in NC0. FOCS 2003: 136-145

Andrej Bogdanov, Luca Trevisan: On Worst-Case to Average-Case Reductions for NP Problems. FOCS 2003: 308-317

Luca Trevisan: An epsilon-Biased Generator in NC0. Electronic Colloquium on Computational Complexity (ECCC) 10(013) (2003)

Luca Trevisan: List Decoding Using the XOR Lemma. Electronic Colloquium on Computational Complexity (ECCC)(042) (2003)

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On epsilon-Biased Generators in NC0. Electronic Colloquium on Computational Complexity (ECCC)(043) (2003)

Luca Trevisan, Salil P. Vadhan: Pseudorandomness and Average-Case Complexity via Uniform Reductions. IEEE Conference on Computational Complexity 2002: 129-138

Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel: Streaming Computation of Combinatorial Objects. IEEE Conference on Computational Complexity 2002: 165-174

Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan: Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. IEEE Conference on Computational Complexity 2002: 175-183

Andrej Bogdanov, Kenji Obata, Luca Trevisan: A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. FOCS 2002: 93-102

Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan: Counting Distinct Elements in a Data Stream. RANDOM 2002: 1-10

Andrej Bogdanov, Luca Trevisan: Lower Bounds for Testing Bipartiteness in Dense Graphs. Electronic Colloquium on Computational Complexity (ECCC)(064) (2002)

Luca Trevisan: A Note on Deterministic Approximate Counting for k-DNF. Electronic Colloquium on Computational Complexity (ECCC)(069) (2002)

Josep Díaz, Jordi Petit, Maria J. Serna, Luca Trevisan: Approximating layout problems on random graphs. Discrete Mathematics 235(1-3): 245-253 (2001)

Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan: On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. Inf. Comput. 167(1): 10-26 (2001)

Luca Trevisan: Extractors and pseudorandom generators. J. ACM 48(4): 860-879 (2001)

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. 62(2): 236-266 (2001)

Oded Goldreich, Luca Trevisan: Three Theorems Regarding Testing Graph Properties. FOCS 2001: 460-469

Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan: Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP 2001: 190-200

Luca Trevisan: Error-Correcting Codes and Pseudorandom Projections. RANDOM-APPROX 2001: 7-9

Luca Trevisan: Non-approximability results for optimization problems on bounded degree instances. STOC 2001: 453-461

Michel X. Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan (Eds.): Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18-20, 2001, Proceedings. Lecture Notes in Computer Science 2129, Springer 2001, isbn 3-540-42470-9

Oded Goldreich, Luca Trevisan: Three Theorems regarding Testing Graph Properties. Electronic Colloquium on Computational Complexity (ECCC) 8(10) (2001)

Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan: Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. Electronic Colloquium on Computational Complexity (ECCC)(080) (2001)

Luca Trevisan: Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming". Algorithmica 27(2): 115-119 (2000)

Luca Trevisan: Approximating Satisfiable Satisfiability Problems. Algorithmica 28(1): 145-172 (2000)

Luca Trevisan: Interactive and probabilistic proof-checking. Ann. Pure Appl. Logic 104(1-3): 325-342 (2000)

Pierluigi Crescenzi, Luca Trevisan: On Approximation Scheme Preserving Reducibility and Its Applications. Theory Comput. Syst. 33(1): 1-16 (2000)

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000)

Luca Trevisan: When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. SIAM J. Comput. 30(2): 475-485 (2000)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson: The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000)

Michele Boreale, Luca Trevisan: A complexity analysis of bisimilarity for value-passing processes. Theor. Comput. Sci. 238(1-2): 313-345 (2000)

Luca Trevisan: A Survey of Optimal PCP Characterizations of NP. IEEE Conference on Computational Complexity 2000: 146-

Luca Trevisan, Salil P. Vadhan: Extracting Randomness from Samplable Distributions. FOCS 2000: 32-42

Rosario Gennaro, Luca Trevisan: Lower Bounds on the Efficiency of Generic Cryptographic Constructions. FOCS 2000: 305-313

Jonathan Katz, Luca Trevisan: On the efficiency of local decoding procedures for error-correcting codes. STOC 2000: 80-86

Alex Samorodnitsky, Luca Trevisan: A PCP characterization of NP with optimal amortized query complexity. STOC 2000: 191-199

Rosario Gennaro, Luca Trevisan: Lower Bounds on the Efficiency of Generic Cryptographic Constructions. Electronic Colloquium on Computational Complexity (ECCC) 7(22) (2000)

Rosario Gennaro, Luca Trevisan: Lower Bounds on the Efficiency of Generic Cryptographic Constructions. IACR Cryptology ePrint Archive 2000: 17 (2000)

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan: Structure in Approximation Classes. SIAM J. Comput. 28(5): 1759-1782 (1999)

Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan: Weak Random Sources, Hitting Sets, and BPP Simulations. SIAM J. Comput. 28(6): 2103-2116 (1999)

Pierluigi Crescenzi, Luca Trevisan: Max NP-completeness Made Easy. Theor. Comput. Sci. 225(1-2): 65-79 (1999)

Andrea E. F. Clementi, Luca Trevisan: Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints. Theor. Comput. Sci. 225(1-2): 113-128 (1999)

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators without the XOR Lemma (Abstract). IEEE Conference on Computational Complexity 1999: 4

Luca Trevisan: Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). STOC 1999: 141-148

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators Without the XOR Lemma (Extended Abstract). STOC 1999: 537-546

Luca Trevisan: Parallel Approximation Algorithms by Positive Linear Programming. Algorithmica 21(1): 72-88 (1998)

Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan: Recent Advances Towards Proving P = BPP. Bulletin of the EATCS 64 (1998)

José D. P. Rolim, Luca Trevisan: A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms. J. Comb. Optim. 2(3): 219-236 (1998)

Luca Trevisan, Fatos Xhafa: The Parallel Complexity of Positive Linear Programming. Parallel Processing Letters 8(4): 527-533 (1998)

Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan: A Tight Characterization of NP with 3 Query PCPs. FOCS 1998: 8-17

Madhu Sudan, Luca Trevisan: Probabilistically Checkable Proofs with Low Amortized Query Complexity. FOCS 1998: 18-27

Maria J. Serna, Luca Trevisan, Fatos Xhafa: The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. STACS 1998: 488-498

Luca Trevisan: Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). STOC 1998: 299-308

Luca Trevisan: Recycling Queries in PCPs and in Linearity Tests. Electronic Colloquium on Computational Complexity (ECCC) 5(7) (1998)

Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan: A tight characterization of NP with 3 query PCPs. Electronic Colloquium on Computational Complexity (ECCC) 5(34) (1998)

Madhu Sudan, Luca Trevisan: Probabilistically checkable proofs with low amortized query complexity. Electronic Colloquium on Computational Complexity (ECCC) 5(40) (1998)

Luca Trevisan: Constructions of Near-Optimal Extractors Using Pseudo-Random Generators. Electronic Colloquium on Computational Complexity (ECCC) 5(55) (1998)

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom generators without the XOR Lemma. Electronic Colloquium on Computational Complexity (ECCC) 5(74) (1998)

Marco Cesati, Luca Trevisan: On the Efficiency of Polynomial Time Approximation Schemes. Inf. Process. Lett. 64(4): 165-171 (1997)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint Satisfaction: The Approximability of Minimization Problems. IEEE Conference on Computational Complexity 1997: 282-296

Luca Trevisan: Approximating Satisfiable Satisfiability Problems (Extended Abstract). ESA 1997: 472-485

Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan: Weak Random Sources, Hitting Sets, and BPP Simulations. FOCS 1997: 264-272

Luca Trevisan: When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). STOC 1997: 21-29

Marco Cesati, Luca Trevisan: On the Efficiency of Polynomial Time Approximation Schemes. Electronic Colloquium on Computational Complexity (ECCC) 4(1) (1997)

Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan: Weak Random Sources, Hitting Sets, and BPP Simulations. Electronic Colloquium on Computational Complexity (ECCC) 4(11) (1997)

Luca Trevisan: On Local versus Global Satisfiability. Electronic Colloquium on Computational Complexity (ECCC) 4(12) (1997)

Pierluigi Crescenzi, Luca Trevisan: MAX NP-Completeness Made Easy. Electronic Colloquium on Computational Complexity (ECCC) 4(39) (1997)

Luca Trevisan: A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees. Inf. Process. Lett. 57(5): 231-236 (1996)

Pierluigi Crescenzi, Luca Trevisan: On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem. ITA 30(5): 431-441 (1996)

Andrea E. F. Clementi, Luca Trevisan: Improved Non-approximability Results for Vertex Cover with Density Constraints. COCOON 1996: 333-342

Luca Trevisan: Positive Linear Programming, Parallel Approximation and PCP's. ESA 1996: 62-75

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626

Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan: To Weight or Not to Weight: Where is the Question? ISTCS 1996: 68-77

Michele Boreale, Luca Trevisan: Bisimilarity Problems Requiring Exponential Time. MFCS 1996: 230-241

Andrea E. F. Clementi, Luca Trevisan: Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints. Electronic Colloquium on Computational Complexity (ECCC) 3(16) (1996)

Luca Trevisan: On the Approximability of the Multi-dimensional Euclidean TSP. Electronic Colloquium on Computational Complexity (ECCC) 3(46) (1996)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint satisfaction: The approximability of minimization problems. Electronic Colloquium on Computational Complexity (ECCC) 3(64) (1996)

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan: Structure in Approximation Classes. Electronic Colloquium on Computational Complexity (ECCC) 3(66) (1996)

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan: Structure in Approximation Classes (Extended Abstract). COCOON 1995: 539-548

Michele Boreale, Luca Trevisan: On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract). FSTTCS 1995: 294-308

Pierluigi Crescenzi, Luca Trevisan: On Approximation Scheme Preserving Reducability and Its Applications. FSTTCS 1994: 330-341

Pierluigi Crescenzi, Luca Trevisan: Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract). WG 1994: 130-139