| Publication | Date of Publication | Type |
|---|
A note on approximability of densest at-least-k-subgraph
Theoretical Computer Science | 2026-09-29 | Paper |
Asymptotic fair division: chores are easier than goods
SIAM Journal on Discrete Mathematics | 2026-07-20 | Paper |
| On equivalence of parameterized inapproximability of \(k\)-median, \(k\)-max-coverage, and 2-CSP | 2026-05-29 | Paper |
| Algorithmic persuasion with evidence | 2026-04-15 | Paper |
| The strongish planted clique hypothesis and its consequences | 2026-04-15 | Paper |
| Tight hardness results for training depth-2 ReLU networks | 2026-04-15 | Paper |
| On distributed differential privacy and counting distinct elements | 2026-04-15 | Paper |
| Pure-DP aggregation in the shuffle model: error-optimal and communication-efficient | 2026-02-03 | Paper |
| Hardness of approximating bounded-degree max 2-CSP and independent set on k-claw-free graphs | 2025-11-04 | Paper |
Asymptotic analysis of weighted fair division
Theoretical Computer Science | 2025-10-17 | Paper |
On equivalence of parameterized inapproximability of k-median, k-max-coverage, and 2-CSP
Algorithmica | 2025-10-10 | Paper |
Complexity of round-robin allocation with potentially noisy queries
Information and Computation | 2025-09-09 | Paper |
Differentially private fair division
Artificial Intelligence | 2025-09-05 | Paper |
| Towards separating computational and statistical differential privacy | 2025-08-15 | Paper |
| From gap-ETH to FPT-inapproximability: clique, dominating set, and more | 2025-08-06 | Paper |
Ordinal maximin guarantees for group fair division
Theoretical Computer Science | 2025-03-31 | Paper |
| Near-tight closure bounds for the Littlestone and threshold dimensions | 2025-02-11 | Paper |
| Complexity of round-robin allocation with potentially noisy queries | 2025-01-31 | Paper |
Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
Theoretical Computer Science | 2025-01-16 | Paper |
| Differentially private aggregation via imperfect shuffling | 2024-11-22 | Paper |
| On differentially private counting on trees | 2024-11-14 | Paper |
| Algorithms with more granular differential privacy guarantees | 2024-09-25 | Paper |
| Private counting of distinct and \(k\)-occurring items in time windows | 2024-09-25 | Paper |
| Improved inapproximability of VC dimension and Littlestone's dimension via (unbalanced) biclique | 2024-09-25 | Paper |
Improved lower bound for differentially private facility location
Information Processing Letters | 2024-09-11 | Paper |
| A note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation | 2024-08-26 | Paper |
Erratum to: ``Multitasking capacity: hardness results and improved constructions''
SIAM Journal on Discrete Mathematics | 2024-07-16 | Paper |
| Improved approximation algorithms and lower bounds for search-diversification problems | 2024-06-24 | Paper |
| Differentially private all-pairs shortest path distances: improved algorithms and lower bounds | 2024-05-14 | Paper |
| Tight bounds for differentially private anonymized histograms | 2024-05-14 | Paper |
| On the fine-grained complexity of approximating \(k\)-center in sparse graphs | 2024-05-14 | Paper |
Fixing knockout tournaments with seeds
Discrete Applied Mathematics | 2023-12-11 | Paper |
Sample-efficient proper PAC learning with approximate differential privacy
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Pure differentially private summation from anonymous messages
(available as arXiv preprint) | 2023-11-02 | Paper |
A note on hardness of computing recursive teaching dimension
Information Processing Letters | 2023-10-12 | Paper |
Justifying groups in multiwinner approval voting
Theoretical Computer Science | 2023-08-01 | Paper |
Justifying groups in multiwinner approval voting
Algorithmic Game Theory | 2023-07-28 | Paper |
On maximum bipartite matching with separation
Information Processing Letters | 2023-06-05 | Paper |
| Consensus halving for sets of items | 2023-03-21 | Paper |
Consensus Halving for Sets of Items
Mathematics of Operations Research | 2023-01-09 | Paper |
Parameterized Intractability of Even Set and Shortest Vector Problem
Journal of the ACM | 2022-12-08 | Paper |
| Nearly optimal robust secret sharing against rushing adversaries | 2022-12-07 | Paper |
| Tight inapproximability of minimum maximal matching on bipartite graphs and related problems | 2022-10-19 | Paper |
Almost envy-freeness for groups: improved bounds via discrepancy theory
Theoretical Computer Science | 2022-08-25 | Paper |
| On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic | 2022-07-18 | Paper |
Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
Theory of Computing | 2022-05-18 | Paper |
Private aggregation from fewer anonymous messages
(available as arXiv preprint) | 2022-03-23 | Paper |
To close is easier than to open: dual parameterization to \(k\)-median
(available as arXiv preprint) | 2022-03-22 | Paper |
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
ACM Transactions on Algorithms | 2022-02-16 | Paper |
On the complexity of fair house allocation
Operations Research Letters | 2021-12-13 | Paper |
Approximation and hardness of shift-bribery
Artificial Intelligence | 2021-11-02 | Paper |
Linear discrepancy is _2-hard to approximate
Information Processing Letters | 2021-10-19 | Paper |
The price of fairness for indivisible goods
Theory of Computing Systems | 2021-09-28 | Paper |
Sherali-Adams integrality gaps matching the log-density threshold
(available as arXiv preprint) | 2021-08-04 | Paper |
| Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut | 2021-08-04 | Paper |
Average whenever you meet: opportunistic protocols for community detection
(available as arXiv preprint) | 2021-08-04 | Paper |
Parameterized approximation algorithms for bidirected Steiner network problems
(available as arXiv preprint) | 2021-08-04 | Paper |
Parameterized intractability of even set and shortest vector problem from Gap-ETH
(available as arXiv preprint) | 2021-07-28 | Paper |
ETH-hardness of approximating 2-CSPs and directed Steiner network
(available as arXiv preprint) | 2021-06-15 | Paper |
Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
(available as arXiv preprint) | 2021-05-04 | Paper |
| Generalized Kings and Single-Elimination Winners in Random Tournaments | 2021-05-01 | Paper |
Closing gaps in asymptotic fair division
SIAM Journal on Discrete Mathematics | 2021-04-28 | Paper |
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum <i>k</i>-Coverage, Unique Set Cover and Related Problems (via <i>t</i>-Wise Agreement Testing Theorem)
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
Combinatorica | 2021-01-25 | Paper |
On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
Combinatorica | 2021-01-25 | Paper |
When do envy-free allocations exist?
SIAM Journal on Discrete Mathematics | 2020-10-29 | Paper |
From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
SIAM Journal on Computing | 2020-08-18 | Paper |
| Near-tight closure bounds for Littlestone and threshold dimensions | 2020-07-07 | Paper |
A birthday repetition theorem and complexity of approximating dense CSPs
(available as arXiv preprint) | 2020-05-27 | Paper |
| Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis | 2020-05-27 | Paper |
Multitasking capacity: hardness results and improved constructions
SIAM Journal on Discrete Mathematics | 2020-03-26 | Paper |
On the Parameterized Complexity of Approximating Dominating Set
Journal of the ACM | 2020-02-11 | Paper |
Losing Treewidth by Separating Subsets
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Computing a small agreeable set of indivisible items
Artificial Intelligence | 2019-08-28 | Paper |
On the parameterized complexity of approximating dominating set
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
Algorithms | 2019-05-08 | Paper |
A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
Information Processing Letters | 2019-03-11 | Paper |
Approximation algorithms for label cover and the log-density threshold
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
(available as arXiv preprint) | 2018-04-19 | Paper |
Asymptotic existence of fair divisions for groups
Mathematical Social Sciences | 2017-11-16 | Paper |
An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
(available as arXiv preprint) | 2017-08-31 | Paper |
Approximating dense MAX 2-CSPs
(available as arXiv preprint) | 2017-08-31 | Paper |
Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Improved approximation algorithms for projection games
Algorithmica | 2017-03-03 | Paper |
Dissection with the fewest pieces is hard, even to approximate
Lecture Notes in Computer Science | 2017-02-01 | Paper |
Improved approximation algorithms for projection games (extended abstract)
Lecture Notes in Computer Science | 2013-09-17 | Paper |
