Research archive
Publications
My papers and preprints on fair division, communication complexity, algorithms, and social choice.
Selected results
- Resolved the longstanding problem of bounded envy-free cake cutting for any number of agents.A central question in fair division, open beyond three agents since the 1960s.Part of my PhD thesis, Upper Bounds for Cake Cutting, supervised by Serge Gaspers.
- Refuted the strongest form of the direct sum conjecture for total functions in deterministic communication complexity.Motivated by Karchmer, Raz and Wigderson’s 1991 programme for proving circuit lower bounds.
- Proved NP-completeness of computing deterministic communication complexity. PreprintA question raised in Andrew Yao’s 1979 paper introducing communication complexity.
- Found a different three-agent, eight-good EFX counterexample for submodular valuations that can be understood and checked by hand.Following Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weidenbach, who first showed that EFX can fail for submodular valuations.The two projects have since been combined.
The direct-sum and NP-completeness results are connected by the interlacing programme.
Papers and preprints
36 entries
Recent papers · 2025–2026
Mechanism design & social choice
Anchoring for Truthfulness: The Random-Anchor Volume Mechanism for Multi-Facility Location
A mechanism for three-facility location on the line that is strategyproof in expectation and gives a constant-factor approximation, answering a question of Lu, Sun, Wang and Zhu (2010).
Fair division
When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations
EF1 and Pareto optimality can be incompatible for submodular valuations, even with two agents. This answers a question of Caragiannis et al. (2016).
Under review for the International Conference on Web and Internet Economics (WINE).
Fair division
Best-of-Both-Worlds Fairness for Mixed Goods and Chores
For mixed goods and chores with additive utilities, we show how randomisation can combine envy-freeness in expectation with envy-freeness up to one item (EF1) in every realised allocation.
Under review for the ACM-SIAM Symposium on Discrete Algorithms (SODA).
Fair division
Optimal Subsidy Bounds for Goods and Chores: One Dollar Each Suffices
For additive utilities with item values between −1 and 1, we give a polynomial-time algorithm that eliminates envy using at most one unit of subsidy per agent. This bound is tight.
Under review for the ACM-SIAM Symposium on Discrete Algorithms (SODA).
Algorithms
Faster Exponential-Time Approximate Counting via Bounded Self-Reductions
Faster randomised approximation algorithms for counting independent sets and solutions to 2-SAT, using bounded self-reductions.
Forthcoming.
Fair division
Counterexamples to EFX for Submodular and Subadditive Valuations
Following the first nonexistence result of Akrami, Mayorov, Mehlhorn, Srinivas, and Weidenbach, we gave a different counterexample for submodular valuations that can be checked by hand, with three agents and eight goods.
Original preprint; this work has since been combined with the paper by Akrami, Mayorov, Mehlhorn, Srinivas, and Weidenbach.
Fair division
Fair Division with Indivisible Goods, Chores, and Cake
For mixed indivisible goods and chores together with cake, we prove that envy-freeness for mixed resources (EFM) is always achievable under additive utilities.
Forthcoming.
Mechanism design & social choice
Sampford Apportionment Satisfies Threshold Monotonicity
Sampford apportionment satisfies threshold monotonicity, resolving a conjecture of Correa et al. (2024). A complementary theorem shows that, for seven or more parties, the separate pairwise threshold-monotonicity axiom is incompatible with quota and ex-ante proportionality.
Communication complexity
NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
Computing deterministic communication complexity from a truth table is NP-complete, answering a question raised by Yao in 1979.
Communication complexity
Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
Solving several instances together can require less deterministic communication than solving them separately. This gives a counterexample to the strongest form of the direct sum conjecture for total functions.
Earlier conference papers
Liquid Democracy: An Algorithmic Perspective
The Fluid Mechanics of Liquid Democracy
The provable virtue of laziness in motion planning
ICAPS Best Paper Award.
Complexity of manipulating sequential allocation
A discrete and bounded envy-free cake cutting protocol for any number of agents
A bounded protocol for dividing a cake among any number of agents so that no one prefers another person’s share, settling a longstanding question.
Computational aspects of multi-winner approval voting
Ex post Efficiency of Random Assignments.
On the number of minimal separators in graphs
Fair Assignment of Indivisible Objects under Ordinal Preference
Fixing a balanced knockout tournament
Earlier journal articles
Liquid democracy: An algorithmic perspective
The fluid mechanics of liquid democracy
Fixing balanced knockout and double elimination tournaments
Bounded and envy-free cake cutting
Two desirable fairness concepts for allocation of indivisible objects under ordinal preferences
Fair assignment of indivisible objects under ordinal preferences
Pillage games with multiple stable sets
Manuscripts
Balancing Approximations in Facility Location
Under review for the International Conference on Web and Internet Economics (WINE).
Computational Complexity of Hall Set Problems