
Correlation Clustering Reconstruction in SemiAdversarial Models
Correlation Clustering is an important clustering problem with many appl...
read it

Sharp Thresholds for a SIR Model on OneDimensional SmallWorld Networks
We study epidemic spreading according to a SusceptibleInfectiousRecove...
read it

Cut Sparsification of the Clique Beyond the Ramanujan Bound
We prove that a random dregular graph, with high probability, is a cut ...
read it

Expansion and Flooding in Dynamic Random Networks with Node Churn
We study expansion and information diffusion in dynamic networks, that i...
read it

Subexponential LPs Approximate MaxCut
We show that for every ε > 0, the degreen^ε SheraliAdams linear progra...
read it

Vector Colorings of Random, Ramanujan, and LargeGirth Irregular Graphs
We prove that in sparse ErdősRényi graphs of average degree d, the vect...
read it

New Notions and Constructions of Sparsification for Graphs and Hypergraphs
A sparsifier of a graph G (Benczúr and Karger; Spielman and Teng) is a s...
read it

Finding a BoundedDegree Expander Inside a Dense One
It follows from the MarcusSpielmanSrivastava proof of the KadisonSing...
read it

A Ramseytype Theorem on the MaxCut Value of dRegular Graphs
In this paper we study the problem of finding large cuts in K_rfree gra...
read it

A New Algorithm for the Robust Semirandom Independent Set Problem
In this paper, we study a semirandom version of the planted independent...
read it

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems
In this work, we study the tradeoff between the running time of approxi...
read it

Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise
Consensus and Broadcast are two fundamental problems in distributed comp...
read it

Optimal Lower Bounds for Sketching Graph Cuts
We study the space complexity of sketching cuts and Laplacian quadratic ...
read it

From GapETH to FPTInapproximability: Clique, Dominating Set, and More
We consider questions that arise from the intersection between the areas...
read it

Partitioning into Expanders
Let G=(V,E) be an undirected graph, lambda_k be the kth smallest eigenv...
read it

Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=...
read it
Luca Trevisan
is this you? claim profile