Discrepancy Minimization via a Self-Balancing Walk

Josef Hadar and William R Russell, Rules for ordering uncertain prospects , The American Economic Review 59

1969

Earlier work this paper cites.

Giora Hanoch and Haim Levy, The efficiency analysis of choices involving risk , The Review of Economic Studies 36

1969

Earlier work this paper cites.

Michael Rothschild and Joseph E Stiglitz, Increasing risk: I. A definition , Journal of Economic theory 2

1970

Earlier work this paper cites.

Joel Spencer, Balancing games , J. Comb. Theory, Ser. B 23

1977

Earlier work this paper cites.

Joel Spencer, Six standard deviations suffice , Trans. Amer. Math. Soc. 289

1985

Earlier work this paper cites.

Joel H Spencer, Aravind Srinivasan, and Prasad Tetali, The discrepancy of permutation families , Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), ACM, New York, 1997, pp. 692–701

1997

Earlier work this paper cites.

Wojciech Banaszczyk, Balancing vectors and gaussian measures of n-dimensional convex bodies , Random Structures & Algorithms 12

1998

Earlier work this paper cites.

Nikhil Bansal, Constructive algorithms for discrepancy minimization , 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, IEEE Computer Society, 2010, pp. 3–10

2010

Earlier work this paper cites.

Wojciech Banaszczyk, On series of signed vectors and their rearrangements , Random Structures & Algorithms 40

2012

Cited alongside, same era.

Alantha Newman, Ofer Neiman, and Aleksandar Nikolov, Beck’s three permutations conjecture: A counterexample and some consequences , 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, IEEE, 2012, pp. 253–262

2012

Cited alongside, same era.

Shachar Lovett and Raghu Meka, Constructive discrepancy minimization by walking on the edges , SIAM J. Comput. 44

2015

Cited alongside, same era.

Jirí Matousek and Aleksandar Nikolov, Combinatorial discrepancy for boxes via the gamma_2 norm , 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands (Lars Arge and János Pach, eds.), LIPIcs, vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 1–15

2015

Cited alongside, same era.

Juhan Aru, Bhargav Narayanan, Alex Scott, and Ramarathnam Venkatesan, Balancing sums of random vectors , Discrete Anal. (2018), Paper No. 4, 17

2018

Later among the works it cites.

Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett, The gram-schmidt walk: a cure for the Banaszczyk blues , Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 (Ilias Diakonikolas, David Kempe, and Monika Henzinger, eds.), ACM, 2018, pp. 587–597

2018

Later among the works it cites.

Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, and Nicole Tomczak-Jaegermann, Balancing vectors in any norm , 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2018, pp. 1–10

2018

Later among the works it cites.

Ronen Eldan and Mohit Singh, Efficient algorithms for discrepancy minimization in convex sets , Random Struct. Algorithms 53

2018

Later among the works it cites.