Papers by Luca Trevisan

Unpublished

• Jess Banks and Luca Trevisan
  Vector Colorings of Random, Ramanujan, and Large-Girth Graphs
  Preprint, 2019
  arXiv:1907.02539
• Luca Trevisan
  Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
  Preprint, 2011 (posted online in 2013)
  arXiv:1303.2730
• Shayan Oveis Gharan, Luca Trevisan
  A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
  Preprint, 2012
  arXiv:1212.2701

2024

• 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
• 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

2023

• Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus.
  On the Role of Memory in Robust Opinion Dynamics
  In Proc. of IJCAI 2023
  arXiv:2302.08600
• Tommaso D'Orsi and Luca Trevisan
  A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
  In Proc. of CCC 2023, pages 27:1-27:16
  arXiv:2204.10881

2022

• 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
• Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi
  Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks
  In Proc. of LATIN 2022
  arXiv:2103.16398
• Antares Chen, Jonathan Shi and Luca Trevisan
  Cut Sparsification of the Clique Beyond the Ramanujan Bound
  In Proc. of SODA 2022
  arXiv:2008.05648

2021

• 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

2020

• Sam Hopkins, Tselil Schramm and Luca Trevisan
  Subexponential LPs Approximate Max Cut
  In Proc. of FOCS 2020
  arXiv:1911.10304
• Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca and Luca Trevisan
  Consensus vs Broadcast, with and w/o Noise
  In Proc. of ITCS 2020
  arXiv:1807.05626
• Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan
  Finding a Bounded-Degree Expander Inside a Dense One
  In Proc. of SODA 2020
  arXiv:1811.10316
• 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

2019

• Nikhil Bansal, Ola Svensson and Luca Trevisan
  New Notions and Constructions of Sparsification for Graphs and Hypergraphs
  In Proc. of FOCS 2019
  arXiv:1905.01495
• 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

2018

• Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
  Friend or Foe? Population Protocols can perform Community Detection
  In Proc. of ESA 2018, pp. 7:1-7:13
  arXiv:1703.05045
• 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
• 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

2017

• 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
• 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
• 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`

2016

• 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
• 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
• Guy Kindler, Alexandra Kolla, Luca Trevisan
  Approximation of non-boolean 2CSP
  In Proc. of SODA 2016, pp. 1705-1714
  arXiv:1504.00681

2015

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

2014

• 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
• Shayan Oveis Gharan, Luca Trevisan
  Partitioning into Expanders
  In Proc. of SODA 2014, pp. 1256-1266
  arXiv:1309.3223

2013

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

2012

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

2010

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

2009

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

2008

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

2007

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

2006

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

2005

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

2004

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

2003

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

2002

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

2001

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

2000

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

1999

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

1998

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

1997

• Alexander E. Andreev, Andrea E.F. Clementi, Jose D.P. Rolim, and Luca Trevisan. 
  Weak Random Sources, Hitting Sets, and BPP Simulations
  SIAM Journal on Computing, 28(6):2103-2116, 1999.
  Preliminary version: Proc. of  38th IEEE FOCS, 1997.
  [Final version][Conference Proceedings]
• 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]
• S. Khanna, M. Sudan,  L. Trevisan and D. Williamson
  The Approximability of Constraint Satisfaction Problems.
  SIAM J. of Computing, 30(6):1863-1920, 2001.
  [Journal Submission]
• 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]
• M. Cesati and L. Trevisan
  On the Efficiency of Polynomial Time Approximation Schemes
  Information Processing Letters, 64(4):165-171, 1997.
  [Journal Submission]

1996

• L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson.
  Gadgets, Approximation, and Linear Programming.
  SIAM J. on Computing, 29(6):2074-2097, 2000
  Preliminary version in Proc. of the 37th IEEE FOCS, 1996.
  [Full version (revised 10/98)] [Conference Proceedings]
• 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]
• 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]
• 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]
• L. Trevisan.
  A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees.
  Information Processing Letters, 57(5):231-236, 1996.
  

1995

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

1994

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