Efficient Splitting of Measures and Necklaces

Jerzy Neyman: Un theoreme d’existence. CR Acad, Sci. Paris, 1946, 222: 843-845

1946

Earlier work this paper cites.

Charles R. Hobby and John R. Rice: A moment problem in L 1 L_{1} approximation. Proceedings of the American Mathematical Society. 16 (4): 665–670, 1965

1965

Earlier work this paper cites.

Robert Tijdeman: On a distribution problem in finite and countable sets. Journal of Combinatorial Theory, Series A, Vol. 15, Issue 2, September 1973, pp. 129–137

1973

Earlier work this paper cites.

Sandeep N. Bhatt and Charles E. Leiserson: How to assemble tree machines. Proceedings of the 14th Symposium on the Theory of Computing, San Francisco, 1981, pp. 99-104

1981

Earlier work this paper cites.

Sandeep N. Bhatt and Frank T. Leighton: A Framework For Solving VLSI Graph Layout Problems. Journal of Computer and System Sciences 28(2), 1984, pp. 300-343

1984

Earlier work this paper cites.

Charles H. Goldberg and Douglas B. West: Bisection of circle colorings. SIAM J. Algebraic Discrete Methods 6, 1985, 93–106

1985

Earlier work this paper cites.

Noga Alon and Douglas B. West : The Borsuk-Ulam Theorem and Bisection of Necklaces. Proceedings of the American Mathematical Society, Vol. 98, No. 4, Dec. 1986, pp. 623-628

1986

Earlier work this paper cites.

Noga Alon: Splitting necklaces. Advances in Mathematics 63, 1987, 247-253

1987

Earlier work this paper cites.

Noga Alon: Non-constructive proofs in Combinatorics. Proceedings of the International Congress of Mathematicians (ICM), Kyoto 1990, Japan, Springer Verlag, Tokyo, 1991, 1421-1429

1991

Earlier work this paper cites.

Christos H. Papadimitriou: On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences 48, 1994, pp. 498–532

1994

Cited alongside, same era.

Steven J. Brams and Alan D. Taylor: Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996

1996

Cited alongside, same era.

Forest W. Simmons and Francis E. Su: Consensus-halving via theorems of Borsuk-Ulam and Tucker. Mathematical Social Sciences, Vol. 45, 2003, pp. 15–25

2003

Cited alongside, same era.

Noga Alon, Michael Krivelevich, Joel H. Spencer and Tibor Szabó: Discrepancy Games. The Electronic Journal of Combinatorics, Vol. 12, No 1 R, 2005

2005

Cited alongside, same era.

Noga Alon, Dana Moshkovitz and Muli Safra: Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms 2, 2006, 153-177

Nikhil Bansal and Joel H. Spencer: Deterministic Discrepancy Minimization. Algorithmica, Vol. 67, 2013, pp. 451-471

2013

Later among the works it cites.

Frédéric Meunier: Simplotopal maps and necklace splitting. Discrete Mathematics, Volume 323, 28 May 2014, Pages 14-26

2014

Later among the works it cites.

Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg and Jie Zhang: Hardness Results for Consensus Halving. 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 2018, pp. 24:1 - 24:16

2018

Later among the works it cites.

Aris Filos-Ratsikas and Paul W. Goldberg: The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches. arXiv:1805.12559, 2018

Original

2018

Later among the works it cites.

Aris Filos-Ratsikas and Paul W. Goldberg: Consensus Halving is PPA-Complete. Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), 2018, pp. 51–64