☰

Luca Trevisan - Publications

Affiliations: 
Electrical Engineering and Computer Science University of California, Berkeley, Berkeley, CA, United States 
Area:
Theory (THY), (Computational Complexity, Randomness in Computation, Combinatorial Optimization); Security (SEC)
Tree Info Similar researchers PubMed Report error

39 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Chalermsook P, Cygan M, Kortsarz G, Laekhanukit B, Manurangsi P, Nanongkai D, Trevisan L. From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More Siam Journal On Computing. 49: 772-810. DOI: 10.1137/18M1166869  0.306
2016 Andersen R, Gharan SO, Peres Y, Trevisan L. Almost Optimal Local Graph Clustering Using Evolving Sets Journal of the Acm. 63: 15. DOI: 10.1145/2856030  0.373
2015 Clementi A, Silvestri R, Trevisan L. Information spreading in dynamic graphs Distributed Computing. 28: 55-73. DOI: 10.1007/S00446-014-0219-2  0.351
2014 Lee JR, Gharan SO, Trevisan L. Multiway spectral partitioning and higher-order cheeger inequalities Journal of the Acm. 61. DOI: 10.1145/2665063  0.356
2014 Trevisan L. Inapproximability of Combinatorial Optimization Problems Paradigms of Combinatorial Optimization: Problems and New Approaches: 2nd Edition. 381-434. DOI: 10.1002/9781118600207.Ch13  0.312
2013 Oveis Gharan S, Trevisan L. A new regularity lemma and faster approximation algorithms for low threshold rank graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8096: 303-316. DOI: 10.1007/978-3-642-40328-6_22  0.35
2012 Trevisan L. Max Cut and the smallest eigenvalue Siam Journal On Computing. 41: 1769-1786. DOI: 10.1137/090773714  0.347
2010 De A, Etesami O, Trevisan L, Tulsiani M. Improved pseudorandom generators for depth 2 circuits Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6302: 504-517. DOI: 10.1007/978-3-642-15369-3_38  0.63
2010 De A, Trevisan L, Tulsiani M. Time space tradeoffs for attacks against one-way functions and PRGs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6223: 649-665. DOI: 10.1007/978-3-642-14623-7_35  0.634
2009 Trevisan L, Tulsiani M, Vadhan S. Regularity, boosting, and efficiently simulating every high-entropy distribution Proceedings of the Annual Ieee Conference On Computational Complexity. 126-136. DOI: 10.1109/CCC.2009.41  0.622
2009 Lovett S, Reingold O, Trevisan L, Vadhan S. Pseudorandom bit generators that fool modular sums Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5687: 615-630. DOI: 10.1007/978-3-642-03685-9_46  0.335
2008 Trevisan L. Average-case complexity Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 11. DOI: 10.1561/0400000004  0.314
2008 Reingold O, Trevisan L, Tulsiani M, Vadhan S. Dense subsets of pseudorandom sets Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 76-85. DOI: 10.1109/FOCS.2008.38  0.644
2007 Schoenebeck G, Trevisan L, Tulsiani M. Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut Proceedings of the Annual Acm Symposium On Theory of Computing. 302-310. DOI: 10.1145/1250790.1250836  0.659
2007 Schoenebeck G, Trevisan L, Tulsiani M. A linear round lower bound for Lovasz-Schrijver SDP relaxations of vertex cover Proceedings of the Annual Ieee Conference On Computational Complexity. 205-216. DOI: 10.1109/CCC.2007.2  0.677
2006 Bogdanov A, Trevisan L. On worst-case to average-case reductions for NP problems Siam Journal On Computing. 36: 1119-1159. DOI: 10.1137/S0097539705446974  0.536
2006 Gennaro R, Gertner Y, Katz J, Trevisan L. Bounds on the efficiency of generic cryptographic constructions Siam Journal On Computing. 35: 217-246. DOI: 10.1137/S0097539704443276  0.31
2006 Mossel E, Shpilka A, Trevisan L. On ε-biased generators in NC0 Random Structures and Algorithms. 29: 56-81. DOI: 10.1002/Rsa.V29:1  0.551
2006 Mossel E, Shpilka A, Trevisan L. On ɛ-biased generators in NC0 Random Structures and Algorithms. 29: 56-81. DOI: 10.1002/Rsa.20112  0.505
2005 Trevisan L. Approximation algorithms for unique games Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 2005: 197-205. DOI: 10.4086/Toc.2008.V004A005  0.321
2005 Chazelle B, Rubinfeld R, Trevisan L. Approximating the minimum spanning tree weight in sublinear time Siam Journal On Computing. 34: 1370-1379. DOI: 10.1137/S0097539702403244  0.315
2005 Schallhart C, Trevisan L. Approximating succinct MaxSat Journal of Logic and Computation. 15: 551-557. DOI: 10.1093/Logcom/Exi033  0.354
2005 Serna M, Trevisan L, Xhafa F. The approximability of non-Boolean satisfiability problems and restricted integer programming Theoretical Computer Science. 332: 123-139. DOI: 10.1016/J.Tcs.2004.10.014  0.339
2004 Trevisan L. On local versus global satisfiability Siam Journal On Discrete Mathematics. 17: 541-547. DOI: 10.1137/S0895480197326528  0.321
2003 Goldreich O, Trevisan L. Three Theorems Regarding Testing Graph Properties Random Structures and Algorithms. 23: 23-57. DOI: 10.1002/Rsa.10078  0.332
2001 Khanna S, Sudan M, Trevisan L, Williamson DP. The Approximability of Constraint Satisfaction Problems Siam Journal On Computing. 30: 1863-1920. DOI: 10.1137/S0097539799349948  0.317
2001 Díaz J, Petit J, Serna M, Trevisan L. Approximating layout problems on random graphs Discrete Mathematics. 235: 245-253. DOI: 10.1016/S0012-365X(00)00278-8  0.326
2001 Crescenzi P, Silvestri R, Trevisan L. On weighted vs unweighted versions of combinatorial optimization problems Information and Computation. 167: 10-26. DOI: 10.1006/Inco.2000.3011  0.336
2000 Trevisan L. When hamming meets euclid: The approximability of geometric TSP and Steiner tree Siam Journal On Computing. 30: 475-485. DOI: 10.1137/S0097539799352735  0.383
2000 Trevisan L, Sorkin GB, Sudan M, Williamson DP. Gadgets, approximation, and linear programming Siam Journal On Computing. 29: 2074-2097. DOI: 10.1137/S0097539797328847  0.354
2000 Boreale M, Trevisan L. A complexity analysis of bisimilarity for value-passing processes Theoretical Computer Science. 238: 313-345. DOI: 10.1016/S0304-3975(98)00177-7  0.303
2000 Trevisan L. Approximating satisfiable satisfiability problems Algorithmica (New York). 28: 145-172. DOI: 10.1007/S004530010035  0.351
2000 Crescenzi P, Trevisan L. On Approximation Scheme Preserving Reducibility and Its Applications Theory of Computing Systems \/ Mathematical Systems Theory. 33: 1-16. DOI: 10.1007/S002249910001  0.343
1999 Andreev AE, Clementi AEF, Rolim JDP, Trevisan L. Weak Random Sources, Hitting Sets, and BPP Simulations Siam Journal On Computing. 28: 2103-2116. DOI: 10.1137/S0097539797325636  0.306
1999 Crescenzi P, Trevisan L. Max NP-completeness made easy Theoretical Computer Science. 225: 65-79. DOI: 10.1016/S0304-3975(98)00200-X  0.322
1998 Rolim JDP, Trevisan L. A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms Journal of Combinatorial Optimization. 2: 219-236. DOI: 10.1023/A:1009793909670  0.33
1998 Trevisan L. Parallel Approximation Algorithms by Positive Linear Programming Algorithmica. 21: 72-88. DOI: 10.1007/Pl00009209  0.323
1997 Cesati M, Trevisan L. On the efficiency of polynomial time approximation schemes Information Processing Letters. 64: 165-171. DOI: 10.1016/S0020-0190(97)00164-6  0.31
1996 Crescenzi P, Trevisan L. On the distributed decision-making complexity of the minimum vertex cover problem Theoretical Informatics and Applications. 30: 431-441. DOI: 10.1051/Ita/1996300504311  0.313
Show low-probability matches.