Luca Trevisan

Orcid: 0000-0002-6982-8530

Affiliations:
  • University of California, Berkeley, USA


According to our database1, Luca Trevisan authored at least 177 papers between 1994 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2021, "For contributions to complexity theory and combinatorial optimization".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
A Mixed Approach for Clock Synchronization in Distributed Data Acquisition Systems.
Sensors, September, 2024

A Versatile Board for Event-Driven Data Acquisition.
Sensors, March, 2024

Bond percolation in small-world graphs with power-law distribution.
Theor. Comput. Sci., 2024

New SDP Roundings and Certifiable Approximation for Cubic Optimization.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

The Minority Dynamics and the Power of Synchronicity.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023
Expansion and flooding in dynamic random networks with node churn.
Random Struct. Algorithms, August, 2023

On the Role of Memory in Robust Opinion Dynamics.
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs.
Proceedings of the 38th Computational Complexity Conference, 2023

2022
Near-Optimal NP-Hardness of Approximating Max k-CSP<sub>R</sub>.
Theory Comput., 2022

An IoT Measurement System Based on LoRaWAN for Additive Manufacturing.
Sensors, 2022

On the Multidimensional Random Subset Sum Problem.
CoRR, 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
Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming.
SIAM J. Discret. Math., 2021

Introducing The Theory Blogs Column.
Bull. EATCS, 2021

Correlation Clustering Reconstruction in Semi-Adversarial Models.
CoRR, 2021

Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks.
CoRR, 2021

2020
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.
SIAM J. Comput., 2020

Find Your Place: Simple Distributed Algorithms for Community Detection.
SIAM J. Comput., 2020

Cut Sparsification of the Clique Beyond the Ramanujan Bound.
CoRR, 2020

A New Algorithm for the Robust Semi-random Independent Set Problem.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Finding a Bounded-Degree Expander Inside a Dense One.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Lower Bounds for Max-Cut via Semidefinite Programming.
Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Consensus vs Broadcast, with and Without Noise (Extended Abstract).
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

Subexponential LPs Approximate Max-Cut.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

An IIoT System to Monitor 3D-Printed Artifacts via LoRaWAN Embedded Sensors.
Proceedings of the 25th IEEE International Conference on Emerging Technologies and Factory Automation, 2020

2019
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs.
CoRR, 2019

Optimal Lower Bounds for Sketching Graph Cuts.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs.
CoRR, 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

Average Whenever You Meet: Opportunistic Protocols for Community Detection.
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
Simple dynamics for plurality consensus.
Distributed Comput., 2017

Friend or Foe? Population Protocols can perform Community Detection.
CoRR, 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

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Learning Heavy Fourier Coefficients of Boolean Functions.
Encyclopedia of Algorithms, 2016

Almost Optimal Local Graph Clustering Using Evolving Sets.
J. ACM, 2016

Approximation of non-boolean 2CSP.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Stabilizing Consensus with Many Opinions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Near-Optimal UGC-hardness of Approximating Max k-CSP_R.
Proceedings of the Approximation, 2016

2015
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.
Theory Comput., 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.
Electron. Colloquium Comput. Complex., 2015

Information spreading in dynamic graphs.
Distributed Comput., 2015

Unique Games on the Hypercube.
Chic. J. Theor. Comput. Sci., 2015

2014
Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).
SIAM J. Comput., 2014

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities.
J. ACM, 2014

Quantum lower bound for inverting a permutation with advice.
Electron. Colloquium Comput. Complex., 2014

Partitioning into Expanders.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank
CoRR, 2013

Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
CoRR, 2013

Simple Dynamics for Majority Consensus.
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

A Derandomized Switching Lemma and an Improved Derandomization of AC0.
Proceedings of the 28th Conference on Computational Complexity, 2013

2012
Max Cut and the Smallest Eigenvalue.
SIAM J. Comput., 2012

A Derandomized Switching Lemma and an Improved Derandomization of AC0.
Electron. Colloquium Comput. Complex., 2012

Better pseudorandom generators from milder pseudorandom restrictions.
Electron. Colloquium Comput. Complex., 2012

On the One-Way Function Candidate Proposed by Goldreich.
Electron. Colloquium Comput. Complex., 2012

Pseudorandomness and derandomization.
XRDS, 2012

A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
CoRR, 2012

Multi-way spectral partitioning and higher-order cheeger inequalities.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Dense Model Theorems and Their Applications.
Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

From Logarithmic Advice to Single-Bit Advice.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
The Program-Enumeration Bottleneck in Average-Case Complexity Theory.
Electron. Colloquium Comput. Complex., 2010

Time Space Tradeoffs for Attacks against One-Way Functions and PRGs.
Proceedings of the Advances in Cryptology, 2010

2009
Guest column: additive combinatorics and theoretical computer science.
SIGACT News, 2009

Gowers Uniformity, Influence of Variables, and PCPs.
SIAM J. Comput., 2009

Non-uniform attacks against one-way functions and PRGs.
Electron. Colloquium Comput. Complex., 2009

Improved Pseudorandom Generators for Depth 2 Circuits.
Electron. Colloquium Comput. Complex., 2009

Foreword.
Algorithmica, 2009

Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

Pseudorandom Bit Generators That Fool Modular Sums.
Proceedings of the Approximation, 2009

Extractors Using Hardness Amplification.
Proceedings of the Approximation, 2009

2008
Learning Heavy Fourier Coefficients of Boolean Functions.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Electron. Colloquium Comput. Complex., 2008

Dense Subsets of Pseudorandom Sets.
Electron. Colloquium Comput. Complex., 2008

Average-case Complexity.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Pseudorandomness and Average-Case Complexity Via Uniform Reductions.
Comput. Complex., 2007

Fun with Sub-linear Time Algorithms.
Proceedings of the Fun with Algorithms, 4th International Conference, 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
Proceedings of the Advances in Cryptology, 2007

2006
On Worst-Case to Average-Case Reductions for NP Problems.
SIAM J. Comput., 2006

On epsilon-biased generators in NC<sup>0</sup>.
Random Struct. Algorithms, 2006

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.
Electron. Colloquium Comput. Complex., 2006

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
Electron. Colloquium Comput. Complex., 2006

Pseudorandomness and Combinatorial Constructions
Electron. Colloquium Comput. Complex., 2006

Average-Case Complexity.
Electron. Colloquium Comput. Complex., 2006

Lower bounds for linear locally decodable codes and private information retrieval.
Comput. Complex., 2006

Pseudorandom walks on regular digraphs and the RL vs. L problem.
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

Bounds on the Efficiency of Generic Cryptographic Constructions.
SIAM J. Comput., 2005

Approximating the Minimum Spanning Tree Weight in Sublinear Time.
SIAM J. Comput., 2005

Approximating Succinct MaxSat.
J. Log. Comput., 2005

Approximation Algorithms for Unique Games
Electron. Colloquium Comput. Complex., 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Electron. Colloquium Comput. Complex., 2005

Compression of Samplable Sources.
Comput. Complex., 2005

On Hardness Amplification of One-Way Functions.
Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

On uniform amplification of hardness in NP.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Hierarchies for semantic classes.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

The Complexity of Making Unique Choices: Approximating 1-in- k SAT.
Proceedings of the Approximation, 2005

2004
Promise Hierarchies
Electron. Colloquium Comput. Complex., 2004

From logarithmic advice to single-bit advice
Electron. Colloquium Comput. Complex., 2004

Inapproximability of Combinatorial Optimization Problems
Electron. Colloquium Comput. Complex., 2004

Some Applications of Coding Theory in Computational Complexity
Electron. Colloquium Comput. Complex., 2004

Notions of Reducibility between Cryptographic Primitives.
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

A Note on Approximate Counting for k-DNF.
Proceedings of the Approximation, 2004

Pseudorandomness - Part II.
Proceedings of the Computational Complexity Theory., 2004

2003
On epsilon-Biased Generators in NC0
Electron. Colloquium Comput. Complex., 2003

List Decoding Using the XOR Lemma
Electron. Colloquium Comput. Complex., 2003

An epsilon-Biased Generator in NC0
Electron. Colloquium Comput. Complex., 2003

On e-Biased Generators in NC0.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Error-Correcting Codes in Complexity Theory.
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002
A Note on Deterministic Approximate Counting for k-DNF
Electron. Colloquium Comput. Complex., 2002

Lower Bounds for Testing Bipartiteness in Dense Graphs
Electron. Colloquium Comput. Complex., 2002

Counting Distinct Elements in a Data Stream.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Streaming Computation of Combinatorial Objects.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Pseudorandom Generators without the XOR Lemma.
J. Comput. Syst. Sci., 2001

Extractors and pseudorandom generators.
J. ACM, 2001

On Weighted vs Unweighted Versions of Combinatorial Optimization Problems.
Inf. Comput., 2001

Three Theorems regarding Testing Graph Properties.
Electron. Colloquium Comput. Complex., 2001

Approximating layout problems on random graphs.
Discret. Math., 2001

Non-approximability results for optimization problems on bounded degree instances.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Error-Correcting Codes and Pseudorandom Projections.
Proceedings of the Approximation, 2001

2000
A complexity analysis of bisimilarity for value-passing processes.
Theor. Comput. Sci., 2000

Gadgets, Approximation, and Linear Programming.
SIAM J. Comput., 2000

When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree.
SIAM J. Comput., 2000

The Approximability of Constraint Satisfaction Problems.
SIAM J. Comput., 2000

On Approximation Scheme Preserving Reducibility and Its Applications.
Theory Comput. Syst., 2000

Lower Bounds on the Efficiency of Generic Cryptographic Constructions
Electron. Colloquium Comput. Complex., 2000

Interactive and probabilistic proof-checking.
Ann. Pure Appl. Log., 2000

Approximating Satisfiable Satisfiability Problems.
Algorithmica, 2000

Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming".
Algorithmica, 2000

A PCP characterization of NP with optimal amortized query complexity.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On the efficiency of local decoding procedures for error-correcting codes.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Extracting Randomness from Samplable Distributions.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

A Survey of Optimal PCP Characterizations of NP.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
Max NP-completeness Made Easy.
Theor. Comput. Sci., 1999

Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.
Theor. Comput. Sci., 1999

Structure in Approximation Classes.
SIAM J. Comput., 1999

Weak Random Sources, Hitting Sets, and BPP Simulations.
SIAM J. Comput., 1999

Construction of Extractors Using Pseudo-Random Generators (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
The Parallel Complexity of Positive Linear Programming.
Parallel Process. Lett., 1998

A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms.
J. Comb. Optim., 1998

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators
Electron. Colloquium Comput. Complex., 1998

Probabilistically checkable proofs with low amortized query complexity
Electron. Colloquium Comput. Complex., 1998

A tight characterization of NP with 3 query PCPs
Electron. Colloquium Comput. Complex., 1998

Recycling Queries in PCPs and in Linearity Tests
Electron. Colloquium Comput. Complex., 1998

Recent Advances Towards Proving P = BPP.
Bull. EATCS, 1998

Parallel Approximation Algorithms by Positive Linear Programming.
Algorithmica, 1998

Recycling Queries in PCPs and in Linearity Tests (Extended Abstract).
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
On the Efficiency of Polynomial Time Approximation Schemes.
Inf. Process. Lett., 1997

On Local versus Global Satisfiability
Electron. Colloquium Comput. Complex., 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

Approximating Satisfiable Satisfiability Problems (Extended Abstract).
Proceedings of the Algorithms, 1997

1996
On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem.
RAIRO Theor. Informatics Appl., 1996

A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees.
Inf. Process. Lett., 1996

Constraint satisfaction: The approximability of minimization problems.
Electron. Colloquium Comput. Complex., 1996

On the Approximability of the Multi-dimensional Euclidean TSP
Electron. Colloquium Comput. Complex., 1996

Bisimilarity Problems Requiring Exponential Time.
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

Gadgets, Approximation, and Linear Programming (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Positive Linear Programming, Parallel Approximation and PCP's.
Proceedings of the Algorithms, 1996

Improved Non-approximability Results for Vertex Cover with Density Constraints.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995
On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract).
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Structure in Approximation Classes (Extended Abstract).
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

On Approximation Scheme Preserving Reducability and Its Applications.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994


  Loading...