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
Luca Trevisan Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
Preprint, 2011 (posted online in 2013) arXiv:1303.2730
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
Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan Information spreading in dynamic graphs
In Proc. of PODC 2012, pp. 37-46 arXiv:1111.0583
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
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]
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 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, 2009 ECCC TR08-103
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)
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
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]
Andrej Bogdanov and Luca Trevisan On Worst-Case to Average-Case Reductions for NP Problems SIAM J. Comput. 36(4): 1119-1159 (2006)
Earlier version in Proc. of 44th
FOCS,
IEEE, pp. 308-317, 2003
[Draft full version: [ps][pdf]] [Conference
Proceedings]
Elchanan Mossel, Amir Shpilka and Luca
Trevisan On epsilon-Biased Generators in NC0 Random Structures and Algorithms,29(1):56-81, 2006
Also in Proc. of 44th
FOCS,
IEEE, pp. 136-145, 2003
[Manuscript]
Luca Trevisan and Salil Vadhan. Extracting Randomness from Samplable Distributions
In Proc. of 41st FOCS,
pages 32-42, IEEE, 2000 [Conference Proceedings]
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 [ps][pdf][Conference
Proceedings]
Alexander E. Andreev, Andrea E.F.
Clementi,
Jose
D.P. Rolim, and Luca Trevisan. Weak Random Sources, Hitting Sets, and BPP Simulations SIAM Journal on Computing, 28(6):2103-2116, 1999.
Preliminary version: Proc. of 38th
IEEE FOCS,1997. [Final
version][Conference
Proceedings][Abstract]
Cryptography
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]
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]
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]
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]
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
Alex Samorodnitsky and Luca Trevisan. Gowers Uniformity, Influence of Variables, and PCPs In Proc. of 38th STOC, ACM, 2006.
[Manuscript]
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]
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]
L. Trevisan
Non-approximability Results for Optimization Problems on Bounded
Degree Instances.
In Proc. of the 33rd ACM STOC, 2001 [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][Abstract]
Integrality Gap Instances
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]
Maria Serna, Luca Trevisan, and Fatos Xhafa.
The Parallel Approximability of Non-Boolean Constraint
Satisfaction
and Restricted Integer Programming. Theoretical Computer Science332(1-3):123-139, 2005
Preliminary version In Proceedings of the 15th STACS, LNCS 1373, Springer-Verlag, pages 488-498, 1998. [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][Abstract]
P. Crescenzi and L. Trevisan.
MAXNP-completeness Made Easy. Theoretical Computer Science, 225(1-2):65-79, 1999. [Journal
Submission][Abstract]
Sanjeev Khanna, Madhu Sudan, Luca Trevisan and David
Williamson.
The Approximability of Constraint Satisfaction Problems. SIAM J. of Computing, 30(6):1863-1920, 2001. [Journal
Submission][Abstract]
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]
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]
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]
Bernard
Chazelle, Ronitt Rubinfeld and Luca
Trevisan Approximating the Minimum Spanning Tree Weight in Sublinear Time SIAM J. on Computing34(6):1370-1379, 2005.
Preliminary version in Proc. of 28th
ICALP, pages 190-200, Springer-Verlag, 2001. [Conference Proceedings]
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]
L. Trevisan A Note on Deterministic Approximate Counting for k-DNF
In Proc. of APPROX-RANDOM, pages 417-426, 2004 [Preliminary version]
Christian Schallhart, Luca Trevisan Approximating Succinct MaxSat J. Log. Comput. 15(4): 551-557, 2005
J. Diaz, J. Petit, M. Serna and L. Trevisan
Approximating Layout Problems on Random Graphs Discrete Mathematics, 235(1-3):245-253, 2001.
L. Trevisan. On Local versus Global Satisfiability. SIAM
Journal on Discrete Mathematics. 17(4):541-547, 2004 [Preliminary
Version][Abstract]
L. Trevisan and F. Xhafa.
The Parallel Complexity of Positive Linear Programming. Parallel Processing Letters, 8(4):527-533, 1998. [Journal
Submission][Abstract]
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]
L. Trevisan.
A Note on Minimum-Area Upward Drawing of Complete and Fibonacci
Trees. Information Processing Letters, 57(5):231-236, 1996. [Journal
Submission][Abstract]
P.
Crescenzi and L. Trevisan On the Distributed Decision-Making Complexity of the Minimum
Vertex
Cover Problem. RAIRO, Theoretical Informatics and Applications, 30:431-441,
1996.
Preliminary version in Proceedings of the 20th WG,1995. [Journal
Submission][Conference
Proceedings ][Abstract]
Survey Papers
Luca Trevisan Pseudorandomness and derandomization ACM Crossroads 18(3): 27-31 (2012) [ACM Digital Library]
Luca Trevisan Additive Combinatorics and Theoretical Computer Science SIGACT News Complexity Column Number 63, 2009 [pdf]
Andrej Bogdanov and Luca Trevisan Average-Case Complexity Foundations and Trends in Theoretical Computer Science1(2), 2006 arXiv:cs/0606037
Luca Trevisan Pseudorandomness and Combinatorial Constructions In Proceedings of ICM 2006 arXiv:cs/0601100
Luca Trevisan Inapproximability of Combinatorial Optimization Problems
French version (translation by Bruno Escoffier) appeared in Optimisation
Combinatiore 2, (Vangelis Paschos, Editor), Hermes, 2005
English version: [ps][pdf]
Luca Trevisan Some Applications of Coding Theory
in Computational Complexity Survey Paper Quaderni di Matematica 13:347-424, 2004
Final version: [ps][pdf]
Luca Trevisan Error-Correcting Codes and Pseudorandom Projections Invited Talk
Abstract in Proc. of RANDOM-APPROX, pp. 7-9, 2001
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
Luca Trevisan. Interactive and probabilistic proof-checking Survey paper
In Annals of Pure and Applied Logic, 104:325-342, 2000 [Final
version]
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]
Grants and Copyright
Some of these papers were based upon work supported by the National
Science Foundation under Grants No. CCF-0729137, CCF-9984703, CCF-1161812, CCF-1216642 and by the Sloan Foundation.
Any opinions, findings and conclusions or recomendations expressed in
this
material are those of the author(s) and do not necessarily reflect the
views of the National Science Foundation (NSF) or of the Sloan
Foundation.
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.