{"id":89,"date":"2025-01-31T19:43:37","date_gmt":"2025-01-31T19:43:37","guid":{"rendered":"https:\/\/focs.computer.org\/2025\/schedule\/"},"modified":"2025-12-18T03:29:15","modified_gmt":"2025-12-18T03:29:15","slug":"schedule","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2025\/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<\/h2>\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 AEDT (UTC +11). Additional (social) activities are or will be listed on the corresponding page<\/a>: fun runs, walks, etc. A mobile-friendly schedule site is available \ud83d\udd17 at this address<\/a><\/strong>.<\/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
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Day 1: Sunday, December 14, 2025<\/span><\/h1>

The planned events on Day 1 include Workshops and a Welcome Reception.\u00a0<\/span><\/p><\/colgroup>
\u00a0<\/td>

Workshop Session A
(Blackwattle 1)<\/span><\/h3><\/td>

Workshop Session B
(Blackwattle 2)<\/span><\/h3><\/td>

Workshop Session C
(Blackwattle 3)<\/span><\/h3><\/td><\/tr>

8:30\u20139:00<\/span><\/td>

Welcome tea and registration \u2615<\/span><\/h3><\/th><\/tr>

\u00a09:00\u201310:00<\/b><\/td>Breaking and Making Quantum Speedups<\/a>
<\/strong>(organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty)<\/td>
10:00\u201310:30<\/span><\/td>

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

\u00a010:30\u201312:00<\/b><\/td>Breaking and Making Quantum Speedups<\/a>
<\/strong>(organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty)<\/td>
12:00\u2013<\/b>1:30<\/span><\/td>

Lunch (provided) \ud83c\udf7d\ufe0f<\/span><\/h3><\/th><\/tr>

1:30\u20133:00<\/strong><\/td>Breaking and Making Quantum Speedups<\/a>
<\/strong>(organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty)<\/td>
3:00\u20133<\/b>:30<\/span><\/td>

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

\u00a03<\/strong>:30\u20134:30<\/b><\/td>Breaking and Making Quantum Speedups<\/a>
<\/strong>(organized by Siddhartha Jain, Seyoon Ragavan, Alexander Schmidhuber, and Noah Shutty)<\/td>
4:30\u20134:45<\/span><\/td>

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

4:45\u20135:30<\/b><\/span><\/td>

Graduating bits<\/span> \ud83c\udf93<\/h3><\/th><\/tr>

5:30\u20136:00<\/b><\/span><\/td>
Welcome to Country<\/span><\/a>
A Welcome to Country is a cultural practice performed by a Traditional Owner of the local region to welcome visitors to their Traditional Country.<\/em><\/h5><\/th><\/tr>
6:00\u2013<\/b>8:00<\/span><\/td>

Welcome Reception \ud83e\udd42<\/span><\/h3><\/th><\/tr><\/tbody><\/table>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\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, December 15, 2025<\/span><\/h1><\/colgroup>
\u00a09:00\u201310:30<\/b><\/td>

Session 1A
(Blackwattle 1)<\/span><\/h3>

Session chair: Yuval Rabani<\/em><\/p><\/td>

Session 1B
(Blackwattle 2)<\/span><\/h3>

Session chair: Josh Alman<\/em><\/p><\/td>

Session 1C
(Blackwattle 3)<\/span><\/h3>

Session chair: Robin Kothari<\/em><\/p><\/td><\/tr>

\u00a0<\/td>Online Edge Coloring: Sharp Thresholds
Authors:<\/i> J. Blikstad, O. Svensson, R. Vintan, D. Wajc<\/td>		Integer multiplication is at least as hard as matrix transposition
Authors:<\/i> D. Harvey, J. van der Hoeven<\/td>		Group Order is in QCMA
Authors:<\/i> F. Le Gall, H. Nishimura, D. Thakkar<\/td><\/tr>
\u00a0<\/td>Edge-weighted Matching in the Dark<\/a>
Authors:<\/i> Z. Huang, E. Sun, X. Wu, J. Zhao<\/td>		Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)<\/a>
Authors:<\/i> L. Wulf<\/td>		Exponential improvements to the average-case hardness of BosonSampling<\/a>
Authors:<\/i> A. Bouland, S. Datta, B. Fefferman, F. Hernandez<\/td><\/tr>
\u00a0<\/td>Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
Authors:<\/i> T. Kesselheim, M. Molinaro, K. Patton, S. Singla<\/td>		Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration<\/a>
Authors:<\/i> S. Hirahara, N. Ohsaka<\/td>		RE-completeness of entangled constraint satisfaction problems
Authors:<\/i> E. Culf, K. Mastel<\/td><\/tr>
\u00a0<\/td>Optimal 4-Approximation for the Correlated Pandora\u2019s Problem<\/a>
Authors:<\/i> N. Bansal, Z. Huang, Z. Zhu<\/td>		Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
Authors:<\/i> A. Larrauri<\/td>		Gap-preserving reductions and RE-completeness of Independent Set Games
Authors:<\/i> L. Man\u010dinska, P. Spaas, T. Spirig, M. Vernooij<\/td><\/tr>
\u00a0<\/td>A Little Clairvoyance Is All You Need<\/a>
Authors:<\/i> A. Gupta, H. Kaplan, A. Lindermayr, J. Schl\u00f6ter, S. Yingchareonthawornchai<\/td>		Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Authors:<\/i> V. Bhattiprolu, V. Guruswami, E. Lee, X. Ren<\/td>		Incompressibility and spectral gaps of random circuits
Authors:<\/i> C. Chen, J. Haah, J. Haferkamp, Y. Liu, T. Metger, X. Tan<\/td><\/tr>
10:30\u201310:50<\/span><\/td>

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

10:50\u201312:02<\/span><\/td>

Session 2A
(Blackwattle 1)<\/span><\/h3>

Session chair: Yang Liu<\/em><\/p><\/td>

Session 2B
(Blackwattle 2)<\/span><\/h3>

Session chair: Sepehr Assadi<\/em><\/p><\/td>

Session 2C
(Blackwattle 3)<\/span><\/h3>

Session chair: Ran Canetti<\/em><\/p><\/td><\/tr>

\u00a0<\/td>Weighted k-Path and Other Problems in Almost O*(2^k) Deterministic Time via Dynamic Representative Sets<\/a>
Author:<\/i> J. Nederlof<\/td>		Factorization Norms and an Inverse Theorem for MaxCut
Authors:<\/i> I. Balla, L. Hambardzumyan, I. Tomon<\/td>		The Sponge is Quantum Indifferentiable
Authors:<\/i> G. Alagic, J. Carolan, C. Majenz, S. Tokat<\/td><\/tr>
\u00a0<\/td>Improved 2-Approximate Shortest Paths for close vertex pairs
Author:<\/i> M. Gupta<\/td>		More efficient sifting for grid norms, and applications to multiparty communication complexity
Authors:<\/i> Z. Kelley, X. Lyu<\/td>		Parallel Repetition for Post-Quantum Arguments
Authors:<\/i> A. Huang, Y. Kalai<\/td><\/tr>
\u00a0<\/td>Paths and Intersections: Exact Emulators for Planar Graphs
Authors:<\/i> G. Li, Z. Tan, T. Zhang<\/td>		Sign-Rank of k-Hamming Distance is Constant
Authors:<\/i> M. G\u00f6\u00f6s, N. Harms, V. Imbach, D. Sokolov<\/td>		On the Impossibility of SNARGs with Short CRS (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting)<\/a>
Authors:<\/i> L. Chen, Z. Jin<\/td><\/tr>
\u00a0<\/td>Distance Approximating Minors for Planar and Minor-Free Graphs
Authors:<\/i> H. Chang, J. Conroy<\/td>		Direct Product Theorems for Randomized Query Complexity
Authors:<\/i> S. Ben-David, E. Blais<\/td>		On Succinct Obfuscation via Propositional Logic (or: How to use pv-IO)
Authors:<\/i> A. Jain, Z. Jin, S. Mathialagan, O. Paneth<\/td><\/tr>
12:02\u2013<\/b>1:30<\/span><\/td>

Lunch (provided) \ud83c\udf7d\ufe0f<\/span><\/h3><\/th><\/tr>

1:30\u20132:30<\/strong><\/td>

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

Shafi Goldwasser, MIT and Berkeley
“Recent Results In ML Safety using a Complexity\/Cryptography Perspective”<\/em><\/h4><\/th><\/tr>

2:30\u20133<\/b>:00<\/span><\/td>

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

3:00\u20134:12<\/strong><\/td>

Session 3A
(Blackwattle 1)<\/span><\/h3>

Session chair: Sepehr Assadi<\/span><\/em><\/p><\/td>

Session 3B
(Blackwattle 2)<\/span><\/h3>

Session chair: Michael A. Forbes<\/em><\/p><\/td>

Session 3C
(Blackwattle 3)<\/span><\/h3>

Session chair: Ronen Shaltiel<\/span><\/em><\/p><\/td><\/tr>

\u00a0<\/td>An Improved Greedy Approximation for (Metric) $k$-Means<\/a>
Authors:<\/i> M. Charikar, V. Cohen-Addad, R. Gao, F. Grandoni, E. Lee, E. van Wijland<\/td>		Deterministic factorization of constant-depth algebraic circuits in subexponential time<\/a>
Authors:<\/i> S. Bhattacharjee, M. Kumar, V. Ramanathan, R. Saptharishi, S. Saraf<\/td>		Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions
Authors:<\/i> R. Ilango, A. Lombardi<\/td><\/tr>
\u00a0<\/td>Stochastic Knapsack without Relaxing the Capacity
Authors:<\/i> A. De, S. Khanna, N. White<\/td>		Rank Bounds and PIT for $\\Sigma^3 \\Pi \\Sigma \\Pi^d$ circuits via a non-linear Edelstein-Kelly theorem
Authors:<\/i> A. Garg, R. Oliveira, A. Sengupta<\/td>		Solving Linear Inequalities over Convex Sets & its Applications to Cryptography and Hydrodynamics
Authors:<\/i> S. Basu, H. Khorasgani, H. Maji, H. Nguyen<\/td><\/tr>
\u00a0<\/td>Adaptivity Gaps for Stochastic Probing with Subadditive Functions<\/a>
Authors:<\/i> J. Li, Y. Liu, Y. Zhang<\/td>		Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
Authors:<\/i> J. Alman, B. Li<\/td>		Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions
Authors:<\/i> G. Lu, J. Silbak, D. Wichs<\/td><\/tr>
\u00a0<\/td>Stochastic scheduling with Bernoulli-type jobs through policy stratification
Authors:<\/i> A. Antoniadis, R. Hoeksma, K. Schewior, M. Uetz<\/td>		Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness
Authors:<\/i> V. Lysikov, M. Walter<\/td>		Succinct Homomorphic MACs from Groups and Applications
Authors:<\/i> Y. Ishai, H. Li, H. Lin<\/td><\/tr>
4:12\u20134:30<\/span><\/td>

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

4:30\u20135:24<\/b><\/span><\/td>

Session 4A
(Blackwattle 1)<\/span><\/h3>

Session chair: Yang Liu<\/em><\/p><\/td>

Session 4B
(Blackwattle 2)<\/span><\/h3>

Session chair: Sumegha Garg<\/span><\/em><\/p><\/td>

Session 4C
(Blackwattle 3)<\/span><\/h3>

Session chair: Robin Kothari<\/em><\/p><\/td><\/tr>

\u00a0<\/td>Faster Mixing of the Jerrum-Sinclair Chain
Authors:<\/i> X. Chen, W. Feng, Z. Ju, T. Miao, Y. Yin, X. Zhang<\/td>		Bipartite Matching is in Catalytic Logspace
Authors:<\/i> A. Agarwala, I. Mertz<\/td>		A distillation\u2013teleportation protocol for fault-tolerant QRAM<\/a>
Authors:<\/i> A. Dalzell, C. Hann, A. Gily\u00e9n, S. McArdle, G. Salton, Q. Nguyen, A. Kubica, F. Brandao<\/td><\/tr>
\u00a0<\/td>Rapid Mixing on Random Regular Graphs beyond Uniqueness
Authors:<\/i> X. Chen, Z. Chen, Z. Chen, Y. Yin, X. Zhang<\/td>		Collapsing Catalytic Classes
Authors:<\/i> M. Koucky, I. Mertz, E. Pyne, S. Sami<\/td>		Adversarially robust quantum state learning and testing<\/a>
Authors:<\/i> M. Aliakbarpour, V. Braverman, N. Chia, Y. Liu<\/td><\/tr>
\u00a0<\/td>Deterministic counting from coupling independence
Authors:<\/i> X. Chen, W. Feng, H. Guo, X. Zhang, Z. Zou<\/td>		Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations<\/a>
Authors:<\/i> M. Naor, B. Menuhin<\/td>		Learning quantum Gibbs states locally and efficiently
Authors:<\/i> C. Chen, A. Anshu, Q. Nguyen<\/td><\/tr>
5:24\u20136:00<\/span><\/td>

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

6:00\u2013<\/b>7:30<\/span><\/td>

Business meeting \ud83d\udcca<\/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<\/a>\n\t\t
\n\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, December 16, 2025<\/span><\/h1><\/colgroup>
\u00a09:00\u201310:30<\/b><\/td>

Session 5A
(Blackwattle 1)<\/span><\/h3>

Session chair: Sanjeev Khanna<\/em><\/p><\/td>

Session 5B
(Blackwattle 2)<\/span><\/h3>

Session chair: Madhur Tulsiani<\/em><\/p><\/td>

Session 5C
(Blackwattle 3)<\/span><\/h3>

Session chair: Xi Chen<\/em><\/p><\/td><\/tr>

\u00a0<\/td>

Near-Optimal Fault-Tolerant Strong Connectivity Preservers<\/p>

Authors:<\/i> G. Hoppenworth, T. Saranurak, B. Wang<\/p><\/td>

Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent<\/p>

Authors:<\/i> M. Levi, J. Mosheiff, N. Shagrithaya<\/p><\/td>

An Improved Bound for the Beck-Fiala Conjecture
Authors:<\/i> N. Bansal, H. Jiang<\/td><\/tr>
\u00a0<\/td>

Deterministic Almost-Linear-Time Gomory-Hu Trees<\/p>

Authors:<\/i> A. Abboud, R. Kyng, J. Li, D. Panigrahi, M. Probst, T. Saranurak, W. Yuan, W. Yuan<\/p><\/td>

Maximally Extendable Product Codes are Good Coboundary Expanders<\/p>

Authors:<\/i> G. Kalachev, P. Panteleev<\/p><\/td>

A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
Authors:<\/i> R. Bourneuf, P. Charbit, S. Thomasse<\/td><\/tr>
\u00a0<\/td>

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs<\/p>

Authors:<\/i> A. Bernstein, J. Blikstad, J. Li, T. Saranurak, T. Tu<\/p><\/td>

Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks<\/p>

Authors:<\/i> L. Golowich, V. Guruswami<\/p><\/td>

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Authors:<\/i> B. Bedert, T. Nakajima, K. Okrasa, S. Zivny<\/td><\/tr>
\u00a0<\/td>

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs<\/p>

Authors:<\/i> S. Jiang, M. Kapralov, L. Er Lu, A. Sidford<\/p><\/td>

A k^{q\/q-2} Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs<\/p>

Authors:<\/i> O. Janzer, P. Manohar<\/p><\/td>

Cycle-factors of regular graphs via entropy
Authors:<\/i> E. Hurley, A. Girao, L. Michel, N. Draganic, A. M\u00fcyesser, M. Christoph<\/td><\/tr>
\u00a0<\/td>

Almost Tight Additive Guarantees for $k$-Edge-Connectivity<\/p>

Authors:<\/i> N. Kumar, C. Swamy<\/p><\/td>

Improved Lower Bounds for all Odd-Query Locally Decodable Codes<\/p>

Authors:<\/i> A. Basu, J. Hsieh, P. Kothari, A. Lin<\/p><\/td>

Polynomial Bounds for the Graph Minor Structure Theorem
Authors:<\/i> M. Gorsky, M. Seweryn, S. Wiederrecht<\/td><\/tr>
10:30\u201310:50<\/span><\/td>

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

10:50\u201312:02<\/span><\/td>

Session 6A
(Blackwattle 1)<\/span><\/h3>

Session chair: Michael Kapralov<\/em><\/p><\/td>

Session 6B
(Blackwattle 2)<\/span><\/h3>

Session chair: Pravesh Kothari<\/em><\/p><\/td>

Session 6C
(Blackwattle 3)<\/span><\/h3>

Session chair: Kevin Tian<\/span><\/em><\/p><\/td><\/tr>

\u00a0<\/td>

The Power of Recursive Embeddings for $\\ell_p$ Metrics<\/a><\/p>

Authors:<\/i> R. Krauthgamer, N. Petruschka, S. Sapir<\/p><\/td>

Undirected Multicast Network Coding Gaps via Locally Decodable Codes<\/p>

Authors:<\/i> Z. He, M. Braverman<\/p><\/td>

How Global Calibration Strengthens Multiaccuracy<\/a>
Authors:<\/i> S. Casacuberta, P. Gopalan, V. Kanade, O. Reingold<\/td><\/tr>
\u00a0<\/td>

Embeddings into Similarity Measures for Nearest Neighbor Search<\/p>

Authors:<\/i> A. Andoni, N. Nosatzki<\/p><\/td>

Constant Rate Codes for Adaptive Broadcasts Do Not Exist<\/p>

Authors:<\/i> K. Efremenko, G. Kol, D. Paramonov, R. Saxena<\/p><\/td>

High dimensional online calibration in polynomial time
Authors:<\/i> B. Peng<\/td><\/tr>
\u00a0<\/td>

Average-Distortion Sketching<\/p>

Authors:<\/i> Y. Bao, A. Baweja, N. Menand, E. Waingarten, N. White, T. Zhang<\/p><\/td>

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time<\/p>

Authors:<\/i> S. Srivastava, M. Tulsiani<\/p><\/td>

Near-Optimal Algorithms for Omniprediction
Authors:<\/i> P. Okoroafor, B. Kleinberg, M. Kim<\/td><\/tr>
\u00a0<\/td>

Query-Efficient Fixpoints of $\\ell_p$-Contractions<\/p>

Authors:<\/i> S. Haslebacher, J. Lill, P. Schnider, S. Weber<\/p><\/td>

Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes<\/p>

Authors:<\/i> S. Garg, A. Sengupta<\/p><\/td>

Density Measures for Language Generation
Authors:<\/i> J. Kleinberg, F. Wei<\/td><\/tr>
12:02\u2013<\/b>1:30<\/span><\/td>

Lunch (provided) \ud83c\udf7d\ufe0f<\/span><\/h3><\/th><\/tr>

1:30\u20132:30<\/strong><\/td>

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

Sebastien Bubeck, OpenAI (remote)
“Recent advances in LLMs for Mathematics”<\/em><\/h4><\/th><\/tr>

2:30\u20133<\/b>:10<\/span><\/td>

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

3:10\u20134:22<\/strong><\/td>

Session 7A
(Blackwattle 1)<\/span><\/h3>

Session chair: Robert Krauthgamer<\/span><\/em><\/p><\/td>

Session 7B
(Blackwattle 2)<\/span><\/h3>

Session chair: Sumegha Garg<\/em><\/p><\/td>

Session 7C
(Blackwattle 3)<\/span><\/h3>

Session chair: Rocco Servedio<\/em><\/p><\/td><\/tr>

\u00a0<\/td>

Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair<\/p>

Authors:<\/i> L. Beretta, V. Cohen-Addad, R. Jayaram, E. Waingarten<\/p><\/td>

Fingerprint Filters are Optimal<\/p>

Authors:<\/i> W. Kuszmaul, J. Liang, R. Zhou<\/p><\/td>

Overcomplete Tensor Decomposition via Koszul-Young Flattenings<\/a>
Authors:<\/i> P. Kothari, A. Moitra, A. Wein<\/td><\/tr>
\u00a0<\/td>

Root Ridge Leverage Score Sampling for $\\ell_p$ Subspace Approximation<\/p>

Authors:<\/i> D. Woodruff, T. Yasuda<\/p><\/td>

Static Retrieval Revisited: To Optimality and Beyond<\/p>

Authors:<\/i> Y. Hu, W. Kuszmaul, J. Liang, H. Yu, J. Zhang, R. Zhou<\/p><\/td>

Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
Authors:<\/i> I. Diakonikolas, D. Kane<\/td><\/tr>
\u00a0<\/td>

Perfect L_p Sampling with Polylogarithmic Update Time<\/p>

Authors:<\/i> W. Swartworth, D. Woodruff, S. Zhou<\/p><\/td>

Stronger Cell Probe Lower Bounds via Local PRGs<\/p>

Authors:<\/i> O. Korten, T. Pitassi, R. Impagliazzo<\/p><\/td>

Robust Learning of Multi-index Models via Iterative Subspace Approximation<\/a>
Authors:<\/i> I. Diakonikolas, G. Iakovidis, D. Kane, N. Zarifis<\/td><\/tr>
\u00a0<\/td>

\u21132\/\u21132 Sparse Recovery via Weighted Hypergraph Peeling<\/p>

Authors:<\/i> N. Fischer, V. Nakos<\/p><\/td>

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
Authors:<\/i> D. Das, J. Gilbert, T. Kociumaka, M. Hajiaghayi, B. Saha<\/p><\/td>

Solving Zero-Sum Games with Fewer Matrix-Vector Products
Authors:<\/i> I. Karmarkar, L. O’Carroll, A. Sidford<\/td><\/tr>
4:22\u20134:40<\/span><\/td>

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

4:40\u20135:34<\/b><\/span><\/td>

Session 8A
(Blackwattle 1)<\/span><\/h3>

Session chair: Thatchaphol Saranurak<\/em><\/p><\/td>

Session 8B
(Blackwattle 2)<\/span><\/h3>

Session chair: Salil Vadhan<\/em><\/p><\/td>

Session 8C
(Blackwattle 3)<\/span><\/h3>

Session chair: David Woodruff<\/em><\/p><\/td><\/tr>

\u00a0<\/td>

Fast Algorithms for Graph Arboricity and Related Problems<\/p>

Authors:<\/i> R. Cen, H. Fleischmann, G. Li, J. Li, D. Panigrahi<\/p><\/td>

Ramanujan bigraphs and applications<\/p>

Authors:<\/i> S. Evra, B. Feigon, O. Parzanchevski, K. Maurischat<\/p><\/td>

Faster exact learning of k-term DNFs with membership and equivalence queries
Authors:<\/i> J. Alman, S. Nadimpalli, S. Patel, R. Servedio<\/td><\/tr>
\u00a0<\/td>

Dynamic Treewidth in Logarithmic Time<\/a><\/p>

Author:<\/i> T. Korhonen<\/p><\/td>

Extractors for Samplable Distributions with Polynomially Small Min-Entropy<\/p>

Authors:<\/i> R. Shaltiel<\/p><\/td>

Computational-Statistical Tradeoffs from NP-hardness<\/a>
Authors:<\/i> G. Blanc, C. Koch, C. Strassle, L. Tan<\/td><\/tr>
\u00a0<\/td>

Random-Shift Revisited: Tight Approximations for Tree Embeddings and \u21131-Oblivious Routings<\/p>

Authors:<\/i> M. Probst, R. Kyng, T. Rieder<\/p><\/td>

Finding Colorings in One-Sided Expanders<\/p>

Authors:<\/i> R. Buhai, Y. Hua, D. Steurer, A. V\u00e1ri-Kakas<\/p><\/td>

Theoretical limitations of multi-layer Transformer
Authors:<\/i> L. Chen, B. Peng, H. Wu<\/td><\/tr>
5:24\u20136:00<\/span><\/td>

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

6:00\u2013<\/b>9:00<\/span><\/td>

Banquet @ Squire Landing<\/a> \ud83c\udf74\ud83c\udf77<\/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<\/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

Day 4: Wednesday, December 17, 2025<\/span><\/h1><\/colgroup>
\u00a09:00\u201310:30<\/b><\/td>

Session 9A
(Blackwattle 1)<\/span><\/h3>

Session chair: Artur Czumaj<\/em><\/p><\/td>

Session 9B
(Blackwattle 2)<\/span><\/h3>

Session chair:\u00a0Michal Kouck\u00fd<\/em><\/p><\/td>

Session 9C
(Blackwattle 3)<\/span><\/h3>

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

\u00a0<\/td>Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
Authors:<\/i> M. Ghaffari, C. Grunau<\/td>		On Inverse Theorems and Combinatorial Lines
Authors:<\/i> A. Bhangale, S. Khot, Y. Liu, D. Minzer<\/td>		Characterization of Priority-Neutral Matching Lattices
Authors:<\/i> C. Thomas<\/td><\/tr>
\u00a0<\/td>Parallel $(1+\\epsilon)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Authors:<\/i> B. Haeupler, Y. Jiang, Y. Long, T. Saranurak, S. Wang<\/td>		NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions
Authors:<\/i> S. Hirahara, R. Ilango<\/td>		Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness
Authors:<\/i> X. Bu, B. Tao<\/td><\/tr>
\u00a0<\/td>On the Parallel Complexity of Finding a Matroid Basis
Authors:<\/i> S. Khanna, A. Putterman, J. Song<\/td>		The Proof Analysis Problem<\/a>
Authors:<\/i> N. Arteche, A. Atserias, S. de Rezende, E. Khaniki<\/td>		Beyond Regularity: Simple versus Optimal Mechanisms, Revisited
Authors:<\/i> Y. Feng, Y. Jin<\/td><\/tr>
\u00a0<\/td>Constant Approximation of Arboricity in Near-Optimal Sublinear Time
Authors:<\/i> J. Dai, M. Ghaffari, J. Portmann<\/td>		High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich<\/a>
Authors:<\/i> R. Gao, A. Hollender, A. Rubinstein<\/td>		Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
Authors:<\/i> R. Bowers, M. Garbea, E. Pountourakis, S. Taggart<\/td><\/tr>
\u00a0<\/td>Lower Bounds for Non-adaptive Local Computation Algorithms<\/a>
Authors:<\/i> A. Azarmehr, S. Behnezhad, A. Ghafari, M. Sudan<\/td>		Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
Authors:<\/i> J. Leake, K. Lindberg, S. Gharan<\/td>		Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade<\/a>
Authors:<\/i> S. Di Gregorio, P. Duetting, F. Fusco, C. Schwiegelshohn<\/td><\/tr>
10:30\u201310:50<\/span><\/td>

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

10:50\u201312:02<\/span><\/td>

Session 10A
(Blackwattle 1)<\/span><\/h3>

Session chair: Aaron Sidford <\/em><\/p><\/td>

Session 10B
(Blackwattle 2)<\/span><\/h3>

Session chair: Cl\u00e9ment Canonne<\/em><\/p><\/td>

Session 10C
(Blackwattle 3)<\/span><\/h3>

Session chair: Michael A. Forbes<\/em><\/p><\/td><\/tr>

\u00a0<\/td>Radial Isotropic Position via an Implicit Newton’s Method
Authors:<\/i> A. Jambulapati, J. Li, K. Tian<\/td>		Distributed Triangle Detection is Hard in Few Rounds<\/a>
Authors:<\/i> S. Assadi, J. Sundaresan<\/td>		On optimal distinguishers for Planted Clique
Authors:<\/i> A. Nagda, P. Raghavendra<\/td><\/tr>
\u00a0<\/td>Faster logconcave sampling from a cold start in high dimension<\/a>
Authors:<\/i> Y. Kook, S. Vempala<\/td>		Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching<\/a>
Authors:<\/i> S. Khoury, A. Schild<\/td>		Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
Authors:<\/i> M. Sellke<\/td><\/tr>
\u00a0<\/td>Optimal Smoothed Analysis of the Simplex Method<\/a>
Authors:<\/i> E. Bach, S. Huiberts<\/td>		Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
Authors:<\/i> Y. Fei, D. Minzer, S. Wang<\/td>		The Quasi-Polynomial Low-Degree Conjecture is False
Authors:<\/i> R. Buhai, J. Hsieh, A. Jain, P. Kothari<\/td><\/tr>
\u00a0<\/td>Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics<\/a>
Authors:<\/i> H. An, M. Kao, C. Lee, M. Lee<\/td>		A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams<\/a>
Authors:<\/i> S. Khanna, A. Padaki, K. Singal, E. Waingarten<\/td>		PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Authors:<\/i> I. Diakonikolas, D. Kane, S. Liu, T. Pittas<\/td><\/tr>
12:02\u2013<\/b>1:30<\/span><\/td>

Lunch (provided) \ud83c\udf7d\ufe0f<\/span><\/h3><\/th><\/tr>

1:30\u20132:24<\/strong><\/td>

Session 11A
(Blackwattle 1)<\/span><\/h3>

Session chair: Eric Blais<\/em><\/p><\/td>

Session 11B
(Blackwattle 2)<\/span><\/h3>

Session chair: Troy Lee<\/em><\/p><\/td>

Session 11C
(Blackwattle 3)<\/span><\/h3>

Session chair: Bernhard Haeupler<\/span><\/em><\/p><\/td><\/tr>

\u00a0<\/td>Near-Optimal Property Testers for Pattern Matching
Authors:<\/i> C. Jin, T. Kociumaka<\/td>		Efficiently Batching Unambiguous Interactive Proofs<\/a>
Authors:<\/i> B. Berger, R. Goyal, M. Hong, Y. Kalai<\/td>		Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
Authors:<\/i> T. Chan, H. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D. Zheng<\/td><\/tr>
\u00a0<\/td>Tight Pair Query Lower Bounds for Matching and Earth Mover’s Distance
Authors:<\/i> A. Azarmehr, S. Behnezhad, M. Roghani, A. Rubinstein<\/td>		Improved Round-by-round Soundness IOPs via Reed-Muller Codes
Authors:<\/i> D. Minzer, K. Zheng<\/td>		Shortest Paths on Convex Polyhedral Surfaces<\/a>
Authors:<\/i> H. Wang<\/td><\/tr>
\u00a0<\/td>Instance-Optimal Uniformity Testing and Tracking<\/a>
Authors:<\/i> G. Blanc, C. Canonne, E. Waingarten<\/td>		Proving Natural Distribution Properties is Harder than Testing Them
Authors:<\/i> T. Herman, G. Rothblum<\/td>

Pattern Matching under Weighted Edit Distance<\/p>

Authors:<\/i> P. Charalampopoulos, T. Kociumaka, P. Wellnitz<\/p><\/td><\/tr>

2:24\u20132:55<\/span><\/td>

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

2:55\u20134:25<\/span><\/td>

\ud83c\udfc6 Session 12<\/span><\/h3>

Session chair: Rotem Oshman<\/span><\/em><\/p><\/th><\/tr>

\u00a0<\/td>Godel in Cryptography: Effectively Zero Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness
Author:<\/i> R. Ilango<\/td><\/tr>
\u00a0<\/td>Obfuscation of Unitary Quantum Programs
Authors:<\/i> M-Y. Huang, E-C. Tang<\/td><\/tr>
\u00a0<\/td>Explicit Lossless Vertex Expanders
Authors:<\/i> J-T. Hsieh, A. Lubotzky, S. Mohanty, A. Reiner, R. Y. Zhang<\/td><\/tr>
4:25\u20134:50<\/span><\/td>

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

4:50\u20135:50<\/span><\/td>

\ud83c\udfc6 Session 13<\/span><\/h3>

Session chair: Ran Raz<\/span><\/em><\/p><\/th><\/tr>

\u00a0<\/td>Quasipolynomial bounds for the corners theorem<\/a>
Authors:<\/i> M. Jaber, Y. P. Liu, S. Lovett, A. Ostuni, M. Sawhney<\/td><\/tr>
\u00a0<\/td>Breaking a Long-Standing Barrier: 2-\u03b5 Approximation for Steiner Forest<\/a>
Authors:<\/i> A. Ahmadi, I. Gholami, M. Hajiaghayi, P. Jabbarzade, M. Mahdavi<\/td><\/tr><\/tbody><\/table>\t\t\t\t\t\t\t\t<\/div>\n\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 AEDT (UTC +11). Additional (social) activities are or will be listed on the corresponding page: fun runs, walks, etc. A mobile-friendly schedule site is available \ud83d\udd17 at this address. Day 1 Day 2 Day 3 Day 4 Day 1: Sunday, December 14, 2025 The planned events on Day […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"footnotes":""},"class_list":["post-89","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages\/89","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/comments?post=89"}],"version-history":[{"count":0,"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/pages\/89\/revisions"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2025\/wp-json\/wp\/v2\/media?parent=89"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}