References

Graph expansion and the Unique Games Conjecture

Prasad Raghavendra and David Steurer · 2010 · misc

Proceedings of the 42nd ACM Symposium on Theory of Computing, 755–764.

Reductions Between Expansion Problems

Prasad Raghavendra and David Steurer and Madhur Tulsiani · 2012 · misc

Proceedings of the 27th IEEE Conference on Computational Complexity, 64–73.

Subexponential Algorithms for Unique Games and Related Problems

Sanjeev Arora and Boaz Barak and David Steurer · 2015 · misc

Journal of the ACM 62 (2015), no. 5, article 42, 1–25.

Statistical Treatment of Polymer Solutions at Infinite Dilution

Orr, W. J. C. · 1947 · article

Exact Critical Point and Critical Exponents of O(n) Models in Two Dimensions

Nienhuis, Bernard · 1982 · article

Self-Avoiding Walks

Slade, Gordon · 2019 · article

First-Passage Percolation, Subadditive Processes, Stochastic Networks, and Generalized Renewal Theory

Hammersley, J. M. and Welsh, D. J. A. · 1965 · incollection

50 Years of First-Passage Percolation

Auffinger, Antonio and Damron, Michael and Hanson, Jack · 2017 · book

Sublinear Variance in First-Passage Percolation for General Distributions

Damron, Michael and Hanson, Jack and Sosoe, Philippe · 2015 · article

On the Liapounoff Limit of Error in the Theory of Probability

Esseen, Carl-Gustav · 1942 · article

On the Absolute Constants in the Berry–Esseen Inequality and Its Structural and Nonuniform Improvements

Shevtsova, Irina G. · 2013 · article

On the Nonuniform Berry–Esseen Bound

Pinelis, Iosif · 2017 · incollection

A Gaussian Inequality for Expected Absolute Products

Li, Wenbo V. and Wei, Ang · 2012 · article

Three-Dimensional Gaussian Product Inequality with Positive Integer Order Moments

Kim, Bara and Kim, Jeongsim and Kim, Jerim · 2025 · article

Towards a Genuinely Polynomial Algorithm for Linear Programming

Megiddo, Nimrod · 1983 · article

Mathematical Problems for the Next Century

Smale, Steve · 1998 · article

A Strongly Polynomial Algorithm for Linear Programs with at Most Two Nonzero Entries per Row or Column

Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and Olver, Neil and V\'egh, L\'aszl\'o A. · 2024 · inproceedings

How Good Is the Simplex Algorithm?

Klee, Victor and Minty, George J. · 1972 · incollection

A Subexponential Randomized Simplex Algorithm

Kalai, Gil · 1992 · inproceedings

Subexponential Lower Bounds for Randomized Pivoting Rules for the Simplex Algorithm

Friedmann, Oliver and Hansen, Thomas Dueholm and Zwick, Uri · 2011 · inproceedings

A Quasi-Polynomial Bound for the Diameter of Graphs of Polyhedra

Kalai, Gil and Kleitman, Daniel J. · 1992 · article

A Counterexample to the Hirsch Conjecture

Santos, Francisco · 2012 · article

An Improved Kalai–Kleitman Bound for the Diameter of a Polyhedron

Todd, Michael J. · 2014 · article

Heuristic Analysis, Linear Programming and Branch and Bound

Wolsey, Laurence A. · 1980 · article

A (Slightly) Improved Approximation Algorithm for Metric TSP

Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan · 2021 · inproceedings

Approximation Algorithms for Traveling Salesman Problems

Traub, Vera and Vygen, Jens · 2024 · book

The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate

Ye, Yinyu · 2011 · article

The Simplex Method Is Strongly Polynomial for Deterministic Markov Decision Processes

Post, Ian and Ye, Yinyu · 2015 · article

The Shortest Path through Many Points

Beardwood, Jillian and Halton, J. H. and Hammersley, J. M. · 1959 · article

An Improved Lower Bound for the Traveling Salesman Constant

Gaudio, Julia and Jaillet, Patrick · 2020 · article

A New Upper Bound for the Euclidean TSP Constant

Carlsson, John Gunnar and Yu, Julien · 2026 · article

Published online September 5, 2025

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers

Gaudio, Julia and Guan, Charlie K. · 2026 · misc

The Modified Integer Round-Up Property of the One-Dimensional Cutting Stock Problem

Scheithauer, Guntram and Terno, Johannes · 1995 · article

An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem

Karmarkar, Narendra and Karp, Richard M. · 1982 · inproceedings

A Logarithmic Additive Integrality Gap for Bin Packing

Hoberg, Rebecca and Rothvoss, Thomas · 2017 · inproceedings

The Zero Error Capacity of a Noisy Channel

Shannon, Claude E. · 1956 · article

On the Shannon Capacity of a Graph

Lov\'asz, L\'aszl\'o · 1979 · article

New Lower Bound on the Shannon Capacity of $C_7$ from Circular Graphs

Polak, Sven C. and Schrijver, Alexander · 2019 · article

Improved Lower Bounds for the Shannon Capacity of Odd Cycles

Itty, Nathaniel and Rosin, Christopher D. and Carstensen, Chase and Reichman, Daniel · 2026 · misc

Shannon's Theorems for Channels with Synchronization Errors

Dobrushin, Roland L. · 1967 · article

A Survey of Results for Deletion Channels and Related Synchronization Channels

Mitzenmacher, Michael · 2009 · article

Improved Upper and Lower Bounds on the Capacity of the Binary Deletion Channel

Rubinstein, Ittai and Con, Roni · 2023 · misc

A Comparison of Signalling Alphabets

Gilbert, Edgar N. · 1952 · article

Estimate of the Number of Signals in Error Correcting Codes

Varshamov, Rom R. · 1957 · article

New Upper Bounds on the Rate of a Code via the Delsarte–MacWilliams Inequalities

McEliece, Robert J. and Rodemich, Eugene R. and Rumsey, Howard C. and Welch, Lloyd R. · 1977 · article

Tracing AG Codes: Toward Meeting the Gilbert–Varshamov Bound

Cohen, Gil and Doron, Dean and Goldgraber, Noam and Manket, Tomer · 2026 · inproceedings

On Runge–Kutta Processes of High Order

Butcher, John C. · 1964 · article

A Symbolic-Numeric Approach to the Solution of the Butcher Equations

Khashin, Sergey · 2010 · misc

Preliminary version, August 1, 2010