31 citations · 69 across the 12 of their papers we have counts for
15 papers
A Better-Than- Approximation Algorithm for Demand Matching via Knapsack Intersection LP and Contention Resolution
Michel X. Goemans, Yuchong Pan
The demand matching problem generalizes both the knapsack problem and the -matching problem. In this problem, each edge of a graph has a demand and a weight, and each vertex has…
Bicriteria Approximation Algorithms for Demand Matching
Yuchong Pan, Michel X. Goemans
The demand matching problem generalizes both the knapsack problem and the -matching problem. In this problem, each edge of a graph has a demand and a weight, each vertex has a c…
Shrunk subspaces via operator Sinkhorn iteration
Cole Franks, Tasuku Soma, Michel X. Goemans
A recent breakthrough in Edmonds' problem showed that the noncommutative rank can be computed in deterministic polynomial time, and various algorithms for it were devised. However,…
Doubly-Efficient Pseudo-Deterministic Proofs
Michel Goemans, Shafi Goldwasser, Dhiraj Holden
In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time…
Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans
We study the problem of community detection in a random hypergraph model which we call the stochastic block model for -uniform hypergraphs (-SBM). We investigate the exact re…
Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares
Chiheon Kim, Afonso S. Bandeira, Michel X. Goemans
We study the problem of community detection in hypergraphs under a stochastic block model. Similarly to how the stochastic block model in graphs suggests studying spiked random mat…