October 27-30, 2024

Chicago, IL, USA

Program Schedule

All the times are in CDT (UTC-05:00). The program given below shows the schedule of talks. The schedule of workshops and other activities will be updated later. You can download each day as a separate pdf here: day1.pdf, day2.pdf, day3.pdf, and day4.pdf. The abstracts of the plenary talks can be found here

Proceedings: The proceedings can be accessed here (the username and password have been sent to conference attendees over email). The abstracts of all the accepted papers can be found here

The main conference location is Floor 14. The session rooms are in Floors 14 and 15.  

Session Rooms:  Session A will be in Sauganash East (Floor 14), Session B is in Western Stage House (Floor 14), and Session C is in Lasalle (Floor 15). All plenaries and single-session activities will be in Sauganash East. Lunch can be picked up in the Sauganash West room (Floor 14). 

Day 1: Sunday, October 27, 2024

Room Assignments: Session A will be in Sauganash East (14th floor), Session B is in Western Stage House (14th floor), and Session C is in Lasalle (Floor 15).

The planned events on Day 1 include Workshops, Graduating Bits and an Industry Workshop. The schedule of the workshops is as follows. You can access the detailed schedules for the workshops using the following links: Distortion in Social Choice, Recent Advances in Quantum Learning, Shang-Hua Teng Fest, Workshop on Calibration, Industry Workshop.

 

Workshop Session A
(Sauganash East,
14th floor)

 

Workshop Session B
(Western Stage House,
14th floor)

Workshop Session C
(Lasalle, 
15th floor)

 9:00am – 10:30amShang-Hua Teng Fest
(organized by Dan Spielman and Xiaorui Sun)
Workshop on Calibration
(organized by Jason Hartline, Jamie Morgenstern, Aaron Roth and Yifan Wu)
Recent Advances in Quantum Learning
(organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)
10:30 – 11:00am

Break

 11:00am – 12:00pmShang-Hua Teng Fest
(organized by Dan Spielman and Xiaorui Sun)
Workshop on Calibration
(organized by Jason Hartline, Jamie Morgenstern, Aaron Roth and Yifan Wu)
Recent Advances in Quantum Learning (organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)
12:00pm – 2:00pm

Graduating Bits and
Conference Lunch

Pick up lunch from Sauganash West, before going to Graduating Bits in Sauganash East 
 2:00pm – 3:30pmShang-Hua Teng Fest
(organized by Dan Spielman and Xiaorui Sun)
Distortion in Social Choice
(organized by Moses Charikar, Prasanna Ramakrishnan, Nisarg Shah, and Kangning Wang)
Recent Advances in Quantum Learning
(organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)
3:30pm – 4:00pm

Break

 4:00pm – 5:00pmShang-Hua Teng Fest
(organized by Dan Spielman and Xiaorui Sun)
Distortion in Social Choice
(organized by Moses Charikar, Prasanna Ramakrishnan, Nisarg Shah, and Kangning Wang)
Recent Advances in Quantum Learning
(organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)
5:30pm – 8:00pm

Industry Workshop Session 

Day 2: Monday, October 28, 2024

Room Assignments: Session A will be in Sauganash East (14th floor), Session B is in Western Stage House (14th floor), and Session C is in Lasalle (Floor 15).  All plenaries and single-session activities will be Sauganash EastLunch can picked up from the Sauganash West room (14th floor).

9:00 – 10:30am

Session 1A

(Session chair: Xiaorui Sun)

Session 1B

(Session chair: Kalen Patton)

Session 1C

(Session chair: Dionysios Arvanitakis)

  Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
Authors: M. Garlet Milani, S. Kreutzer, I. Muzi, M. Hatzel
O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
Authors: T. Bell, A. Frieze
On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
Authors: Y. Liu
  First-Order Model Checking on Monadically Stable Graph Classes
Authors: J. Dreier, I. Eleftheriadis, N. Mählmann, R. McCarty, M. Pilipczuk, S. Toruńczyk
Fast Mixing in Sparse Random Ising Models
Authors: K. Liu, S. Mohanty, A. Rajaraman, D. Wu
Fully Dynamic k-Clustering with Fast Update Time and Small Recourse
Authors: S. Bhattacharya, M. Costa, N. Garg, S. Lattanzi, N. Parotsidis
  Obstructions to Erdős-Pósa Dualities for Minors
Authors: C. Paul, E. Protopapas, D. Thilikos, S. Wiederrecht
A Sampling Lovász Local Lemma for Large Domain Sizes
Authors: C. Wang, Y. Yin
Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
Authors: L. Hu, Y. Wu
  Minor Containment and Disjoint Paths in almost-linear time
Authors: T. Korhonen, M. Pilipczuk, G. Stamoulis
Sampling, counting, and large deviations for triangle-free graphs near the critical density Authors: M. Jenssen, W. Perkins, A. Potukuchi, M. Simkin A Lossless Deamortization for Dynamic Greedy Set Cover
Authors: S. Solomon, A. Uzrad, T. Zhang
  Computing the 3-edge-connected components of directed graphs in linear time
Authors: E. Kosinas, L. Georgiadis, G. Italiano
Computational Dynamical Systems
Authors: J. Cotler, S. Rezchikov
The Online Submodular Assignment Problem
Authors: S. Sarkar, D. Hathcock, M. Zlatin, B. Jin, K. Patton
  Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem
Authors: Y. Inoue, K. Kawarabayashi, A. Miyashita, B. Mohar, T. Sonobe
Locally Stationary Distributions
Authors: K. Liu, S. Mohanty, P. Raghavendra, A. Rajaraman, D. Wu
Fully Dynamic Matching and Ordered Ruzsa-Szemer’edi Graphs
Authors: S. Behnezhad, A. Ghafari
10:30 – 10:50am

Break

10:50 – 12:00

Plenary 1 

Roger Myerson, University of Chicago

Dual Reduction and Elementary Games with Senders and Receivers

12:00 – 1:30pm

TCS-For-All Best Research Practices Talk by Ankur Moitra 
and
 Conference Lunch

(Please pick up lunch from common area tables on Floor 14, before going to TCS-For-All talk in Sauganash East) 

1:30pm – 2:30pm

Session 2A

(Session chair: Ioannis Panageas)

Session 2B

(Session chair: Anxin (Bob) Guo)

Session 2C

(Session chair: Sean Hallgren)

  Fast list decoding of univariate multiplicity and folded Reed-Solomon codes
Authors: R. Goyal, P. Harsha, M. Kumar, A. Shankar
Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
Authors: S. Ron, C. Thomas, S. Weinberg, Q. Zhang
Efficient approximate unitary designs from random Pauli rotations
Authors: J. Haah, Y. Liu, X. Tan
  Decoding Quasi-Cyclic Quantum LDPC Codes
Authors: L. Golowich, V. Guruswami
On Pigeonhole Principles and Ramsey in TFNP
Authors: S. Jain, J. Li, R. Robere, Z. Xun
Efficient Unitary Designs from Random Sums and Permutations
Authors: C. Chen, J. Docter, M. Xu, A. Bouland, F. Brandao, P. Hayden
  Optimal Coding Theorems for Randomized Kolmogorov Complexity and Its Applications
Authors: S. Hirahara, Z. Lu, M. Nanashima
An XOR Lemma for Deterministic Communication Complexity
Authors: S. Iyer, A. Rao
Simple constructions of linear-depth t-designs and pseudorandom unitaries
Authors: T. Metger, A. Poremba, M. Sinha, H. Yuen
  Expansion of high-dimensional cubical complexes with application to quantum locally testable codes
Authors: I. Dinur, T. Lin, T. Vidick
The Communication Complexity of Approximating Matrix Rank
Authors: A. Sherstov, A. Storozhenko
Gapped Clique Homology is QMA1-hard and contained in QMA
Authors: R. King, T. Kohler
2:40 – 3:50pm

Plenary 2

Irit Dinur, Weizmann Institute

Expanders and PCPs: Emergence from Local to Global

3:55 – 4:15

Break

4:15 – 5:30PM

Session 3A

(Chair: Meena Mahajan)

Session 3B

(Chair: Yang Liu)

Session 3C

(Chair: Santosh Vempala)

  Reverse Mathematics of Complexity Lower Bounds
Authors: L. Chen, J. Li, I. Oliveira
Optimal Bounds for Open Addressing Without Reordering
Authors: M. Farach-Colton, A. Krapivin, W. Kuszmaul
Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
Authors: N. Buchbinder, M. Feldman
  Interactive Proofs for General Distribution Properties
Authors: T. Herman, G. Rothblum
Tight Analyses of Ordered and Unordered Linear Probing
Authors: M. Braverman, W. Kuszmaul
On Approximating Cutwidth and Pathwidth
Authors: N. Bansal, D. Katzelnick, R. Schwartz
  Trading Determinism for Noncommutativity in Edmonds’ Problem
Authors: V. Arvind, A. Chatterjee, P. Mukhopadhyay
Tight Bounds for Classical Open Addressing
Authors: M. Bender, W. Kuszmaul, R. Zhou
The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2.
Authors: J. Byrka, F. Grandoni, V. Traub
  \Pi_2^p vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
Authors: D. Zhuk
Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
Authors: S. Narayanan, V. Rozhoň, J. Tětek, M. Thorup
Efficient Approximation of Hypertree Width
Authors: V. Surianarayanan, D. Lokshtanov, S. Saurabh, J. Xue, V. Korchemna
  Jump operators, Interactive Proofs and Proof Complexity Generators
Authors: E. Khaniki
An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
Authors: M. Opler
Canonical forms for matrix tuples in polynomial time
Authors: Y. Qiao, X. Sun
6pm

Business Meeting

Day 3: Tuesday, October 29, 2024

Room Assignments: Session A will be in Sauganash East (14th floor), Session B is in Western Stage House (14th floor), and Session C is in Lasalle (Floor 15). Lunch can picked up from the Sauganash West room (14th floor).

9:00 – 10:30am

Session 4A

(Session chair: Maryam Aliakbarpour)

Session 4B

(Session chair: Santosh Vempala)

Session 4C

(Session chair: Sean Hallgren)

 Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
Authors: S. Mouli
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the Dimension Threshold
Authors: V. Guruswami, J. Hsieh, P. Raghavendra
High-Temperature Gibbs States are Unentangled and Efficiently Preparable
Authors: A. Bakshi, A. Liu, A. Moitra, E. Tang
 A Dense Model Theorem for the Boolean Slice
Authors: G. Kalai, N. Lifshitz, T. Ziegler, D. Minzer
Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis
Authors: I. Diakonikolas, S. Karmalkar, S. Pang, A. Potechin
Structure learning of Hamiltonians from real-time evolution
Authors: A. Bakshi, A. Liu, A. Moitra, E. Tang
 Dot-Product Proofs and Their Applications
Authors: N. Bitansky, P. Harsha, Y. Ishai, R. Rothblum, D. Wu
Semirandom Planted Clique and the Restricted Isometry Property
Authors: J. Błasiok, R. Buhai, P. Kothari, D. Steurer
Quantum eigenvalue processing
Authors: G. Low, Y. Su
 

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs Authors: Y. Dikstein, I. Dinur, A. Lubotzky and

and

Constant Degree Direct Product Testers with Small Soundness Authors: M. Bafna, N. Lifshitz, D. Minzer

Efficient Certificates of Anti-Concentration Beyond Gaussians
Authors: A. Bakshi, P. Kothari, G. Rajendran, M. Tulsiani, A. Vijayaraghavan
Quantum computational advantage with constant-temperature Gibbs sampling
Authors: T. Bergamaschi, C. Chen, Y. Liu
 Chernoff-Hoeffding and Reverse Hypercontractivity on High Dimensional Expanders
Authors: Y. Dikstein, M. Hopkins
Efficient Statistics With Unknown Truncation: Polynomial Time Algorithms Beyond Gaussians
Authors: J. Lee, A. Mehrotra, M. Zampetakis
Optimal tradeoffs for estimating Pauli observables
Authors: S. Chen, W. Gong, Q. Ye
 New investigations into noncommutative CSPs
Authors: E. Culf, H. Mousavi, T. Spirig
Tensor cumulants for statistical inference on invariant distributions
Authors: D. Kunisky, C. Moore, A. Wein
A computational test of quantum contextuality, and even simpler proofs of quantumness
Authors: A. Arora, A. Coladangelo, A. Cojocaru, K. Bharti

10:30 – 10:50am

Break

10:50 – 12:00

Plenary 3

Christos Papadimitriou, Columbia University

Computing with Dynamical Systems

  

12pm – 1:30pm

Conference Lunch

1:30pm – 2:20pm

Session 5: Best Student Papers (Machtey Prize)

(Session chair: Santosh Vempala)
 
Capacity Threshold for the Ising Perceptron
Authors: B. Huang
 
Optimal quantile estimation: beyond the comparison model
Authors: M. Singhal, M. Gupta, H. Wu

2:40 – 3:50pm

Knuth Prize Lecture

Rajeev Alur, University of Pennsylvania

Specification-guided Reinforcement Learning 

3:55 – 4:15

Break

4:15 – 5:30pm

Session 6A

(Session chair: He Jia)

Session 6B

(Session chair: Chang Wang)

Session 6C

(Session chair: Emanuele Viola)

 Proofs of Space with Maximal Hardness
Authors: L. Reyzin
Online Combinatorial Allocations and Auctions with Few Samples
Authors: P. Duetting, T. Kesselheim, B. Lucier, R. Reiffenhauser, S. Singla
The Tractability Border of Reachability in Simple Vector Addition Systems with States
Authors: D. Chistikov, W. Czerwiński, Ł. Orlikowski, F. Mazowiecki, H. Sinclair-Banks, K. Węgrzycki
 Commitments are equivalent to one-way state generators
Authors: R. Batra, J. Rahul
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
Authors: Y. Jin, P. Lu
Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
Authors: M. Abrahamsen, J. Stade
 Succinct arguments for QMA from standard assumptions via compiled nonlocal games
Authors: T. Metger, A. Natarajan, T. Zhang
Semi-Bandit Learning for Monotone Stochastic Optimization
Authors: A. Agarwal, R. Ghuge, V. Nagarajan
The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds
Authors: R. Williams
 Certifying almost all quantum states with few single-qubit measurements
Authors: H. Huang, J. Preskill, M. Soleimanifar
On Robustness to k-wise Independence of Optimal Bayesian Mechanisms
Authors: N. Gravin, Z. Wang
Strong vs. Weak Range Avoidance and the Linear Ordering Principle
Authors: O. Korten, T. Pitassi
 How to Simulate Random Oracles with Auxiliary Input
Authors: Y. Dodis, A. Jain, R. Lin, J. Luo, D. Wichs
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
Authors: R. Gao, M. Roghani, A. Rubinstein, A. Saberi
Faster isomorphism testing of p-groups of Frattini class-2
Authors: G. Ivanyos, E. Mendoza, Y. Qiao, X. Sun, C. Zhang

Day 4: Wednesday, October 30, 2024

Room Assignments: Session A will be in Sauganash East (14th floor), Session B is in Western Stage House (14th floor), and Session C is in Lasalle (Floor 15). All plenaries and single-session activities will be Sauganash EastLunch can picked up from the Sauganash West room (14th floor).

 

9:00 – 10:30am

Session 7A

(Session chair: Santosh Vempala)

Session 7B

(Session chair: Yang Liu)

Session 7C

(Session chair: Dionysios Arvanitakis)

 Boosting uniformity in quasirandom groups: faster and simpler
Authors: E. Viola, H. Derksern, C. Lee
Improved Distance (Sensitivity) Oracles with Subquadratic Space
Authors: D. Bilò, S. Chechik, K. Choudhary, S. Cohen, T. Friedrich, M. Schirneck
Replicability in High Dimensional Statistics
Authors: M. Hopkins, R. Impagliazzo, D. Kane, S. Liu, C. Ye
 The sample complexity of smooth boosting and the tightness of the hardcore theorem
Authors: G. Blanc, A. Hayderi, C. Koch, L. Tan
Sparse graph counting and Kelley–Meka bounds for binary systems
Authors: Y. Filmus, H. Hatami, K. Hosseini, E. Kelman
Computing Approximate Centerpoints in Polynomial Time
Authors: Y. Cherapanamjeri
 On the Existence of Seedless Condensers: Exploring the Terrain
Authors: E. Chattopadhyay, M. Gurumukhani, N. Ringach
Towards Instance-Optimal Euclidean Spanners
Authors: H. Le, S. Solomon, C. Than, C. T\’oth, T. Zhang
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
Authors: S. Khanna, A. Putterman, M. Sudan
 Tight Bounds for the Zig-Zag Product
Authors: G. Cohen, G. Maor, I. Cohen
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
Authors: F. Eisenbrand, L. Rohwedder, K. Wegrzycki
Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds
Authors: N. Bansal, V. Cohen-Addad, M. Prabhu, D. Saulpic, C. Schwiegelshohn
 Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
Authors: J. Li, E. Pyne, R. Tell
Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Authors: X. Yu, D. Kunisky
Novel properties of hierarchical probabilistic partitions and their algorithmic applications
Authors: S. Banerjee, Y. Bartal, L. Gottlieb, A. Hovav
 Improved Condensers for Chor-Goldreich Sources
Authors: J. Goodman, X. Li, D. Zuckerman
New Structures and Algorithms for Length-Constrained Expander Decompositions
Authors: B. Haeupler, D Hershkowitz, Z. Tan
Spectral Guarantees for Adversarial Streaming PCA
Authors: Z. Xun, E. Price

10:30 – 10:50am

Break

10:50 – 12:05pm

Session 8A

(Session chair: Xiaorui Sun)

Session 8B

(Session chair: Idan Attias)

Session 8C

(Session chair: Santosh Vempala)

 

A stronger bound for linear 3-LCC
Authors: T. Yankovitz

and

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Authors: P. Kothari, P. Manohar

Gaussian Approximation of Convex Sets by Intersections of Halfspaces
Authors: A. De, S. Nadimpalli, R. Servedio
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Authors: J. van den Brand, L. Chen, R. Kyng, Y. Liu, S. Meierhans, M. Gutenberg, S. Sachdeva
 Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
Authors: Z. Guo, C. Xing, C. Yuan, Z. Zhang
Agnostically Learning Multi-index Models with Queries
Authors: I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, N. Zarifis
Dynamic Deterministic Constant-Approximate Distance Oracles with Worst-Case Update Time
Authors: B. Haeupler, Y. Long, T. Saranurak
 Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
Authors: O. Alrabiah, V. Guruswami
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Authors: N. Golowich, A. Moitra, D. Rohatgi
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Authors: D. Kempa, T. Kociumaka
 An Improved Line-Point Low-Degree Test
Authors: P. Harsha, M. Kumar, R. Saptharishi, M. Sudan
Revisiting Agnostic PAC Learning
Authors: S. Hanneke, K. Larsen, N. Zhivotovskiy
Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
Authors: A. Bernstein, J. Blikstad, T. Saranurak, T. Tu
 Fast decision tree learning solves hard coding-theoretic problems
Authors: C. Koch, C. Strassle, L. Tan
Ramsey Theorems for Trees and a General ‘Private Learning Implies Online Learning’ Theorem
Authors: S. Fioravanti, S. Hanneke, S. Moran, H. Schefler, I. Tsubari
Near-Optimal (1+ϵ)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs
Authors: A. Filtser, G. Goranci, N. Patel, M. Gutenberg

12:05 – 1:30pm

Conference Lunch

1:30pm – 2:20pm

Session 9: Best Papers

(Session chair: Aravindan Vijayaraghavan)
 
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Authors: B. Haeupler, R. Hladík, V. Rozhon, R. Tarjan, J. Tětek
 
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
Authors: M. Ghaffari, C. Grunau

2:20 – 2:45

Break

2:45 – 4:15pm

Session 10A

(Session chair: He Jia)

Session 10B

(Session chair: Vaidehi Srinivas)

Session 10C

(Session chair: Santosh Vempala)

 Verifying Groups in Linear Time
Authors: O. Klein, I. Komargodski, S. Evra, S. Gadot
Nearly Optimal List Labeling
Authors: M. Bender, A. Conway, M. Farach-Colton, H. Komlos, M. Koucky, W. Kuszmaul, M. Saks
The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution
Authors: Z. Ding, E. Epperly, L. Lin, R. Zhang
 Power Series Composition in Near-Linear Time
Authors: Y. Kinoshita, B. Li
Stochastic Online Correlated Selection
Authors: Z. Chen, Z. Huang, E. Sun
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
Authors: R. Andrews, A. Wigderson
 Faster (Δ+1)-Edge Coloring: Breaking the Time Barrier
Authors: S. Bhattacharya, D. Carmon, M. Costa, S. Solomon, T. Zhang
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
Authors: R. Pinto Jr.
Gradient descent for unbounded convex functions on Hadamard manifolds and its applications to scaling problems
Authors: H. Hirai, K. Sakabe
 An Improved Pseudopolynomial Time Algorithm for Subset Sum
Authors: L. Chen, J. Lian, Y. Mao, G. Zhang
Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
Authors: K. Dvijotham, H. McMahan, K. Pillutla, T. Steinke, A. Thakurta
On the Complexity of Avoiding Heavy Elements
Authors: Z. Lu, I. Oliveira, H. Ren, R. Santhanam
 Naively Sorting Evolving Data is Optimal and Robust
Authors: G. Giakkoupis, M. Kiwi, D. Los
A Strong Separation for Adversarially Robust Estimation for Linear Sketches
Authors: E. Gribelyuk, H. Lin, D. Woodruff, H. Yu, S. Zhou
Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
Authors: M. Blanchard
 Tight Bounds for Sorting Under Partial Information
Authors: I. van der Hoog, D. Rutschmann