research
∙
05/05/2023
On Optimization and Counting of Non-Broken Bases of Matroids
Given a matroid M=(E, I), and a total ordering over the elements E, a br...
share
research
∙
03/07/2023
Complete Log Concavity of Coverage-Like Functions
We introduce an expressive subclass of non-negative almost submodular se...
research
∙
12/13/2022
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
We show that the max entropy algorithm can be derandomized (with respect...
research
∙
08/09/2022
An Improved Trickle-Down Theorem for Partite Complexes
Given a d+1-partite d-dimensional simplicial complex, we prove a general...
research
∙
11/24/2021
Matroid Partition Property and the Secretary Problem
A matroid ℳ on a set E of elements has the α-partition property, for som...
research
∙
06/07/2021
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
We show that the natural Glauber dynamics mixes rapidly and generates a ...
research
∙
05/20/2021
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
We show that for some ϵ > 10^-36 and any metric TSP instance, the max en...
research
∙
03/15/2021
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
We show that the ratio of the number of near perfect matchings to the nu...
research
∙
01/15/2021
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem
We give a randomized 1+√(8ln k/k)-approximation algorithm for the minimu...
research
∙
07/02/2020
A (Slightly) Improved Approximation Algorithm for Metric TSP
For some ϵ > 10^-36 we give a 3/2-ϵ approximation algorithm for metric T...
research
∙
04/15/2020
Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees
We prove tight mixing time bounds for natural random walks on bases of m...
research
∙
01/02/2020
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
We say a probability distribution μ is spectrally independent if an asso...
research
∙
08/01/2019
An Improved Approximation Algorithm for TSP in the Half Integral Case
We design a 1.49993-approximation algorithm for the metric traveling sal...
research
∙
07/06/2019
Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
"Composable core-sets" are an efficient framework for solving optimizati...
research
∙
11/05/2018
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
We use recent developments in the area of high dimensional expanders and...
research
∙
11/05/2018
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids
We give a self-contained proof of the strongest version of Mason's conje...
research
∙
10/20/2018
A Polynomial Time MCMC Method for Sampling from Continuous DPPs
We study the Gibbs sampling algorithm for continuous determinantal point...
research
∙
07/31/2018
Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
We study a spectral generalization of classical combinatorial graph span...
research
∙
07/02/2018
Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids
We give a deterministic polynomial time 2^O(r)-approximation algorithm f...
research
∙
06/18/2018
On the Bias of Reed-Muller Codes over Odd Prime Fields
We study the bias of random bounded-degree polynomials over odd prime fi...
research
∙
11/17/2017
Graph Clustering using Effective Resistance
#1#1 We design a polynomial time algorithm that for any weighted undire...
research
∙
11/03/2017
A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Stable matching is a classical combinatorial problem that has been the s...
research
∙
08/08/2017
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
We develop an extension of recently developed methods for obtaining time...
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