| Publication | Date of Publication | Type |
|---|
| Beyond worst-case budget-feasible mechanism design | 2024-09-25 | Paper |
| Maximizing non-monotone submodular functions over small subsets: beyond \(1/2\)-approximation | 2024-06-24 | Paper |
| Beating greedy matching in sublinear time | 2024-05-14 | Paper |
| Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window) | 2024-05-14 | Paper |
| Sublinear time algorithms and complexity of approximate maximum matching | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7829345 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
SIAM Journal on Computing | 2023-12-19 | Paper |
Settling the complexity of Nash equilibrium in congestion games
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
The randomized communication complexity of randomized auctions
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Exponential communication separations between notions of selfishness
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
The Limitations of Optimization from Samples
Journal of the ACM | 2023-04-27 | Paper |
scientific article; zbMATH DE number 7650366 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
scientific article; zbMATH DE number 7650408 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
Operations Research | 2022-12-01 | Paper |
Communication complexity of approximate Nash equilibria
Games and Economic Behavior | 2022-07-15 | Paper |
On the complexity of dynamic mechanism design
Games and Economic Behavior | 2022-07-15 | Paper |
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
SIAM Journal on Computing | 2022-01-07 | Paper |
Computing exact minimum cuts without knowing the graph
(available as arXiv preprint) | 2021-06-15 | Paper |
| Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds | 2021-06-15 | Paper |
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Does preprocessing help in fast sequence comparisons?
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Constant-factor approximation of near-linear edit distance in near-linear time
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Honest signaling in zero-sum games is hard, and lying is even harder
(available as arXiv preprint) | 2020-05-27 | Paper |
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Hardness of approximate nearest neighbor search
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Sorting from Noisier Samples
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Combinatorial prophet inequalities
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
ETH hardness for densest-\(k\)-subgraph with perfect completeness
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
On the complexity of dynamic mechanism design
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Inapproximability of Nash equilibrium
SIAM Journal on Computing | 2018-07-04 | Paper |
Detecting communities is hard (and counting them is even harder)
(available as arXiv preprint) | 2018-05-03 | Paper |
The hunting of the SNARK
Journal of Cryptology | 2018-02-15 | Paper |
Robust probabilistic inference
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Beyond matroids: secretary problem and prophet inequality with general constraints
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
The limitations of optimization from samples
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Communication complexity of approximate Nash equilibria
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
On the computational complexity of optimal simple mechanisms
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Can almost everybody be almost happy?
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
| Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input | 2015-12-30 | Paper |
Inapproximability of Nash equilibrium
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
On Simplex Pivoting Rules and Complexity Theory
Integer Programming and Combinatorial Optimization | 2014-06-02 | Paper |
Converting online algorithms to local computation algorithms
Automata, Languages, and Programming | 2013-08-12 | Paper |
Determining Sets for the Discrete Laplacian
SIAM Review | 2007-06-26 | Paper |
