research
∙
02/16/2023
On the Role of Memory in Robust Opinion Dynamics
We investigate opinion dynamics in a fully-connected system, consisting ...
share
research
∙
07/28/2022
On the Multidimensional Random Subset Sum Problem
In the Random Subset Sum Problem, given n i.i.d. random variables X_1, ....
research
∙
05/18/2022
Bond Percolation in Small-World Graphs with Power-Law Distribution
Full-bond percolation with parameter p is the process in which, given a ...
research
∙
04/20/2022
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
We define a notion of "non-backtracking" matrix associated to any symmet...
research
∙
08/10/2021
Correlation Clustering Reconstruction in Semi-Adversarial Models
Correlation Clustering is an important clustering problem with many appl...
research
∙
03/30/2021
Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks
We study epidemic spreading according to a Susceptible-Infectious-Recove...
research
∙
08/13/2020
Cut Sparsification of the Clique Beyond the Ramanujan Bound
We prove that a random d-regular graph, with high probability, is a cut ...
research
∙
07/29/2020
Expansion and Flooding in Dynamic Random Networks with Node Churn
We study expansion and information diffusion in dynamic networks, that i...
research
∙
11/23/2019
Subexponential LPs Approximate Max-Cut
We show that for every ε > 0, the degree-n^ε Sherali-Adams linear progra...
research
∙
07/04/2019
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
We prove that in sparse Erdős-Rényi graphs of average degree d, the vect...
research
∙
05/04/2019
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...
research
∙
11/26/2018
Finding a Bounded-Degree Expander Inside a Dense One
It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Sing...
research
∙
10/23/2018
A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs
In this paper we study the problem of finding large cuts in K_r-free gra...
research
∙
08/10/2018
A New Algorithm for the Robust Semi-random Independent Set Problem
In this paper, we study a semi-random version of the planted independent...
research
∙
07/25/2018
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems
In this work, we study the trade-off between the running time of approxi...
research
∙
07/15/2018
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...
research
∙
12/29/2017
Optimal Lower Bounds for Sketching Graph Cuts
We study the space complexity of sketching cuts and Laplacian quadratic ...
research
∙
08/14/2017
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
We consider questions that arise from the intersection between the areas...
research
∙
09/12/2013
Partitioning into Expanders
Let G=(V,E) be an undirected graph, lambda_k be the k-th smallest eigenv...
research
∙
01/23/2013