research
∙
05/25/2023
Smoothed Complexity of SWAP in Local Graph Partitioning
We give the first quasipolynomial upper bound ϕ n^polylog(n) for the smo...
share
research
∙
11/30/2022
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
We show subexponential lower bounds (i.e., 2^Ω (n^c)) on the smoothed co...
research
∙
09/15/2022
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP
We study the complexity of computational problems arising from existence...
research
∙
06/27/2022
Center-Embedding and Constituency in the Brain and a New Characterization of Context-Free Languages
A computational system implemented exclusively through the spiking of ne...
research
∙
09/13/2020
The Platform Design Problem
On-line firms deploy suites of software platforms, where each platform i...
research
∙
05/28/2020
Planar Graphs that Need Four Pages
We show that there are planar graphs that require four pages in any book...
research
∙
04/03/2020
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
In 1979, Hylland and Zeckhauser <cit.> gave a simple and general scheme ...
research
∙
11/23/2019
Smoothed complexity of local Max-Cut and binary Max-CSP
We show that the smoothed complexity of the FLIP algorithm for local Max...
research
∙
09/07/2019
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
The use of monotonicity and Tarski's theorem in existence proofs of equi...
research
∙
06/11/2018
Reachability for Branching Concurrent Stochastic Games
We give polynomial time algorithms for deciding almost-sure and limit-su...
research
∙
06/04/2018
