{"id":1854,"date":"2026-10-14T19:17:02","date_gmt":"2026-10-14T19:17:02","guid":{"rendered":"https:\/\/focs.computer.org\/2026\/?page_id=1854"},"modified":"2026-10-15T00:41:54","modified_gmt":"2026-10-15T00:41:54","slug":"main-program","status":"publish","type":"page","link":"https:\/\/focs.computer.org\/2026\/main-program\/","title":{"rendered":"Main Program"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"1854\" class=\"elementor elementor-1854\" data-elementor-post-type=\"page\">\n\t\t\t\t<div data-particle_enable=\"false\" data-particle-mobile-disabled=\"false\" class=\"elementor-element elementor-element-610ca7c e-flex e-con-boxed e-con e-parent\" data-id=\"610ca7c\" data-element_type=\"container\" data-e-type=\"container\">\n\t\t\t\t\t<div class=\"e-con-inner\">\n\t\t\t\t<div class=\"elementor-element elementor-element-0f5be61 elementor-widget elementor-widget-wp-widget-custom_html\" data-id=\"0f5be61\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"wp-widget-custom_html.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"textwidget custom-html-widget\"><div id=\"focs-program\" class=\"wrap\">\r\n<header class=\"mast\"><p class=\"eyebrow\">67th IEEE Symposium on Foundations of Computer Science<\/p><h1>FOCS 2026 Program<\/h1><\/header><nav class=\"program-nav\" aria-label=\"Program days\">\r\n<a href=\"#sunday\">Sunday \u00b7 Nov 8<\/a><a href=\"#monday\">Monday \u00b7 Nov 9<\/a><a href=\"#tuesday\">Tuesday \u00b7 Nov 10<\/a><a href=\"#wednesday\">Wednesday \u00b7 Nov 11<\/a>\r\n<\/nav><div class=\"program-links\"><a class=\"pdf-link\" href=\"https:\/\/focs.computer.org\/2026\/wp-content\/uploads\/sites\/5\/2026\/10\/FOCS-2026-program.pdf\" download>Paper program (PDF)<\/a><a href=\"https:\/\/focs.computer.org\/2026\/workshop-program\/\">Workshop program<\/a><\/div>\r\n<section id=\"sunday-program\" aria-labelledby=\"sunday\">\r\n<h2 id=\"sunday\" class=\"workday\">Sunday, November 8, 2026<\/h2>\r\n<p class=\"workshop-intro\">Workshops and Jane Street Estimathon<\/p>\r\n<p class=\"workshop-venue\"><strong>Workshop Tracks 1\u20133:<\/strong> Warren Weaver Hall, 251 Mercer Street.<\/p>\r\n<div class=\"workshop-row\"><div class=\"workshop-time\">8:30\u20139:00 a.m.<\/div>\r\n<div class=\"workshop-break\">Breakfast<\/div>\r\n<\/div>\r\n<div class=\"workshop-row\"><div class=\"workshop-time\">9:00\u201311:30 a.m.<\/div>\r\n<div class=\"workshop-grid\">\r\n<article class=\"workshop-card track-1\">\r\n<h3><span class=\"workshop-track\">Track 1 \u00b7 WWH 109<\/span>Subspace Designs: A Universal Tool for Derandomization, Part 1<\/h3>\r\n<p>Organizers: Venkatesan Guruswami, Rohan Goyal, Joshua Brakensiek<\/p>\r\n<\/article>\r\n<article class=\"workshop-card track-2\">\r\n<h3><span class=\"workshop-track\">Track 2 \u00b7 WWH 101<\/span>Validating Quantum Devices: From Practice to Theory<\/h3>\r\n<p>Organizers: Andrea Coladangelo, Joseph Slote, Jerry Li<\/p>\r\n<\/article>\r\n<article class=\"workshop-card track-3\">\r\n<h3><span class=\"workshop-track\">Track 3 \u00b7 WWH 102<\/span>Performative Prediction<\/h3>\r\n<p>Organizer: Juan C. Perdomo<\/p>\r\n<p><a href=\"https:\/\/jcperdomo.org\/workshops\/focs2026\/\">Workshop website<span class=\"screen-reader-text\">: Performative Prediction<\/span><\/a><\/p>\r\n<\/article>\r\n<\/div>\r\n<\/div>\r\n<div class=\"workshop-row\"><div class=\"workshop-time\">11:30 a.m.\u201312:30 p.m.<\/div>\r\n<div class=\"workshop-break\">Lunch<\/div>\r\n<\/div>\r\n<div class=\"workshop-row\"><div class=\"workshop-time\">12:30\u20133:00 p.m.<\/div>\r\n<div class=\"workshop-grid\">\r\n<article class=\"workshop-card track-1\">\r\n<h3><span class=\"workshop-track\">Track 1 \u00b7 WWH 109<\/span>Subspace Designs: A Universal Tool for Derandomization, Part 2<\/h3>\r\n<p>Organizers: Venkatesan Guruswami, Rohan Goyal, Joshua Brakensiek<\/p>\r\n<\/article>\r\n<article class=\"workshop-card track-2\">\r\n<h3><span class=\"workshop-track\">Track 2 \u00b7 WWH 101<\/span>TCS Problems in Quantum Architecture and Compilation<\/h3>\r\n<p>Organizers: Zhiyang He, Robert Huang, Siddhartha Jain, Robin Kothari, Esha Swaroop<\/p>\r\n<p><a href=\"https:\/\/sidjain.me\/workshop\/\">Workshop website<span class=\"screen-reader-text\">: TCS Problems in Quantum Architecture and Compilation<\/span><\/a><\/p>\r\n<\/article>\r\n<article class=\"workshop-card track-3\">\r\n<h3><span class=\"workshop-track\">Track 3 \u00b7 WWH 102<\/span>Algorithmic Perspectives on Quasirandomness<\/h3>\r\n<p>Organizers: Cassandra Marcussen, Ted Pyne, Ronitt Rubinfeld, Asaf Shapira<\/p>\r\n<p><a href=\"https:\/\/quasirandomness-focs2026.github.io\/\">Workshop website<span class=\"screen-reader-text\">: Algorithmic Perspectives on Quasirandomness<\/span><\/a><\/p>\r\n<\/article>\r\n<\/div>\r\n<\/div>\r\n<div class=\"workshop-row\"><div class=\"workshop-time\">3:00\u20133:30 p.m.<\/div>\r\n<div class=\"workshop-break\">Coffee break<\/div>\r\n<\/div>\r\n<div class=\"workshop-row\"><div class=\"workshop-time\">3:30\u20135:30 p.m.<\/div>\r\n<article class=\"workshop-card workshop-joint\"><h3>AI and TCS Workshop<span class=\"heading-room\" data-heading-room=\"joint-workshop\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/h3><p>Joint session for all attendees<\/p><p>Organizer: Aaron Roth<\/p><p><strong>Kimmel Center<\/strong><br>60 Washington Square South<\/p><\/article>\r\n<\/div>\r\n<div class=\"workshop-row\"><div class=\"workshop-time\">6:00\u20137:30 p.m. ET<\/div><article class=\"workshop-card workshop-estimathon\"><h3><a href=\"https:\/\/focs.computer.org\/2026\/jane-street-estimathon\/\">Jane Street Estimathon<\/a><span class=\"heading-room\" data-heading-room=\"estimathon\"> - NYU Kimmel Center, Room 802 (Shorin)<\/span><\/h3><p>All conference participants are welcome. Signup is optional; sign up individually and teams will be formed onsite.<\/p><div class=\"workshop-actions\"><a href=\"https:\/\/focs.computer.org\/2026\/jane-street-estimathon\/\">Event details and flyer<\/a><a href=\"https:\/\/forms.gle\/qfsF3t7z9LdB8Ugn7\">Sign up (optional)<\/a><\/div><\/article><\/div>\r\n<\/section>\r\n<h2 class=\"paper-section-title\">Paper sessions \u00b7 November 9\u201311<\/h2><p class=\"paper-venue\" data-heading-room=\"paper-venue\">Kimmel Center<\/p>\r\n<dl class=\"facts\"><div class=\"fact\"><dt>Lunch<\/dt><dd>from 12:50<\/dd><\/div><\/dl>\r\n<div class=\"legend\"><span><i style=\"background:var(--tA)\"><\/i>Track A<span class=\"legend-room\" data-room-note=\"legend-A\"> \u00b7 Eisner &amp; Lubin Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span><span><i style=\"background:var(--tB)\"><\/i>Track B<span class=\"legend-room\" data-room-note=\"legend-B\"> \u00b7 Rooms 405\/406<\/span><\/span><span><i style=\"background:var(--tC)\"><\/i>Track C<span class=\"legend-room\" data-room-note=\"legend-C\"> \u00b7 Rooms 905\/907<\/span><\/span><span><i style=\"background:var(--tD)\"><\/i>Track D &mdash; Monday only<span class=\"legend-room\" data-room-note=\"legend-D\"> \u00b7 Room 914<\/span><\/span><span><i style=\"background:var(--award)\"><\/i>Plenary \/ award<\/span><\/div>\r\n<h2 id=\"monday\" class=\"day\">Monday, November 9<\/h2><div class=\"dayrule\"><span class=\"daymeta\">4 parallel tracks<\/span><\/div>\r\n<div class=\"row\"><div class=\"time\">9:00 \u2013 9:30 am<\/div><div class=\"evt\"><span class=\"lbl\">Breakfast \/ Registration<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 1<\/b>9:30 \u2013 11:00 am<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(4,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">1A<span class=\"heading-room\" data-heading-room=\"paper-1A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Flows, Connectivity and Matchings<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time<\/div><div class=\"a\">Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh (ETH Zurich)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth<\/div><div class=\"a\">Yonggang Jiang (MPIINF); Changki Yun (Seoul National University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Connectivity augmentation is fixed-parameter tractable<\/div><div class=\"a\">Tuukka Korhonen, Mikkel Thorup (University of Copenhagen)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs<\/div><div class=\"a\">Bernhard Haeupler (INSAIT, Sofia University &quot;St. Kliment Ohridski&quot; and ETH Zurich); Yonggang Jiang (MPIINF); Thatchaphol Saranurak (University of Michigan)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> A Shortest Augmenting Path Algorithm for Linear Matroid Parity<\/div><div class=\"a\">Kou Hamada, Satoru Iwata (University of Tokyo)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">1B<span class=\"heading-room\" data-heading-room=\"paper-1B\"> - Rooms 405\/406<\/span><\/span>Quantum Tomography and Hamiltonian Learning<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Mixed state tomography reduces to pure state tomography<\/div><div class=\"a\">Angelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> Nearly Time-Optimal Pure State Tomography with Pauli Measurements<\/div><div class=\"a\">Sabee Grewal (UT Austin); Meghal Gupta (UC Berkeley); William He (Carnegie Mellon University); Aniruddha Sen (UT Austin); Mihir Singhal (UC Berkeley)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition<\/div><div class=\"a\">Kean Chen (University of Pennsylvania); Filippo Girardi (Scuola Normale Superiore); Aadil Oufkir (University Mohammed VI Polytechnic); Nengkun Yu (Stony Brook University); Zhicheng Zhang (Griffith University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> The Keyl--Werner algorithm is not optimal for spectrum estimation<\/div><div class=\"a\">Angelos Pelecanos, Jack Spilecki, Ewin Tang (UC Berkeley); John Wright (The University of California, Berkeley)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> Lower Bounds for Learning Hamiltonians from Time Evolution<\/div><div class=\"a\">Ziyun Chen, Jerry Li, Joe Slote (University of Washington)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">1C<span class=\"heading-room\" data-heading-room=\"paper-1C\"> - Rooms 905\/907<\/span><\/span>Cryptography<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Doubly-Efficient Interactive Arguments for Bounded-Space from One-Way Functions<\/div><div class=\"a\">Guy Rothblum (Apple)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> Lower Bounds for PIR with Preprocessing from Blackbox Cryptography<\/div><div class=\"a\">Alexander Hoover (Stevens Institute of Technology); Giuseppe Persiano (Universit\u00e0 di Salerno); Kevin Yeo (Google)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> On the Hardness of LWE with Trapdoor Hints and Applications to Fuzzy Cryptography<\/div><div class=\"a\">Divesh Aggarwal (National University of Singapore); Aayush Jain (CMU); Huijia (Rachel) Lin (University of Washington); Yuetian Wu (Peking University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> Overcoming Padding in Cryptography via the Hardness of Certifying Random Strings<\/div><div class=\"a\">Yao-Ching Hsieh (University of Washington); Abhishek Jain (NTT Research and Johns Hopkins); Jiatu Li (Massachusetts Institute of Technology); Surya Mathialagan (NTT Research)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> Undetectable Conversations Between AI Agents via Pseudorandom Noise-Resilient Key Exchange<\/div><div class=\"a\">Vinod Vaikuntanathan (MIT CSAIL); Or Zamir (Tel Aviv University)<\/div>\r\n<\/div>\r\n<div class=\"sess D\"><h3><span class=\"code\">1D<span class=\"heading-room\" data-heading-room=\"paper-1D\"> - Room 914<\/span><\/span>Clustering and Coresets<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> A Constant Approximation for Non-Uniform k-Center<\/div><div class=\"a\">Tanmay Inamdar (Indian Institute of Technology Jodhpur); William Lochet (CNRS, LIRMM); Fahad Panolan (School of Computer Science, University of Leeds)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> FPT Approximation Schemes for Min-Sum Radii and Min-Sum Diameters<\/div><div class=\"a\">Fabrizio Grandoni (IDSIA, USI-SUPSI); Anupam Gupta (New York University, USA); Jatin Yadav (Indian Institute Of Technology, Delhi)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Fully Dynamic Euclidean k-Means<\/div><div class=\"a\">Sayan Bhattacharya (University of Warwick, UK); Martin Costa, Ermiya Farokhnejad (University of Warwick); Shaofeng Jiang (Peking University); Yaonan Jin (Huawei); Jianing Lou (Peking University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> k-Clustering via Iterative Randomized Rounding<\/div><div class=\"a\">Jaros\u0142aw Byrka (University of Wroc\u0142aw); Yuhao Guo, Yang Hu (Tsinghua University); Shi Li (Nanjing University); Chengzhang Wan (Tsinghua University); Zaixuan Wang (Nanjing University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> A Polynomial Coreset for Furthest Neighbor in Planar Metrics<\/div><div class=\"a\">Kacper Kluk (University of Warsaw); Hung Le (University of Massachusetts, Amherst, USA); Wojciech Nadara, Marcin Pilipczuk (University of Warsaw); Hector Tierno, Vinayak Vinayak (University of Massachusetts, Amherst)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">11:00 \u2013 11:20 am<\/div><div class=\"evt\"><span class=\"lbl\">Coffee Break (20 min)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 2<\/b>11:20 am \u2013 12:50 pm<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(4,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">2A<span class=\"heading-room\" data-heading-room=\"paper-2A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Shortest Paths and Distances<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> Almost Optimal Multiple Source Shortest Paths and Reachability<\/div><div class=\"a\">Barna Saha, Yinzhan Xu, Christopher Ye (University of California, San Diego)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> Bellman-Ford in Almost-Linear Time for Dense Graphs<\/div><div class=\"a\">George Li (Carnegie Mellon University); Jason Li (CMU); Junkai Zhang (Tsinghua University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> Shortest Paths with Linear Edge Weights<\/div><div class=\"a\">Suryajith Chillara, Kshitij Gajjar (International Institute of Information Technology, Hyderabad); Nithish Raja (Eindhoven University of Technology)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Distances in Planar Graphs are Almost for Free!<\/div><div class=\"a\">Shay Mozes, Daniel Prigan (Reichman University, Israel)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Optimal algorithm for 2-Approximate All Pair Shortest Paths --- almost<\/div><div class=\"a\">Manoj Gupta, Mrigankashekhar Shandilya (IIT Gandhinagar)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">2B<span class=\"heading-room\" data-heading-room=\"paper-2B\"> - Rooms 405\/406<\/span><\/span>Circuit Lower Bounds and Separations<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> A Lower Bound for Non-Commutative Circuits<\/div><div class=\"a\">Ran Raz (Princeton University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> Exponential lower bounds for depth-3 circuits in small characteristic<\/div><div class=\"a\">Michael A. Forbes (University of Illinois at Urbana-Champaign)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> Derandomized Sunflowers and Radical Lower Bounds<\/div><div class=\"a\">Bruno Cavalar (University of Oxford); Th\u00e9o Fabris (University of Copenhagen); Partha Mukhopadhyay (Chennai Mathematical Institute); Srikanth Srinivasan, Amir Yehudayoff (University of Copenhagen)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries<\/div><div class=\"a\">Hanlin Ren (Institute for Advanced Study); Ryan Williams (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Separating RAM and Multitape Turing Machines with Short Random Oracles<\/div><div class=\"a\">Lijie Chen, Yichuan Wang (UC Berkeley)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">2C<span class=\"heading-room\" data-heading-room=\"paper-2C\"> - Rooms 905\/907<\/span><\/span>Learning Theory and Calibration<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> Robust Learning with Optimal Error<\/div><div class=\"a\">Guy Blanc (Stanford University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners<\/div><div class=\"a\">Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Mingchen Ma (UW-Madison)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> Tight Bounds for Learning Polyhedra with a Margin<\/div><div class=\"a\">Shyamal Patel (Columbia University); Santosh Vempala (Georgia Tech)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End<\/div><div class=\"a\">Steve Hanneke (Purdue University); Idan Mehalel (The Hebrew University); Shay Moran (Technion and Google Research)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Optimal Lower Bounds for Online Multicalibration<\/div><div class=\"a\">Natalie Collina, Jiuyao Lu, Georgy Noarov, Aaron Roth (University of Pennsylvania)<\/div>\r\n<\/div>\r\n<div class=\"sess D\"><h3><span class=\"code\">2D<span class=\"heading-room\" data-heading-room=\"paper-2D\"> - Room 914<\/span><\/span>Geometry, Polyhedra and Metric Spaces<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> A general framework for geometric problems: Low-dimensionality implies a PTAS<\/div><div class=\"a\">Alon Hovav, Yair Bartal (Hebrew University); Lee-Ad Gottlieb (Ariel University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> L\u2081-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids<\/div><div class=\"a\">Chris Gartland (UNC Charlotte); Mikhail Ostrovskii (St. John&#x27;s University); Yuval Rabani (The Hebrew University of Jerusalem); Robert Young (New York University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> A PTAS for Euclidean Capacitated Vehicle Routing<\/div><div class=\"a\">Zachary Friggstad (University of Alberta); Fabrizio Grandoni, Ramin Mousavi (IDSIA, USI-SUPSI); Kinter Ren, Mohammad R. Salavatipour (University of Alberta)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs<\/div><div class=\"a\">Mark de Berg (TU Eindhoven); Bart Jansen (TU Eindhoven, the Netherlands); Jeroen S.K. Lamme (TU Eindhoven)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Circuit Diameter of Polyhedra is Strongly Polynomial<\/div><div class=\"a\">Bento Natura (Columbia University)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">12:50 \u2013 2:20 pm<\/div><div class=\"evt major\"><span class=\"lbl\">Lunch (90 minutes)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 3<\/b>2:20 \u2013 3:50 pm<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(4,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">3A<span class=\"heading-room\" data-heading-room=\"paper-3A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Fine-Grained Complexity<\/h3>\r\n<div class=\"t\"><span class=\"tm\">2:20<\/span> 3SUM Is Really Hard: A Real-to-Integer Reduction<\/div><div class=\"a\">Nick Fischer (Max Planck Institute for Informatics); Adam Polak, Jonas Schmidt (Bocconi University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">2:38<\/span> Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem<\/div><div class=\"a\">Nick Fischer (Max Planck Institute for Informatics); Ce Jin (UC Berkeley); Yinzhan Xu (University of California, San Diego)<\/div>\r\n<div class=\"t\"><span class=\"tm\">2:56<\/span> Dynamic Time Warping in the Low-Distance Regime<\/div><div class=\"a\">Itai Boneh (University of Wroc\u0142aw); Shay Golan (Ariel University); Tomasz Kociumaka (Max Planck Institute for Informatics)<\/div>\r\n<div class=\"t\"><span class=\"tm\">3:14<\/span> Can We Break Fine-Grained and NP-Hardness Barriers if We&#x27;ve Seen the Graph Before? The Isomorphic-Priors Model<\/div><div class=\"a\">Dani Dorfman, Simon D\u00f6ring, Martin Herold, Danupon Nanongkai (Max Planck Institute for Informatics, Saarland Informatics Campus); Daniel Neuen (TU Dresden); Joachim Spoerhase (University of Liverpool); Zihang Wu (Max Planck Institute for Informatics, Saarland Informatics Campus)<\/div>\r\n<div class=\"t\"><span class=\"tm\">3:32<\/span> Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis<\/div><div class=\"a\">Deepak Bhati (CISPA Helmholtz Center for Information Security); Pranjal Dutta (Nanyang Technological University, Singapore); Antoine Joux, Mahesh Sreekumar Rajasree (CISPA Helmholtz Center for Information Security); Karol W\u0119grzycki (Max Planck Institute for Informatics)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">3B<span class=\"heading-room\" data-heading-room=\"paper-3B\"> - Rooms 405\/406<\/span><\/span>Quantum Circuits and Lower Bounds<\/h3>\r\n<div class=\"t\"><span class=\"tm\">2:20<\/span> QAC\u2070 contains TC\u2070 (with many copies of the input)<\/div><div class=\"a\">Daniel Grier, Jackson Morris (University of California, San Diego); Kewen Wu (Institute for Advanced Study)<\/div>\r\n<div class=\"t\"><span class=\"tm\">2:38<\/span> Worst-case depth hierarchy for shallow quantum circuits<\/div><div class=\"a\">Min-Hsiu Hsieh, Michael de Oliveira (Hon Hai (Foxconn) Quantum Computing Research Center); Sathyawageeswar Subramanian (University of Oxford); Xingjian Zhang (University of Technology Sydney)<\/div>\r\n<div class=\"t\"><span class=\"tm\">2:56<\/span> Quantum Speedups Require Structure or Depth<\/div><div class=\"a\">Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan (Stanford University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">3:14<\/span> Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders<\/div><div class=\"a\">Vishnu Iyer, Siddhartha Jain (UT Austin); Stephen Jordan, Rolando D. Somma (Google)<\/div>\r\n<div class=\"t\"><span class=\"tm\">3:32<\/span> Tight Quantum Lower Bound for k-Distinctness<\/div><div class=\"a\">Aleksandrs Belovs (University of Latvia)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">3C<span class=\"heading-room\" data-heading-room=\"paper-3C\"> - Rooms 905\/907<\/span><\/span>Mechanism Design, Fair Division and Fixed Points<\/h3>\r\n<div class=\"t\"><span class=\"tm\">2:20<\/span> Approximately Efficient Multidimensional Bilateral Trade<\/div><div class=\"a\">Aviad Rubinstein (Stanford University, USA); Xizhi Tan, Zixin Zhou (Stanford University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">2:38<\/span> On the Existence of Fair Allocations for Goods and Chores under Dissimilar Preferences<\/div><div class=\"a\">Egor Gagushin, Marios Mertzanidis (Purdue University); Alexandros Psomas (Purdue University and Google Research)<\/div>\r\n<div class=\"t\"><span class=\"tm\">2:56<\/span> Sample-efficient black-box reductions in Bayesian mechanism design with independent items<\/div><div class=\"a\">Arya Maheshwari (Carnegie Mellon University); S. Matthew Weinberg, Eric Xue (Princeton University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">3:14<\/span> Truthful-in-Expectation Mechanisms for MMS Approximation<\/div><div class=\"a\">Moshe Babaioff (The Hebrew University of Jerusalem); Uriel Feige (Weizmann Institute of Science); Noam Manaker Morag (The Hebrew University of Jerusalem)<\/div>\r\n<div class=\"t\"><span class=\"tm\">3:32<\/span> Faster Approximate Fixed Points of \u2113\u221e-Contractions<\/div><div class=\"a\">Andrei Feodorov, Sebastian Haslebacher (ETH Zurich)<\/div>\r\n<\/div>\r\n<div class=\"sess D\"><h3><span class=\"code\">3D<span class=\"heading-room\" data-heading-room=\"paper-3D\"> - Room 914<\/span><\/span>Streaming, Sketching and Communication<\/h3>\r\n<div class=\"t\"><span class=\"tm\">2:20<\/span> Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams<\/div><div class=\"a\">Elena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A&amp;M University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">2:38<\/span> Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams<\/div><div class=\"a\">Cheng Jiang (MIT); Yinchen Liu (Tsinghua University); Huacheng Yu (Princeton University)<\/div>\r\n<div class=\"merged\"><span class=\"mtag\">Merged &middot; one talk slot<\/span><div class=\"t\"><span class=\"tm\">2:56<\/span> Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs<\/div><div class=\"a\">Noah G. Singer (Carnegie Mellon University); Madhur Tulsiani (Toyota Technological Institute at Chicago); Santhoshini Velusamy (University of Waterloo)<\/div><div class=\"t\">Near-Optimal Space Lower Bounds for Streaming CSPs<\/div><div class=\"a\">Yumou Fei, Dor Minzer, Shuo Wang (MIT)<\/div><\/div>\r\n<div class=\"t\"><span class=\"tm\">3:14<\/span> Quality control in sublinear time: a case study via random graphs<\/div><div class=\"a\">Cassandra Marcussen (Harvard University); Ronitt Rubinfeld (MIT); Madhu Sudan (Harvard University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">3:32<\/span> Short and Sweet: Computationally Efficient Collaborative Communication Through Indistinguishability and Coarsening<\/div><div class=\"a\">Mark Bedaywi, Scott Emmons, Nika Haghtalab, Stuart Russell (UC Berkeley)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">3:50 \u2013 4:10 pm<\/div><div class=\"evt\"><span class=\"lbl\">Coffee Break (20 min)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 4<\/b>4:10 \u2013 5:58 pm<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(4,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">4A<span class=\"heading-room\" data-heading-room=\"paper-4A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Data Structures and Space\u2013Time Tradeoffs<\/h3>\r\n<div class=\"t\"><span class=\"tm\">4:10<\/span> An \u03a9((log n \/ log log n)\u00b2) Cell-Probe Lower Bound for Dynamic Boolean Data Structures<\/div><div class=\"a\">Young Kun Ko (Pennsylvania State University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:28<\/span> Compressed Inverse Suffix Arrays<\/div><div class=\"a\">Sharma V. Thankachan (North Carolina State University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:46<\/span> Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space<\/div><div class=\"a\">Guy E. Blelloch (Carnegie Mellon University); Yang Hu (Tsinghua University); William Kuszmaul (Carnegie Mellon University); Tianxiao Li (Independent Researcher); Renfei Zhou (Carnegie Mellon University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:04<\/span> Sorting under Partial Information with Optimal Preprocessing Time via Unified Bound Heaps<\/div><div class=\"a\">Daniel Rutschmann (Institute of Science and Technology Austria (ISTA))<\/div>\r\n<div class=\"merged\"><span class=\"mtag\">Merged &middot; one talk slot<\/span><div class=\"t\"><span class=\"tm\">5:22<\/span> Improved space-time tradeoff for TSP via extremal set systems<\/div><div class=\"a\">Justin Dallant, L\u00e1szl\u00f3 Kozma (Dresden University of Technology)<\/div><div class=\"t\">Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics<\/div><div class=\"a\">Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang (Utrecht University)<\/div><\/div>\r\n<div class=\"t\"><span class=\"tm\">5:40<\/span> The Power of Two-Choice Linear Probing<\/div><div class=\"a\">Amir Azarmehr (Northeastern University); Michael Bender (Stony Brook University); William Kuszmaul, Rose Silver (Carnegie Mellon University)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">4B<span class=\"heading-room\" data-heading-room=\"paper-4B\"> - Rooms 405\/406<\/span><\/span>Proof Complexity and Space-Bounded Computation<\/h3>\r\n<div class=\"t\"><span class=\"tm\">4:10<\/span> Hard CNF Instances for Ideal Proof Systems: The ROABP Case<\/div><div class=\"a\">Tuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:28<\/span> Many Proof Complexity Generators Inside One Demi-Bits Generator<\/div><div class=\"a\">Xin Li (Johns Hopkins University); Hanlin Ren (Institute for Advanced Study); Yan Zhong (Johns Hopkins University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:46<\/span> Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size<\/div><div class=\"a\">Susanna F. de Rezende, David Engstr\u00f6m (Lund University); Yassine Ghannane (University of Copenhagen); Kilian Risse (Lund University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:04<\/span> The Proof Analysis Problem for Constant-Depth Frege<\/div><div class=\"a\">Noel Arteche (Lund University &amp; University of Copenhagen); Susanna de Rezende (Lund University); Erfan Khaniki (University of Oxford); Kilian Risse (Lund University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:22<\/span> Limit on the computational power of C-random strings<\/div><div class=\"a\">Alexey Milovanov (University of Lisbon)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:40<\/span> Composing Low-Space Algorithms<\/div><div class=\"a\">Edward Pyne (MIT); Roei Tell (University of Toronto)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">4C<span class=\"heading-room\" data-heading-room=\"paper-4C\"> - Rooms 905\/907<\/span><\/span>Online Algorithms, Scheduling and Optimization<\/h3>\r\n<div class=\"t\"><span class=\"tm\">4:10<\/span> Online Algorithms via Minimax and Posterior Matching<\/div><div class=\"a\">Thomas Kesselheim (University of Bonn); Marco Molinaro (Microsoft Research); Kalen Patton, Sahil Singla (Georgia Institute of Technology)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:28<\/span> Optimal Online Bin Packing under Prophet, Random-Order, and Learning-from-Samples Models<\/div><div class=\"a\">Kailash Gopal Darmasubramanian (Indian Institute of Technology, Madras); Samyak Jha, Arindam Khan, K. V. N. Sreenivas (Indian Institute of Science, Bengaluru)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:46<\/span> The Instability of all Backoff Protocols<\/div><div class=\"a\">Leslie Ann Goldberg (University of Oxford); John Lapinskas (University of Bristol)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:04<\/span> Breaking the Barrier of 2 for Approximating Weighted Throughput Maximization via the Sherali-Adams Hierarchy<\/div><div class=\"a\">Alexander Armbruster (Technical University of Munich); Fabrizio Grandoni (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:22<\/span> NP-Hardness and a PTAS for the Pinwheel Problem<\/div><div class=\"a\">Robert Kleinberg, Ahan Mishra (Cornell University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:40<\/span> Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory<\/div><div class=\"a\">Michael Menart (University of Toronto, Vector Institute); Sasho Nikolov (University of Toronto); Ohad Shamir (Weizmann Institute and University of Toronto)<\/div>\r\n<\/div>\r\n<div class=\"sess D\"><h3><span class=\"code\">4D<span class=\"heading-room\" data-heading-room=\"paper-4D\"> - Room 914<\/span><\/span>Parameterized Algorithms and Enumeration<\/h3>\r\n<div class=\"t\"><span class=\"tm\">4:10<\/span> Branch-width of connectivity functions is fixed-parameter tractable<\/div><div class=\"a\">Tuukka Korhonen (University of Copenhagen); Sang-il Oum (Institute for Basic Science)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:28<\/span> Fixed-Parameter Tractability and Hardness for Steiner Rooted and Locally Connected Orientations<\/div><div class=\"a\">Krist\u00f3f B\u00e9rczi (E\u00f6tv\u00f6s Lor\u00e1nd University); Florian H\u00f6rsch (CISPA Helmholtz Center for Information Security); Andr\u00e1s Imolay (E\u00f6tv\u00f6s Lor\u00e1nd University); Tam\u00e1s Schwarcz (London School of Economics and Political Science)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:46<\/span> Optimal Bounds for the k-Disjoint Paths Problem<\/div><div class=\"a\">Maximilian Gorsky (Institute for Basic Science); Dario Giuliano Cavallaro, Stephan Kreutzer (TU Berlin); Dimitrios Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France); Sebastian Wiederrecht (KAIST)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:04<\/span> Weighted Treewidth on Minor-Free Graphs: Combinatorics and Approximation<\/div><div class=\"a\">D\u00e1niel Marx (CISPA Helmholtz Center for Information Security); Micha\u0142 Pilipczuk (University of Warsaw, Poland); Karol W\u0119grzycki (Max Planck Institute for Informatics)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:22<\/span> Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration<\/div><div class=\"a\">Karl Bringmann (ETH Zurich); Nick Fischer (Max Planck Institute for Informatics); Yanheng Wang (ETH Z\u00fcrich)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">6:30 \u2013 7:45 pm<\/div><div class=\"evt major\"><span class=\"lbl\">Business Meeting<\/span><\/div><\/div>\r\n<h2 id=\"tuesday\" class=\"day\">Tuesday, November 10<\/h2><div class=\"dayrule\"><span class=\"daymeta\">3 parallel tracks; afternoon given to the award sessions<\/span><\/div>\r\n<div class=\"row\"><div class=\"time\">9:00 \u2013 9:30 am<\/div><div class=\"evt\"><span class=\"lbl\">Breakfast<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 5<\/b>9:30 \u2013 11:00 am<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(3,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">5A<span class=\"heading-room\" data-heading-room=\"paper-5A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Quantum Information Theory<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Constructive counterexamples to the additivity of minimum output R\u00e9nyi entropy of quantum channels for all p &gt; 1<\/div><div class=\"a\">Harm Derksen (Northeastern University); Benjamin Lovitz (Concordia University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> On the undecidability of quantum channel capacities<\/div><div class=\"a\">Archishna Bhattacharyya, Arthur Mehta (University of Ottawa); Yuming Zhao (University of Copenhagen)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> A quasipolynomial-time classical algorithm for SYK thermal expectations<\/div><div class=\"a\">Alexander Zlokapa (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians<\/div><div class=\"a\">Zhengfeng Ji (Tsinghua University); Tongyang Li (Peking University); Changpeng Shao (Academy of Mathematics and System Sciences, Chinese Academy of Sciences); Xinzhao Wang (Peking University); Yuxin Zhang (Academy of Mathematics and Systems Science, Chinese Academy of Sciences)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> Explicit Separations for One-Query Unitary Synthesis<\/div><div class=\"a\">Fangqi Dong, Alex Lombardi (Princeton University); Fermi Ma (New York University)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">5B<span class=\"heading-room\" data-heading-room=\"paper-5B\"> - Rooms 405\/406<\/span><\/span>Quantum Cryptography and Oracles<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Classical Obfuscation of Quantum Circuits via Publicly-Verifiable QFHE<\/div><div class=\"a\">James Bartusek (Columbia); Aparna Gupte (MIT CSAIL); Saachi Mutreja (Columbia); Omri Shmueli (NTT Research)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> Obfuscation of Arbitrary Quantum Circuits (via Subspace-Preserving Pseudorandom Unitary)<\/div><div class=\"a\">Er-Cheng Tang (University of Washington); Mi-Ying Miryam Huang (University of Southern California)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Certified Randomness without Structure Against Shallow-Query Adversaries<\/div><div class=\"a\">Dakshita Khurana (UIUC and NTT Research); Bhaskar Roberts, Avishay Tal (UC Berkeley)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> Quantum oracles, weak and strong<\/div><div class=\"a\">John Wright (The University of California, Berkeley); Ewin Tang (UC Berkeley); Mark Zhandry (Stanford)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> Separating Quantum and Classical Advice with Good Codes<\/div><div class=\"a\">Andrew Huang (MIT); John Bostanci (Columbia University); Vinod Vaikuntanathan (MIT)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">5C<span class=\"heading-room\" data-heading-room=\"paper-5C\"> - Rooms 905\/907<\/span><\/span>Coding Theory and Error Correction<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep&#x27;s clothing<\/div><div class=\"a\">Pranav Joshi (California Institute of Technology); Daniel McMorrow (National University of Singapore); Yihan Zhang (University of Bristol); Amitalok J. Budkuley (Indian Institute of Technology Kharagpur); Sidharth Jaggi (University of Bristol)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> Towards a Unified Algorithmic Framework for Shannon&#x27;s Theorem<\/div><div class=\"a\">Sayan Bhattacharya (University of Warwick, UK); Martin Costa (University of Warwick); Shay Solomon (Tel Aviv University); Tianyi Zhang (Nanjing University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Linear-Time Encodable and Decodable Quantum Error-Correcting Codes<\/div><div class=\"a\">Adam Wills (Center for Theoretical Physics --- a Leinweber Institute, Massachusetts Institute of Technology, Cambridge, MA; Hon Hai (Foxconn) Research Institute, Taipei, Taiwan); Ting-Chun Lin (Department of Physics, University of California at San Diego, La Jolla, CA; Hon Hai (Foxconn) Research Institute, Taipei, Taiwan); Rachel Yun Zhang (CSAIL, Massachusetts Institute of Technology, Cambridge, MA); Min-Hsiu Hsieh (Hon Hai (Foxconn) Research Institute, Taipei, Taiwan)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> Explicit Constant-Alphabet Subspace Design Codes<\/div><div class=\"a\">Rohan Goyal (MIT); Venkatesan Guruswami (UC Berkeley); Jun-Ting Hsieh (Massachusetts Institute of Technology)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> Error-Correction of Matrix Multiplication Algorithms over Integers<\/div><div class=\"a\">Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Institute of Science Tokyo)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">11:00 \u2013 11:20 am<\/div><div class=\"evt\"><span class=\"lbl\">Coffee Break (20 min)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 6<\/b>11:20 am \u2013 12:50 pm<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(3,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">6A<span class=\"heading-room\" data-heading-room=\"paper-6A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Sampling and Counting<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> A computational phase transition for learning-to-sample from Ising models<\/div><div class=\"a\">Andrej Risteski (Carnegie Mellon University); Thuy-Duong (June) Vuong (UC San Diego)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> Rapid mixing in positively weighted restricted Boltzmann machines<\/div><div class=\"a\">Weiming Feng (The University of Hong Kong); Heng Guo (University of Edinburgh); Minji Yang (The University of Hong Kong)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> Subquadratic Counting via Perfect Marginal Sampling<\/div><div class=\"a\">Xiaoyu Chen (MIT); Zongchen Chen (Georgia Institute of Technology); Kuikui Liu (MIT); Xinyuan Zhang (Nanjing University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Non-existence probabilities and lower tails in the critical regime via Belief Propagation<\/div><div class=\"a\">Matthew Jenssen (King&#x27;s College London); Will Perkins (Georgia Institute of Technology); Aditya Potukuchi (Max Planck Institute for Software Systems); Michael Simkin (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> On Sampling Lower Bounds for Polynomials<\/div><div class=\"a\">Mohammad Mahdi Khodabandeh, Igor Shinkar (Simon Fraser University)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">6B<span class=\"heading-room\" data-heading-room=\"paper-6B\"> - Rooms 405\/406<\/span><\/span>Random Structures and Constraint Satisfaction<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> Strong Low Degree Hardness for Stable Local Optima in Spin Glasses<\/div><div class=\"a\">Brice Huang (Stanford); Mark Sellke (Harvard)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> Stable algorithms cannot reliably find isolated perceptron solutions<\/div><div class=\"a\">Shuyang Gong (Peking University); Brice Huang (Stanford University); Shuangping Li (Yale University); Mark Sellke (Harvard University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> Sharp Lovasz-Theta Bounds on Random Graphs<\/div><div class=\"a\">Aaron Potechin (University of Chicago); Jeff Xu (TTIC)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Expanders Meet Reed--Muller: Easy Instances of Noisy k-XOR<\/div><div class=\"a\">Jaros\u0142aw B\u0142asiok, Paul Lou, Alon Rosen (Bocconi University); Madhu Sudan (Harvard University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> The Richness of CSP Non-redundancy<\/div><div class=\"a\">Joshua Brakensiek (University of California, Berkeley); Venkatesan Guruswami (UC Berkeley); Bart Jansen (TU Eindhoven, the Netherlands); Victor Lagerkvist (Link\u00f6pings universitet); Magnus Wahlstrom (Royal Holloway, University of London, UK)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">6C<span class=\"heading-room\" data-heading-room=\"paper-6C\"> - Rooms 905\/907<\/span><\/span>Communication, Space-Bounded and Algebraic Algorithms<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> Gap-Majority Lemmas in Communication Complexity<\/div><div class=\"a\">Pachara Sawettamalya, Huacheng Yu (Princeton University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> No Constant-Cost Protocol for Point\u2013Line Incidence<\/div><div class=\"a\">Mika G\u00f6\u00f6s (EPFL); Nathaniel Harms (UBC); Florian K. Richter, Anastasia Sofronova (EPFL)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> Space-Efficient Simulations Beyond Multitape Turing Machines<\/div><div class=\"a\">Danil Sibgatullin, Ryan Williams (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2<\/div><div class=\"a\">Joshua A. Grochow (University of Colorado\u2014Boulder); Gabor Ivanyos (Hungarian Academy of Sciences); Youming Qiao (University of New South Wales); Xiaorui Sun (University of Illinois Chicago)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality<\/div><div class=\"a\">Frederic Koehler, Pui Kuen Leung (University of Chicago)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">12:50 \u2013 2:35 pm<\/div><div class=\"evt major\"><span class=\"lbl\">Lunch (1 hour 45 minutes)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Plenary<\/b>2:35 \u2013 4:05 pm<\/div><div class=\"award\"><h3>Best Paper Session<\/h3><p class=\"sub\">single track<\/p>\r\n<div class=\"slot\"><span class=\"tm\">2:35<\/span> <span><span class=\"st\">Rational degree is polynomially related to degree<\/span><span class=\"sa\">Robin Kothari (Google); Matt Kovacs-Deak (University of Maryland); Daochen Wang, Rain Zimin Yang (University of British Columbia)<\/span><\/span><\/div>\r\n<div class=\"slot\"><span class=\"tm\">3:05<\/span> <span><span class=\"st\">Approximation Algorithms for Matroid-Intersection Coloring with Applications to Rota&#x27;s Basis Conjecture<\/span><span class=\"sa\">Stephen Arndt, Benjamin Moseley (Carnegie Mellon University); Kirk Pruhs (University of Pittsburgh); Chaitanya Swamy (University of Waterloo); Michael Zlatin (Pomona College)<\/span><\/span><\/div>\r\n<div class=\"slot\"><span class=\"tm\">3:35<\/span> <span><span class=\"st\">The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring<\/span><span class=\"sa\">Yuta Inoue (The University of Tokyo); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Atsuyuki Miyashita (The University of Tokyo); Bojan Mohar (Simon Fraser University, Burnaby, Canada); Carsten Thomassen (Technical University of Denmark); Mikkel Thorup (University of Copenhagen)<\/span><\/span><\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">4:05 \u2013 4:30 pm<\/div><div class=\"evt\"><span class=\"lbl\">Coffee Break (25 min)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Plenary<\/b>4:30 \u2013 5:30 pm<\/div><div class=\"award\"><h3>Best Student Paper Session<\/h3><p class=\"sub\">single track<\/p>\r\n<div class=\"slot\"><span class=\"tm\">4:30<\/span> <span><span class=\"st\">Flip Distance Between Triangulations of Convex Polygons is NP-Complete<\/span><span class=\"sa\">Joseph Dorfer (Graz University of Technology)<\/span><\/span><\/div>\r\n<div class=\"slot\"><span class=\"tm\">5:00<\/span> <span><span class=\"st\">Parity \u2209 QAC\u2070 \u21d4 QAC\u2070 is Fourier-Concentrated<\/span><span class=\"sa\">Lucas Gretta, Meghal Gupta, Malvika Raj Joshi (UC Berkeley)<\/span><\/span><\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">7:30 \u2013 10:00 pm<\/div><div class=\"evt major\"><span class=\"lbl\">Joint FOCS + TCC Reception \u2014 Eisner, NYU (room turnover 5:30 \u2013 7:30)<\/span><p class=\"room-note\" data-room-note=\"reception\">Kimmel Center \u00b7 Eisner &amp; Lubin Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/p><\/div><\/div>\r\n<h2 id=\"wednesday\" class=\"day\">Wednesday, November 11<\/h2><div class=\"dayrule\"><span class=\"daymeta\">3 parallel tracks, with the Knuth Prize Lecture after lunch<\/span><\/div>\r\n<div class=\"row\"><div class=\"time\">9:00 \u2013 9:30 am<\/div><div class=\"evt\"><span class=\"lbl\">Breakfast<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 7<\/b>9:30 \u2013 11:00 am<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(3,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">7A<span class=\"heading-room\" data-heading-room=\"paper-7A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Algebraic Complexity and Tensors<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Schur complements for tensors and multilinear commutative rank<\/div><div class=\"a\">Guy Moshkovitz (City University of New York); Daniel G. Zhu (Princeton University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> The edge of the asymptotic spectrum of tensors<\/div><div class=\"a\">Josh Alman, Baitian Li, Kevin Pratt (Columbia University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Strassen&#x27;s support functionals coincide with the quantum functionals: a general classical-quantum correspondence for optimization on entanglement polytopes and beyond<\/div><div class=\"a\">Keiya Sakabe, Mahmut Levent Do\u011fan, Michael Walter (LMU Munich)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> Hilbert&#x27;s Nullstellensatz is in the Counting Hierarchy<\/div><div class=\"a\">Robert Andrews, Abhibhav Garg, \u00c9ric Schost (University of Waterloo)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials<\/div><div class=\"a\">Martino Bernasconi (Bocconi Univeristy); Matteo Castiglioni (Politecnico di Milano); Andrea Celli (Bocconi University); Gabriele Farina (MIT)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">7B<span class=\"heading-room\" data-heading-room=\"paper-7B\"> - Rooms 405\/406<\/span><\/span>PCPs and Hardness of Approximation<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Direct-product testers and PCPs from coset complexes<\/div><div class=\"a\">Ryan O&#x27;Donnell, Noah G. Singer (Carnegie Mellon University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> Classical Adversarial Fault-Tolerance and PCPs<\/div><div class=\"a\">Anurag Anshu (Harvard University); Nikolas Breuckmann (University of Bristol); Louis Golowich (UC Berkeley); Quynh T Nguyen (Harvard University); Umesh Vazirani (UC Berkeley)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Gap Amplification for Local Hamiltonians with Combinatorial Soundness<\/div><div class=\"a\">Mitali Bafna (University of Washington); Quynh T Nguyen (Harvard University); Tina Zhang (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> Deterministic Hardness of Approximation for SVP in all Finite \u2113\u209a Norms<\/div><div class=\"a\">Isaac Hair (UCSB, UCLA); Amit Sahai (UCLA)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> Optimal PSPACE-hardness of Approximating q-CSP Reconfiguration<\/div><div class=\"a\">Shuichi Hirahara (National Institute of Informatics); Naoto Ohsaka (CyberAgent, Inc.)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">7C<span class=\"heading-room\" data-heading-room=\"paper-7C\"> - Rooms 905\/907<\/span><\/span>Constraint Satisfaction and Boolean Functions<\/h3>\r\n<div class=\"t\"><span class=\"tm\">9:30<\/span> Conservative Maltsev Constraint Satisfaction Problems<\/div><div class=\"a\">Andrew Moorhead, Manuel Bodirsky (TU Dresden)<\/div>\r\n<div class=\"t\"><span class=\"tm\">9:48<\/span> Singleton algorithms for the Constraint Satisfaction Problem<\/div><div class=\"a\">Dmitriy Zhuk (Charles University, Prague)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:06<\/span> Approximate polymorphisms of predicates<\/div><div class=\"a\">Yuval Filmus, Yaroslav Alekseev (Technion)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:24<\/span> PTF Lower Bounds from Low-Degree Testing Lower Bounds in Additive Noise Models<\/div><div class=\"a\">Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Sihan Liu (UCSD); Trung Tran (University of California, San Diego)<\/div>\r\n<div class=\"t\"><span class=\"tm\">10:42<\/span> DNF formulas are efficiently testable with relative error<\/div><div class=\"a\">William Pires (Columbia); Xi Chen, Toniann Pitassi, Rocco A. Servedio (Columbia University)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">11:00 \u2013 11:20 am<\/div><div class=\"evt\"><span class=\"lbl\">Coffee Break (20 min)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 8<\/b>11:20 am \u2013 12:50 pm<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(3,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">8A<span class=\"heading-room\" data-heading-room=\"paper-8A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Codes, Fault Tolerance and Information<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> Recovering Polynomials over Finite Fields from Noisy Character Values<\/div><div class=\"a\">Swastik Kopparty (University of Toronto)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> Explicit Almost-Optimal \u03b5-Balanced Codes via Free Expander Walks<\/div><div class=\"a\">Jun-Ting Hsieh (Massachusetts Institute of Technology); Sidhanth Mohanty (Northwestern University); Rachel Yun Zhang (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets<\/div><div class=\"a\">Zeyu Guo, Roshan Raj (The Ohio State University); Chong Shangguan (Shandong University); Zihan Zhang (The Ohio State University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> Fault-Tolerant Quantum Computation with Adversarial Errors<\/div><div class=\"a\">Nikolas Breuckmann (University of Bristol); Louis Golowich, Umesh Vazirani (UC Berkeley)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Zero-error information equals amortized communication complexity<\/div><div class=\"a\">Daiki Suruga (CFT PAN)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">8B<span class=\"heading-room\" data-heading-room=\"paper-8B\"> - Rooms 405\/406<\/span><\/span>Structural Graph Theory<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> Polynomial \u03c7-boundedness for excluding P\u2085<\/div><div class=\"a\">Tung Nguyen (University of Oxford)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> Hereditary 2-WQO Graph Classes Have Bounded Clique-Width<\/div><div class=\"a\">Julien Duron, Nikolas M\u00e4hlmann, Szymon Toru\u0144czyk (University of Warsaw)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> The Lov\u00e1sz conjecture holds for moderately dense Cayley graphs<\/div><div class=\"a\">Benjamin Bedert (Univeversity of Cambridge); Nemanja Draganic, Alp Muyesser (University of Oxford); Matias Pavez-Signe (University of Chile)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> A coarse Menger&#x27;s Theorem for planar graphs<\/div><div class=\"a\">V\u00e1clav Bla\u017eej, Micha\u0142 Pilipczuk, Evangelos Protopapas (Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Poland)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Better Bounds For Graph Reconstruction<\/div><div class=\"a\">Antoni Buraczewski, Pawe\u0142 Gawrychowski (University of Wroc\u0142aw)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">8C<span class=\"heading-room\" data-heading-room=\"paper-8C\"> - Rooms 905\/907<\/span><\/span>Equilibria, Welfare and Price of Anarchy<\/h3>\r\n<div class=\"t\"><span class=\"tm\">11:20<\/span> On the Complexity of Learning Nash Equilibria<\/div><div class=\"a\">Oliver Biggar (Columbia University); Christos Papadimitriou (Columbia U); Georgios Piliouras (Google DeepMind \/ SUTD)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:38<\/span> The Complexity of Computing a Unique Nash Equilibrium<\/div><div class=\"a\">Abheek Ghosh (Technical University of Munich); Paul W. Goldberg, Alexandros Hollender (University of Oxford)<\/div>\r\n<div class=\"t\"><span class=\"tm\">11:56<\/span> The Mystery Deepens: On the Query Complexity of Tarski Fixed Points<\/div><div class=\"a\">Xi Chen, Yuhao Li, Mihalis Yannakakis (Columbia University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:14<\/span> The Price of Anarchy for Selfish Load Balancing<\/div><div class=\"a\">Xihan Deng (Shanghai Jiao Tong University); Yaonan Jin (Hong Kong University of Science and Technology); Wenqian Wang, Yuhao Zhang (Shanghai Jiao Tong University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">12:32<\/span> Online Submodular Welfare Maximization: Computation is not the Bottleneck<\/div><div class=\"a\">Rajan Udwani (UC Berkeley); David Wajc (Technion)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">12:50 \u2013 2:20 pm<\/div><div class=\"evt major\"><span class=\"lbl\">Lunch (90 minutes)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Plenary<\/b>2:20 \u2013 3:35 pm<\/div><div class=\"award\"><h3>Knuth Prize Lecture<span class=\"heading-room\" data-heading-room=\"knuth\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/h3><p class=\"sub\">single track<\/p><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">3:35 \u2013 4:00 pm<\/div><div class=\"evt\"><span class=\"lbl\">Coffee Break (25 min)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 9<\/b>4:00 \u2013 5:12 pm<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(3,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">9A<span class=\"heading-room\" data-heading-room=\"paper-9A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Graph Algorithms and Distance Oracles<\/h3>\r\n<div class=\"t\"><span class=\"tm\">4:00<\/span> Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate<\/div><div class=\"a\">Yaowei Long (University of Michigan)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:18<\/span> A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs<\/div><div class=\"a\">Kuowen Chen (Tsinghua University); Nicole Wein (University of Michigan, Ann Arbor, USA); Yiran Zhang (Tsinghua University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:36<\/span> Approximate Spanning Tree Counting from Uncorrelated Edge Sets<\/div><div class=\"a\">Yang Liu, Richard Peng, Junzhao Yang (Carnegie Mellon University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:54<\/span> Instance-Optimality of Bidirectional PageRank Estimation<\/div><div class=\"a\">Mikkel Thorup (University of Copenhagen); Hanzhi Wang (The University of Melbourne)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">9B<span class=\"heading-room\" data-heading-room=\"paper-9B\"> - Rooms 405\/406<\/span><\/span>Sublinear Algorithms and Property Testing<\/h3>\r\n<div class=\"t\"><span class=\"tm\">4:00<\/span> \u00d5(1)-Depth Parallel Reachability Faster than Transitive Closure<\/div><div class=\"a\">Shimon Kogan, Merav Parter (Weizmann)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:18<\/span> Graph k-Coloring in Sublinear Average Time<\/div><div class=\"a\">Cassandra Marcussen (Harvard University); Edward Pyne, Ronitt Rubinfeld (MIT); Asaf Shapira, Shlomo Tauber (Tel Aviv University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:36<\/span> Testing Properties of Edge Distributions<\/div><div class=\"a\">Yumou Fei (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:54<\/span> Efficient and Private Property Testing via Indistinguishability<\/div><div class=\"a\">Cynthia Dwork, Pranay Tankala (Harvard University)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">9C<span class=\"heading-room\" data-heading-room=\"paper-9C\"> - Rooms 905\/907<\/span><\/span>Privacy and Learning<\/h3>\r\n<div class=\"t\"><span class=\"tm\">4:00<\/span> Local Node Differential Privacy<\/div><div class=\"a\">Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov (Boston University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:18<\/span> The Sample Complexity of Membership Inference and Privacy Auditing<\/div><div class=\"a\">Mahdi Haghifam (TTIC); Adam Smith (Boston University); Jonathan Ullman (Northeastern University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:36<\/span> The optimal information complexity of VC learning<\/div><div class=\"a\">Steve Hanneke, Juexiao Wang (Purdue University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">4:54<\/span> Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery<\/div><div class=\"a\">Chao Gao (University of Chicago); Liren Shan (Toyota Technological Institute at Chicago); Vaidehi Srinivas, Aravindan Vijayaraghavan (Northwestern University)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<div class=\"row\"><div class=\"time\">5:12 \u2013 5:32 pm<\/div><div class=\"evt\"><span class=\"lbl\">Coffee Break (20 min)<\/span><\/div><\/div>\r\n<div class=\"row\"><div class=\"time\"><b>Block 10<\/b>5:32 \u2013 6:44 pm<\/div><div class=\"grid\" style=\"grid-template-columns:repeat(3,minmax(0,1fr))\">\r\n<div class=\"sess A\"><h3><span class=\"code\">10A<span class=\"heading-room\" data-heading-room=\"paper-10A\"> - E&amp;L Auditorium <span class=\"floor-note\">(4th floor)<\/span><\/span><\/span>Approximation and Exact Algorithms<\/h3>\r\n<div class=\"t\"><span class=\"tm\">5:32<\/span> An O(log log n)-Approximation Algorithm for Submodular Unsplittable Flow on a Path<\/div><div class=\"a\">Alexander Armbruster (Technical University of Munich); Fabrizio Grandoni (IDSIA, USI-SUPSI); Andreas Wiese (Technical University of Munich); Ruilong Zhang (City University of Hong Kong (Dongguan))<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:50<\/span> Stochastic Gradient Meets Randomized Rounding: New Algorithms for Node-Weighted Steiner Problems<\/div><div class=\"a\">Joseph Koutsoutis, Jesse Lerner, Roie Levin, Jiawei Yu (Rutgers University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">6:08<\/span> Improved Upper Bounds for the Directed Flow-Cut Gap<\/div><div class=\"a\">Greg Bodwin, Luba Samborska (University of Michigan)<\/div>\r\n<div class=\"t\"><span class=\"tm\">6:26<\/span> Dense Subset Sum in Multi-Dimension<\/div><div class=\"a\">Lin Chen, Tingwei Hu, Yuchen Mao, Guochuan Zhang (Zhejiang University)<\/div>\r\n<\/div>\r\n<div class=\"sess B\"><h3><span class=\"code\">10B<span class=\"heading-room\" data-heading-room=\"paper-10B\"> - Rooms 405\/406<\/span><\/span>Optimization, Refutation and Parameterized Approximation<\/h3>\r\n<div class=\"t\"><span class=\"tm\">5:32<\/span> Strongly Refuting Random CSP without Literals<\/div><div class=\"a\">Siu On Chan (Unaffiliated); Tommaso D&#x27;Orsi (Bocconi University); Jeff Xu (TTIC)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:50<\/span> Fast Convergence of Gradient Descent on Random \u2113\u209a-Norm Regression<\/div><div class=\"a\">Yang Liu, Richard Peng, Weina Wang, Junzhao Yang (Carnegie Mellon University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">6:08<\/span> A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition<\/div><div class=\"a\">Ioannis Anagnostides (Carnegie Mellon University); Gabriele Farina (MIT); Tuomas Sandholm (Carnegie Mellon University); Brian Hu Zhang (MIT)<\/div>\r\n<div class=\"t\"><span class=\"tm\">6:26<\/span> Optimal FPT-Approximability for Modular Linear Equations<\/div><div class=\"a\">Konrad K. Dabrowski (Newcastle University); Peter Jonsson (Link\u00f6ping University); Sebastian Ordyniak (University of Leeds, UK); George Osipov (University of Oxford); Magnus Wahlstrom (Royal Holloway, University of London, UK)<\/div>\r\n<\/div>\r\n<div class=\"sess C\"><h3><span class=\"code\">10C<span class=\"heading-room\" data-heading-room=\"paper-10C\"> - Rooms 905\/907<\/span><\/span>Hashing, Contention and Communication<\/h3>\r\n<div class=\"t\"><span class=\"tm\">5:32<\/span> Fast Insertion for Bucketized Cuckoo Hashing<\/div><div class=\"a\">Tolson Bell, William Kuszmaul (Carnegie Mellon University)<\/div>\r\n<div class=\"t\"><span class=\"tm\">5:50<\/span> Online Graph Balancing and the Power of Two Choices<\/div><div class=\"a\">Nikhil Bansal, Milind Prabhu (University of Michigan); Sahil Singla (Georgia Institute of Technology); Siddharth Meenachi Sundaram (Georgia Tech)<\/div>\r\n<div class=\"t\"><span class=\"tm\">6:08<\/span> The communication complexity of distributed estimation<\/div><div class=\"a\">Parikshit Gopalan (Apple); Raghu Meka (UCLA); Prasad Raghavendra, Mihir Singhal (UC Berkeley); Avi Wigderson (Institute for Advanced Study)<\/div>\r\n<div class=\"t\"><span class=\"tm\">6:26<\/span> Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication<\/div><div class=\"a\">Guangxu Yang, Jiapeng Zhang (University of Southern California)<\/div>\r\n<\/div>\r\n<\/div><\/div>\r\n<\/div><\/div>\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":"","protected":false},"author":20,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":"","_members_access_role":[],"_members_access_error":""},"class_list":["post-1854","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages\/1854","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/comments?post=1854"}],"version-history":[{"count":19,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages\/1854\/revisions"}],"predecessor-version":[{"id":1892,"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/pages\/1854\/revisions\/1892"}],"wp:attachment":[{"href":"https:\/\/focs.computer.org\/2026\/wp-json\/wp\/v2\/media?parent=1854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}