Luca Trevisan
Orcid: 0000-0002-6982-8530Affiliations:
- University of California, Berkeley, USA
According to our database1,
Luca Trevisan
authored at least 177 papers
between 1994 and 2024.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2021, "For contributions to complexity theory and combinatorial optimization".
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on zbmath.org
-
on twitter.com
-
on orcid.org
-
on id.loc.gov
-
on github.com
-
on d-nb.info
On csauthors.net:
Bibliography
2024
Sensors, September, 2024
Theor. Comput. Sci., 2024
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
2023
Random Struct. Algorithms, August, 2023
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023
Proceedings of the 38th Computational Complexity Conference, 2023
2022
Theory Comput., 2022
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022
Percolation and Epidemic Processes in One-Dimensional Small-World Networks - (Extended Abstract).
Proceedings of the LATIN 2022: Theoretical Informatics, 2022
Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models.
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022
2021
SIAM J. Discret. Math., 2021
2020
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.
SIAM J. Comput., 2020
SIAM J. Comput., 2020
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Proceedings of the LATIN 2020: Theoretical Informatics, 2020
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020
Evaluation of LoRaWAN for Sensor Data Collection in an IIoT-based Additive Manufacturing Project.
Proceedings of the 2020 IEEE International Instrumentation and Measurement Technology Conference, 2020
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020
Proceedings of the 25th IEEE International Conference on Emerging Technologies and Factory Automation, 2020
2019
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019
2018
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems.
CoRR, 2018
Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise.
CoRR, 2018
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Proceedings of the 26th Annual European Symposium on Algorithms, 2018
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut.
Proceedings of the Approximation, 2018
2017
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
2016
Encyclopedia of Algorithms, 2016
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Proceedings of the Approximation, 2016
2015
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.
Theory Comput., 2015
Electron. Colloquium Comput. Complex., 2015
2014
Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).
SIAM J. Comput., 2014
Electron. Colloquium Comput. Complex., 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
2013
CoRR, 2013
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Proceedings of the 28th Conference on Computational Complexity, 2013
2012
Electron. Colloquium Comput. Complex., 2012
Electron. Colloquium Comput. Complex., 2012
Electron. Colloquium Comput. Complex., 2012
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012
2011
Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
2010
Electron. Colloquium Comput. Complex., 2010
Proceedings of the Advances in Cryptology, 2010
2009
SIGACT News, 2009
Electron. Colloquium Comput. Complex., 2009
Electron. Colloquium Comput. Complex., 2009
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009
Proceedings of the Approximation, 2009
2008
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008
Electron. Colloquium Comput. Complex., 2008
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
Comput. Complex., 2007
Proceedings of the Fun with Algorithms, 4th International Conference, 2007
Proceedings of the Advances in Cryptology, 2007
2006
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.
Electron. Colloquium Comput. Complex., 2006
Electron. Colloquium Comput. Complex., 2006
Electron. Colloquium Comput. Complex., 2006
Comput. Complex., 2006
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
2005
The approximability of non-Boolean satisfiability problems and restricted integer programming.
Theor. Comput. Sci., 2005
SIAM J. Comput., 2005
SIAM J. Comput., 2005
Electron. Colloquium Comput. Complex., 2005
Electron. Colloquium Comput. Complex., 2005
Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
Proceedings of the Approximation, 2005
2004
Electron. Colloquium Comput. Complex., 2004
Electron. Colloquium Comput. Complex., 2004
Electron. Colloquium Comput. Complex., 2004
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004
List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004
Proceedings of the Computational Complexity Theory., 2004
2003
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003
2002
Electron. Colloquium Comput. Complex., 2002
Electron. Colloquium Comput. Complex., 2002
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002
2001
Inf. Comput., 2001
Electron. Colloquium Comput. Complex., 2001
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Proceedings of the Approximation, 2001
2000
Theor. Comput. Sci., 2000
SIAM J. Comput., 2000
Theory Comput. Syst., 2000
Electron. Colloquium Comput. Complex., 2000
Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming".
Algorithmica, 2000
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000
1999
Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.
Theor. Comput. Sci., 1999
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999
1998
Parallel Process. Lett., 1998
J. Comb. Optim., 1998
Electron. Colloquium Comput. Complex., 1998
Electron. Colloquium Comput. Complex., 1998
Electron. Colloquium Comput. Complex., 1998
Electron. Colloquium Comput. Complex., 1998
Recent Advances Towards Proving P = BPP.
Bull. EATCS, 1998
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming.
Proceedings of the STACS 98, 1998
1997
Inf. Process. Lett., 1997
When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
Proceedings of the Algorithms, 1997
1996
RAIRO Theor. Informatics Appl., 1996
Inf. Process. Lett., 1996
Electron. Colloquium Comput. Complex., 1996
Electron. Colloquium Comput. Complex., 1996
Proceedings of the Mathematical Foundations of Computer Science 1996, 1996
To Weight or Not to Weight: Where is the Question?
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
Proceedings of the Algorithms, 1996
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996
1995
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995
1994
Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994