{"id":308,"date":"2020-07-25T02:00:51","date_gmt":"2020-07-25T02:00:51","guid":{"rendered":"http:\/\/ieeecs-wp-pro.computer.org\/?page_id=308"},"modified":"2024-11-19T03:07:21","modified_gmt":"2024-11-19T03:07:21","slug":"schedule","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2024\/program\/schedule\/","title":{"rendered":"Schedule"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

Program Schedule<\/h1>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

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<\/a>, day2.pdf<\/a>, day3.pdf<\/a>, and day4.pdf<\/a>. The abstracts of the plenary talks can be found here<\/a>. <\/p>\n

Proceedings:<\/b> The proceedings can be accessed here<\/a> (the username and password have been sent to conference attendees over email). The abstracts of all the accepted papers can be found here<\/a>. <\/p>\n

The main conference location is Floor 14. The session rooms are in Floors 14 and 15.  <\/span><\/p>\n

Session Rooms: <\/span> <\/span>Session A<\/span> will be in <\/span>Sauganash East<\/span> (Floor 14),<\/span> Session B<\/span> is in <\/span>Western Stage House<\/span> (Floor 14), and <\/span>Session C<\/span> is in<\/span> Lasalle<\/span> (Floor 15)<\/strong>. All plenaries and single-session activities will be in <\/span>Sauganash East<\/span>. Lunch can be picked up in the Sauganash West room (Floor 14). <\/span><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t

\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tDay 1<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tDay 2<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tDay 3<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\n\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\tDay 4<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t
\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Day 1: Sunday, October 27, 2024<\/span><\/h1>

Room Assignments:<\/span>\u00a0Session A<\/span> will be in Sauganash East<\/span> (14th floor), Session B<\/span> is in Western Stage House<\/span> (14th floor), and Session C<\/span> is in Lasalle<\/span>\u00a0(Floor 15).<\/p>

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

\u00a0<\/h4><\/td>

Workshop Session A
(Sauganash East,
14th floor)<\/span><\/h3>
\u00a0<\/div><\/td>

Workshop Session B
(Western Stage House,
14th floor)<\/span><\/h3><\/td>

Workshop Session C
(Lasalle,\u00a0
15th floor)<\/span><\/h3><\/td><\/tr>

\u00a09:00am – 10:30am<\/b><\/td>Shang-Hua Teng Fest<\/strong><\/a>
(organized by Dan Spielman and Xiaorui Sun)<\/td>		Workshop on Calibration<\/strong><\/a>
(organized by Jason Hartline, Jamie Morgenstern, Aaron Roth and Yifan Wu)<\/td>		Recent Advances in Quantum Learning<\/strong><\/a>
(organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)<\/td><\/tr>
10:30 – 11:00am<\/span><\/td>

Break<\/span><\/h3><\/th><\/tr>

\u00a011:00am – 12:00pm<\/b><\/td>Shang-Hua Teng Fest<\/strong><\/a>
(organized by Dan Spielman and Xiaorui Sun)<\/td>		Workshop on Calibration<\/strong><\/a>
(organized by Jason Hartline, Jamie Morgenstern, Aaron Roth and Yifan Wu)<\/td>		Recent Advances in Quantum Learning<\/strong><\/a> (organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)<\/td><\/tr>
12:00pm – 2:00pm<\/span><\/td>

Graduating Bits<\/a>\u00a0and
Conference Lunch
<\/span><\/h3>
Pick up lunch from Sauganash West, before going to Graduating Bits in Sauganash East\u00a0<\/span><\/h5><\/th><\/tr>

\u00a02:00pm – 3:30pm<\/b><\/td>Shang-Hua Teng Fest<\/strong><\/a>
(organized by Dan Spielman and Xiaorui Sun)<\/td>		Distortion in Social Choice <\/strong><\/a>
(organized by Moses Charikar, Prasanna Ramakrishnan, Nisarg Shah, and Kangning Wang)<\/td>		Recent Advances in Quantum Learning<\/strong><\/a>
(organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)<\/td><\/tr>
3:30pm – 4:00pm<\/span><\/td>

Break<\/span><\/h3><\/th><\/tr>

\u00a04:00pm – 5:00pm<\/b><\/td>Shang-Hua Teng Fest<\/strong><\/a>
(organized by Dan Spielman and Xiaorui Sun)<\/td>		Distortion in Social Choice<\/a>
<\/strong> (organized by Moses Charikar, Prasanna Ramakrishnan, Nisarg Shah, and Kangning Wang)<\/td>		Recent Advances in Quantum Learning<\/strong><\/a>
(organized by organized by Sitan Chen Jordan Cotler, Robert Huang, Jerry Li)<\/td><\/tr>
5:30pm – 8:00pm<\/span><\/td>

Industry Workshop Session<\/a>\u00a0<\/span><\/h3><\/th><\/tr><\/tbody><\/table>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t
\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Day 2: Monday, October 28, 2024<\/span><\/h1>
Room Assignments:<\/span>\u00a0Session 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).\u00a0 All plenaries and single-session activities will be Sauganash East<\/span>.\u00a0Lunch can picked up from the Sauganash West room (14th floor).<\/span>
<\/span><\/div><\/colgroup>

9:00 – 10:30am<\/h4><\/td>

Session 1A
<\/span><\/h3>

(Session chair: Xiaorui Sun)<\/p><\/td>

Session 1B<\/span><\/h3>

(Session chair: Kalen Patton)<\/p><\/td>

Session 1C<\/span><\/h3>

(Session chair: Dionysios Arvanitakis)<\/p><\/td><\/tr>

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

Break<\/span><\/h3><\/th><\/tr>

10:50 – 12:00<\/b><\/td>

Plenary 1\u00a0<\/span><\/a><\/h3>

Roger Myerson, University of Chicago<\/h4>

Dual Reduction and Elementary Games with Senders and Receivers<\/a><\/p><\/th><\/tr>

12:00 – 1:30pm<\/b><\/td>

TCS-For-All Best Research Practices Talk by Ankur Moitra\u00a0
and<\/span>\u00a0Conference Lunch
<\/span><\/h3>
(Please pick up lunch from common area tables on Floor 14, before going to TCS-For-All talk in Sauganash East)\u00a0<\/span><\/h5><\/th><\/tr>

1:30pm – 2:30pm<\/b><\/span><\/p><\/td>

Session 2A<\/span><\/h3>

(Session chair: Ioannis Panageas)<\/p><\/td>

Session 2B<\/span><\/h3>

(Session chair: Anxin (Bob) Guo)<\/p><\/td>

Session 2C<\/span><\/h3>

(Session chair: Sean Hallgren)<\/p><\/td><\/tr>

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

Plenary 2 <\/span><\/a><\/h3>

Irit Dinur, Weizmann Institute<\/h4>

Expanders and PCPs: Emergence from Local to Global<\/p><\/th><\/tr>

3:55 – 4:15<\/b><\/td>

Break<\/span><\/h4><\/th><\/tr>

4:15 – 5:30PM<\/b><\/td>

Session 3A<\/span><\/h3>

(Chair: Meena Mahajan)<\/p><\/td>

Session 3B<\/span><\/h3>

(Chair: Yang Liu)<\/p><\/td>

Session 3C<\/span><\/h3>

(Chair: Santosh Vempala)<\/p><\/td><\/tr>

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

Business Meeting<\/span><\/h3><\/th><\/tr><\/tbody><\/table>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t
\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Day 3: Tuesday, October 29, 2024<\/span><\/h1>

Room Assignments:<\/span>\u00a0Session A<\/span> will be in Sauganash East<\/span> (14th floor), Session B<\/span> is in Western Stage House<\/span> (14th floor), and Session C<\/span> is in Lasalle<\/span>\u00a0(Floor 15).\u00a0Lunch can picked up from the Sauganash West room (14th floor).<\/span><\/p><\/div><\/colgroup>

9:00 – 10:30am<\/h4><\/td>

Session 4A<\/span><\/h3>

(Session chair: Maryam Aliakbarpour)<\/p><\/td>

Session 4B<\/span><\/h3>

(Session chair: Santosh Vempala)<\/p><\/td>

Session 4C<\/span><\/h3>

(Session chair: Sean Hallgren)<\/p><\/td><\/tr>

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

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs<\/a> Authors: Y. Dikstein, I. Dinur, A. Lubotzky and<\/p>

and<\/em><\/p>

Constant Degree Direct Product Testers with Small Soundness Authors: M. Bafna, N. Lifshitz, D. Minzer<\/p><\/td>

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

10:30 – 10:50am<\/h4><\/td>

Break<\/span><\/h3><\/th><\/tr>

10:50 – 12:00<\/h4><\/td>

Plenary 3<\/span><\/a><\/h3>

Christos Papadimitriou, Columbia University<\/h4>

Computing with Dynamical Systems<\/a><\/p><\/th>

\u00a0<\/td>\u00a0<\/td><\/tr>

12pm – 1:30pm<\/h4><\/td>

Conference Lunch<\/span><\/h3><\/th><\/tr>

1:30pm – 2:20pm<\/h4><\/td>

Session 5: Best Student Papers (Machtey Prize)<\/span><\/h3>
(Session chair: Santosh Vempala)<\/h6><\/th><\/tr>

\u00a0<\/th>
Capacity Threshold for the Ising Perceptron<\/em>
Authors: B. Huang<\/em><\/h5><\/th><\/tr>
\u00a0<\/th>
Optimal quantile estimation: beyond the comparison model<\/em>
Authors: M. Singhal, M. Gupta, H. Wu<\/em><\/h5><\/th><\/tr>

2:40 – 3:50pm<\/h4><\/td>

Knuth Prize Lecture<\/a>
<\/span><\/h3>

Rajeev Alur, University of Pennsylvania<\/h4>

Specification-guided Reinforcement Learning<\/a>\u00a0<\/p><\/th><\/tr>

3:55 – 4:15<\/h4><\/td>

Break<\/span><\/h3><\/th><\/tr>

4:15 – 5:30pm<\/h4><\/td>

Session 6A<\/span><\/h3>

(Session chair: He Jia)<\/p><\/td>

Session 6B<\/span><\/h3>

(Session chair: Chang Wang)<\/p><\/td>

Session 6C<\/span><\/h3>

(Session chair: Emanuele Viola)<\/p><\/td><\/tr>

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

Day 4: Wednesday, October 30, 2024<\/span><\/h1>

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

\u00a0<\/span><\/p><\/div><\/colgroup>

9:00 – 10:30am<\/h4><\/td>

Session 7A<\/span><\/h3>

(Session chair: Santosh Vempala)<\/p><\/td>

Session 7B<\/span><\/h3>

(Session chair: Yang Liu)<\/p><\/td>

Session 7C<\/span><\/h3>

(Session chair: Dionysios Arvanitakis)<\/p><\/td><\/tr>

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

10:30 – 10:50am<\/h4><\/td>

Break<\/span><\/h3><\/th><\/tr>

10:50 – 12:05pm<\/h4><\/td>

Session 8A<\/span><\/h3>

(Session chair: Xiaorui Sun)<\/p><\/td>

Session 8B<\/span><\/h3>

(Session chair: Idan Attias)<\/p><\/td>

Session 8C<\/span><\/h3>

(Session chair: Santosh Vempala)<\/p><\/td><\/tr>

\u00a0<\/td>

A stronger bound for linear 3-LCC<\/a>
Authors: T. Yankovitz<\/p>

and<\/em><\/p>

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Authors: P. Kothari, P. Manohar<\/p><\/td>

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

12:05 – 1:30pm<\/h4><\/td>

Conference Lunch<\/span><\/h3><\/th><\/tr>

1:30pm – 2:20pm<\/h4><\/td>

Session 9: Best Papers<\/span><\/h3>
(Session chair: Aravindan Vijayaraghavan)<\/h6><\/th><\/tr>

\u00a0<\/th>
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps<\/em>
Authors: B. Haeupler, R. Hlad\u00edk, V. Rozhon, R. Tarjan, J. T\u011btek<\/em><\/h5><\/th><\/tr>
\u00a0<\/th>
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS<\/em>
Authors: M. Ghaffari, C. Grunau<\/em><\/h5><\/th><\/tr>

2:20 – 2:45<\/h4><\/td>

Break<\/span><\/h3><\/th><\/tr>

2:45 – 4:15pm<\/h4><\/td>

Session 10A<\/span><\/h3>

(Session chair: He Jia)<\/p><\/td>

Session 10B<\/span><\/h3>

(Session chair: Vaidehi Srinivas)<\/p><\/td>

Session 10C<\/span><\/h3>

(Session chair: Santosh Vempala)<\/p><\/td><\/tr>

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

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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":304,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"footnotes":""},"class_list":["post-308","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/pages\/308","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/comments?post=308"}],"version-history":[{"count":0,"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/pages\/308\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/pages\/304"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2024\/wp-json\/wp\/v2\/media?parent=308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}