Fetching the paper…
Reading the bibliography…
In the $\varepsilon$-Consensus-Halving problem, a fundamental problem in fair division, there are $n$ agents with valuations over the interval $[0,1]$, and the goal is to divide the interval into pieces and assign a label "$+$" or "$-$" to each piece, such that every agent values the total amount of "$+$" and the total amount of "$-$" almost equally.
Drei Sätze über die n-dimensionale euklidische Sphäre
Karol Borsuk · 1933
Earlier work this paper cites.
Un théorème d’existence
Jerzy Neyman · 1946
Earlier work this paper cites.
Sur la division pragmatique
Hugo Steinhaus · 1949
Earlier work this paper cites.
A moment problem in L1 approximation
Charles R. Hobby and John R. Rice · 1965
Earlier work this paper cites.
On a topological generalization of a theorem of Tverberg
Imre Bárány, Senya B. Shlosman, and András Szücs · 1981
Earlier work this paper cites.
Bisection of Circle Colorings
Charles H. Goldberg and Douglas B. West · 1985
Earlier work this paper cites.
The Borsuk-Ulam Theorem and Bisection of Necklaces
Noga Alon and Douglas B. West · 1986
Earlier work this paper cites.
Splitting necklaces
Noga Alon · 1987
Earlier work this paper cites.
On total functions, existence theorems and computational complexity
Nimrod Megiddo and Christos H. Papadimitriou · 1991
Earlier work this paper cites.
On the complexity of the parity argument and other inefficient proofs of existence
Christos H. Papadimitriou · 1994
Earlier work this paper cites.
Fair Division: From cake-cutting to dispute resolution
Steven J. Brams and Alan D. Taylor · 1996
Earlier work this paper cites.
A Sperner lemma complete for PPA
Michelangelo Grigni · 2001
Earlier work this paper cites.
Some Topological Properties of Disk and Sphere
Albert W. Tucker · 2002
Earlier work this paper cites.
Consensus-halving via theorems of Borsuk-Ulam and Tucker
Forest W. Simmons and Francis E. Su · 2003
Cited alongside, same era.
Efficient splitting of measures and necklaces
Noga Alon and Andrei Graur · 2006
Cited alongside, same era.
Settling the complexity of computing two-player Nash equilibria
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009
Cited alongside, same era.
The complexity of computing a Nash equilibrium
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou · 2009
Cited alongside, same era.
Combinatorial Necklace Splitting
Dömötör Pálvölgyi · 2009
Cited alongside, same era.
On the complexity of Nash equilibria and other fixed points
Kousha Etessami and Mihalis Yannakakis · 2010
Cited alongside, same era.
Constant rank two-player games are PPAD-hard
Ruta Mehta · 2018
Later among the works it cites.
2-D Tucker is PPA complete
James Aisenberg, Maria Luisa Bonet, and Sam Buss · 2019
Later among the works it cites.
Fair and efficient cake division with connected pieces
Eshwar Ram Arunachaleswaran, Siddharth Barman, Rachitesh Kumar, and Nidhi Rathi · 2019
Later among the works it cites.
The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches
Aris Filos-Ratsikas and Paul W. Goldberg · 2019
Later among the works it cites.
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, and Paul G. Spirakis · 2020
Closest in time.
Understanding PPA-completeness
Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu · 2020
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Algorithmic solutions for envy-free cake cutting
Xiaotie Deng, Qi Qi, and Amin Saberi · 2012
Cited alongside, same era.
A discrete and bounded envy-free cake cutting protocol for any number of agents
Haris Aziz and Simon Mackenzie · 2016
Cited alongside, same era.
The complexity of non-monotone markets
Xi Chen, Dimitris Paparas, and Mihalis Yannakakis · 2017
Cited alongside, same era.
Octahedral Tucker is PPA-complete
Xiaotie Deng, Zhe Feng, and Rucha Kulkarni · 2017
Cited alongside, same era.
Substitution with satiation: A new class of utility functions and a complementary pivot algorithm
Jugal Garg, Ruta Mehta, and Vijay V. Vazirani · 2017
Cited alongside, same era.
Consensus Halving is PPA-complete
Aris Filos-Ratsikas and Paul W. Goldberg · 2018
Cited alongside, same era.
On the Complexity of Modulo- q q Arguments and the Chevalley-Warning Theorem
Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis · 2020
Closest in time.
Strong approximate Consensus Halving and the Borsuk-Ulam theorem
Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh · 2021
Closest in time.
A topological characterization of modulo- p p arguments and implications for necklace splitting
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, and Manolis Zampetakis · 2021
Closest in time.
The Hairy Ball problem is PPAD-complete
Paul W. Goldberg and Alexandros Hollender · 2021
Closest in time.
The classes PPA- k k : Existence from arguments modulo k k
Alexandros Hollender · 2021
Closest in time.
Two’s company, three’s a crowd: Consensus-halving for a constant number of agents
Argyrios Deligkas, Aris Filos-Ratsikas, and Alexandros Hollender · 2022
Closest in time.