Publications (34)
Find Your Place: Simple Distributed Algorithms for Community Detection
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
Unique Games on the Hypercube
Naman Agarwal, Guy Kindler, Alexandra Kolla +1
A Higher-Order Cheeger's Inequality
Shayan Oveis Gharan, Luca Trevisan
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
Max Cut and the Smallest Eigenvalue
Luca Trevisan
Gowers Uniformity, Influence of Variables, and PCPs
Alex Samorodnitsky, Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
Shayan Oveis Gharan, Luca Trevisan
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
Shayan Oveis Gharan, Luca Trevisan
Partitioning into Expanders
Shayan Oveis Gharan, Luca Trevisan
New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition
Omer Reingold, Luca Trevisan, Madhur Tulsiani +1
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems
Pasin Manurangsi, Luca Trevisan
Near-Optimal UGC-hardness of Approximating Max k-CSP_R
Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
Luca Trevisan
Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise
Andrea Clementi, Luciano GualÃ, Emanuele Natale +3
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee +2
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
Shayan Oveis Gharan, Luca Trevisan
Optimal Lower Bounds for Sketching Graph Cuts
Charles Carlson, Alexandra Kolla, Nikhil Srivastava +1
Approximation of non-boolean 2CSP
Guy Kindler, Alexandra Kolla, Luca Trevisan
Information Spreading in Dynamic Graphs
Andrea Clementi, Riccardo Silvestri, Luca Trevisan
Multi-way spectral partitioning and higher-order Cheeger inequalities
James R. Lee, Shayan Oveis Gharan, Luca Trevisan
Some Applications of Coding Theory in Computational Complexity
Luca Trevisan
Pseudorandomness and Combinatorial Constructions
Luca Trevisan
Quantum lower bound for inverting a permutation with advice
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs +1
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank
Shayan Oveis Gharan, Luca Trevisan
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan, Raghu Meka, Omer Reingold +2
Inapproximability of Combinatorial Optimization Problems
Luca Trevisan
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Nikhil Bansal, Ola Svensson, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz +4
Stabilizing Consensus with Many Opinions
Luca Becchetti, Andrea Clementi, Emanuele Natale +2
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
Nikhil Srivastava, Luca Trevisan
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
Jess Banks, Luca Trevisan
Average whenever you meet: Opportunistic protocols for community detection
Luca Becchetti, Andrea Clementi, Pasin Manurangsi +4
Simple Dynamics for Plurality Consensus
Luca Becchetti, Andrea Clementi, Emanuele Natale +3