research
∙
07/15/2023
A Nearly-Linear Time Algorithm for Structured Support Vector Machines
Quadratic programming is a fundamental problem in the field of convex op...
share
research
∙
04/27/2023
Fast Sampling of b-Matchings and b-Edge Covers
For an integer b ≥ 1, a b-matching (resp. b-edge cover) of a graph G=(V,...
research
∙
03/26/2023
Weak Recovery Threshold for the Hypergraph Stochastic Block Model
We study the problem of weak recovery for the r-uniform hypergraph stoch...
research
∙
03/26/2023
Uniqueness of BP fixed point for the Potts model and applications to community detection
In the study of sparse stochastic block model (SBM) one needs to analyze...
research
∙
02/24/2023
Optimal Bounds for Noisy Sorting
Sorting is a fundamental problem in computer science. In the classical s...
research
∙
02/21/2023
Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
Given a matrix M∈ℝ^m× n, the low rank matrix completion problem asks us ...
research
∙
11/11/2022
A Faster Small Treewidth SDP Solver
Semidefinite programming is a fundamental tool in optimization and theor...
research
∙
05/06/2021
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is...
research
∙
01/29/2021
Stochastic block model entropy and broadcasting on trees with survey
The limit of the entropy in the stochastic block model (SBM) has been ch...
research
∙
05/15/2020
Broadcasting on trees near criticality
We revisit the problem of broadcasting on d-ary trees: starting from a B...
research
∙
05/11/2020
Non-linear Log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
Consider a Markov process with state space [k], which jumps continuously...
research
∙
10/05/2018
A note on spanoid rank
We construct a spanoid S on n elements with rank(S) > n^c f-rank(S) wher...
research
∙
09/19/2018
Zero-error communication over adder MAC
Adder MAC is a simple noiseless multiple-access channel (MAC), where if ...
research
∙
04/18/2018