# Luca Trevisan

According to our database1, Luca Trevisan authored at least 155 papers between 1994 and 2020.

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

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

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

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

2019
Subexponential LPs Approximate Max-Cut.
CoRR, 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

Find Your Place: Simple Distributed Algorithms for Community Detection.
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

Quantum lower bound for inverting a permutation with advice.
Quantum Inf. Comput., 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.
Electronic Colloquium on Computational Complexity (ECCC), 2015

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

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, CCC 2013, K.lo Alto, 2013

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

A Derandomized Switching Lemma and an Improved Derandomization of AC0.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Better pseudorandom generators from milder pseudorandom restrictions.
Electronic Colloquium on Computational Complexity (ECCC), 2012

On the One-Way Function Candidate Proposed by Goldreich.
Electronic Colloquium on Computational Complexity (ECCC), 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

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.
Electronic Colloquium on Computational Complexity (ECCC), 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

Non-uniform attacks against one-way functions and PRGs.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Improved Pseudorandom Generators for Depth 2 Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 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

Approximation Algorithms for Unique Games.
Theory Comput., 2008

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Dense Subsets of Pseudorandom Sets.
Electronic Colloquium on Computational Complexity (ECCC), 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 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.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Pseudorandomness and Combinatorial Constructions
Electronic Colloquium on Computational Complexity (ECCC), 2006

Average-Case Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 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

Gowers Uniformity, Influence of Variables, and PCPs
Electronic Colloquium on Computational Complexity (ECCC), 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Electronic Colloquium on Computational Complexity (ECCC), 2005

On Worst-Case to Average-Case Reductions for NP Problems
Electronic Colloquium on Computational Complexity (ECCC), 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
On Local Versus Global Satisfiability.
SIAM J. Discret. Math., 2004

Promise Hierarchies
Electronic Colloquium on Computational Complexity (ECCC), 2004

Electronic Colloquium on Computational Complexity (ECCC), 2004

Inapproximability of Combinatorial Optimization Problems
Electronic Colloquium on Computational Complexity (ECCC), 2004

Some Applications of Coding Theory in Computational Complexity
Electronic Colloquium on Computational Complexity (ECCC), 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
Electronic Colloquium on Computational Complexity (ECCC), 2003

List Decoding Using the XOR Lemma
Electronic Colloquium on Computational Complexity (ECCC), 2003

An epsilon-Biased Generator in NC0
Electronic Colloquium on Computational Complexity (ECCC), 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
Electronic Colloquium on Computational Complexity (ECCC), 2002

Lower Bounds for Testing Bipartiteness in Dense Graphs
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 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

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
Electronic Colloquium on Computational Complexity (ECCC), 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
Theor. Comput. Sci., 1999

Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.
Theor. Comput. Sci., 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
Electronic Colloquium on Computational Complexity (ECCC), 1998

Probabilistically checkable proofs with low amortized query complexity
Electronic Colloquium on Computational Complexity (ECCC), 1998

A tight characterization of NP with 3 query PCPs
Electronic Colloquium on Computational Complexity (ECCC), 1998

Recycling Queries in PCPs and in Linearity Tests
Electronic Colloquium on Computational Complexity (ECCC), 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

Weak Random Sources, Hitting Sets, and BPP Simulations
Electronic Colloquium on Computational Complexity (ECCC), 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

Structure in Approximation Classes
Electronic Colloquium on Computational Complexity (ECCC), 1996

Constraint satisfaction: The approximability of minimization problems.
Electronic Colloquium on Computational Complexity (ECCC), 1996

On the Approximability of the Multi-dimensional Euclidean TSP
Electronic Colloquium on Computational Complexity (ECCC), 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