| STOC 2025 Program | ||||||||||||
|
|
||||||||||||
| Sunday June 22 | ||||||||||||
| 18:00- 20:00 |
Hotel Foyer
Reception
|
|||||||||||
|
|
||||||||||||
|
|
||||||||||||
| Monday June 23 | ||||||||||||
|
Congress Hall Sun I + II
Workshop B
|
Lounge Jupiter
Workshop D
|
Lounge Uranus
Workshop A
|
||||||||||
| 8:45-10:45 | ||||||||||||
|
|
||||||||||||
| 10:45 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I + II
Session 1A: Best Student Paper and start of Best Papers
|
||||||||||||
| 11:15 | Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bounds Yeyuan Chen (University of Michigan, Ann Arbor); Zihan Zhang (Ohio State University) |
|||||||||||
| 11:35 | ||||||||||||
| 11:55 | Vizing's Theorem in Near-Linear Time Sepehr Assadi (University of Waterloo); Soheil Behnezhad (Northeastern University); Sayan Bhattacharya, Martin Costa (University of Warwick); Shay Solomon (Tel Aviv University); Tianyi Zhang (ETH Zurich) |
|||||||||||
|
|
||||||||||||
| 12:15 |
Buffet Lunch (provided)
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 2A
|
Congress Hall Sun II
Session 2B
|
Lounge Jupiter
Session 2C
|
Lounge Uranus
Session 2D
|
|||||||||
| 14:00 | Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection Euiwoong Lee (University of Michigan); Ola Svensson, Theophile Thiery (EPFL) |
Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More Tuukka Korhonen (University of Copenhagen) |
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from #P Hardness Dakshita Khurana (University of Illinois at Urbana-Champaign, NTT Research); Kabir Tomer (University of Illinois Urbana-Champaign) |
|||||||||
| 14:18 | Approximation Algorithms for Satisfiable CSPs via a Mixed Invariance Principle Amey Bhangale (UC Riverside); Subhash Khot (NYU); Dor Minzer (MIT) |
Network Unreliability in Almost-Linear Time Debmalya Panigrahi, Ruoxu Cen (Duke University); Jason Li (Carnegie Mellon University) |
Quantum-Computable One-Way Functions without One-Way Functions William Kretschmer (Simons Institute); Luowen Qian (NTT Research, Inc.); Avishay Tal (UC Berkeley) |
A Framework for Building Data Structures from Communication Protocols Alexandr Andoni, Shunhua Jiang (Columbia University); Omri Weinstein (Columbia University and the Hebrew University) |
||||||||
| 14:36 | Hardness of 4-colouring $G$-colourable graphs Sergey Avvakumov (Tel Aviv University); Marek Filakovský (Masaryk University); Jakub Opršal (University of Birmingham); Gianluca Tasinato, Uli Wagner (Institute of Science and Technology Austria (ISTA)) |
Deterministic Dynamic Maximal Matching in Sublinear Update Time Aaron Bernstein (New York University); Sayan Bhattacharya (University of Warwick); Peter Kiss (University of Vienna); Thatchaphol Saranurak (University of Michigan) |
A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire John Bostanci (Columbia University); Barak Nehoran (Princeton University); Mark Zhandry (NTT Research) |
Optimal Non-Oblivious Open Addressing Michael A. Bender (Stony Brook University); William Kuszmaul, Renfei Zhou (Carnegie Mellon University) |
||||||||
| 14:54 | Sum-of-Squares Lower Bounds for Coloring Random Graphs Aaron Potechin (University of Chicago); Jeff Xu (Carnegie Mellon University) |
Breaking the $O(mn)$-Time Barrier for Vertex-Weighted Global Minimum Cut Julia Chuzhoy, Ohad Trabelsi (Toyota Technological Institute at Chicago) |
Quantum One-Time Programs, Revisited Aparna Gupte, Jiahui Liu (MIT); Justin Raizes (CMU); Bhaskar Roberts (UC Berkeley); Vinod Vaikuntanathan (MIT) |
Optimal Static Dictionary with Worst-Case Constant Query Time Yang Hu (Tsinghua University); Jingxun Liang (CMU); Huacheng Yu (Princeton University); Junkai Zhang (Tsinghua University); Renfei Zhou (CMU) |
||||||||
| 15:12 | Fully dynamic biconnectivity in Õ(log² n) time Jacob Holm (University of Copenhagen); Wojciech Nadara (Technical University of Denmark and University of Warsaw); Eva Rotenberg (Technical University of Denmark); Marek Sokołowski (Max Planck Institute for Informatics) |
A bound on the quantum value of all compiled nonlocal games Alexander Kulpe (Ruhr University Bochum); Giulio Malavolta (Bocconi University); Connor Paddock (U Ottawa); Simon Schmidt, Michael Walter (Ruhr University Bochum) |
On the Hardness Hierarchy for the O(n √log n) Complexity in the Word RAM Dominik Kempa (Stony Brook University, USA); Tomasz Kociumaka (INSAIT, Sofia University “St. Kliment Ohridski”) |
|||||||||
| 15:30 | Parallel Repetition for $3$-Player $\mathsf{XOR}$ Games Amey Bhangale (UC Riverside); Mark Braverman (Princeton University); Subhash Khot (NYU); Yang Liu (IAS and CMU); Dor Minzer (MIT) |
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth Zhuan Khye Koh (Boston University); Omri Weinstein (The Hebrew University of Jerusalem); Sorrachai Yingchareonthawornchai (The Hebrew University of Jerusalem and ETH Zurich) |
Classical Commitments to Quantum States Sam Gunn (Berkeley); Yael Kalai, Anand Natarajan, Agi Villanyi (MIT) |
|||||||||
|
|
||||||||||||
| 15:46 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I + II
Session 3: Best Papers continued
|
||||||||||||
| 16:30 | Breaking the Sorting Barrier for Directed Single-Source Shortest Paths Ran Duan, Jiayi Mao (Tsinghua University); Xiao Mao (Stanford University); Xinkai Shu (Max Planck Institute for Informatics); Longhui Yin (Tsinghua University) |
|||||||||||
| 16:50 | Quasi-Linear Size PCPs with Small Soundness from HDX Mitali Bafna, Dor Minzer (MIT); Nikhil Vyas (Harvard); Zhiwei Yun (MIT) |
|||||||||||
|
|
||||||||||||
| 18:00-19:00 |
Online Poster Session
|
|||||||||||
|
|
||||||||||||
|
|
||||||||||||
| Tuesday June 24 | ||||||||||||
|
Congress Hall Sun I + II
Workshop B
|
Lounge Jupiter
Workshop C
|
Lounge Uranus
Workshop A
|
||||||||||
| 8:45-10:45 | ||||||||||||
|
|
||||||||||||
| 10:45 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I + II
Plenary talk
|
||||||||||||
| 11:15 |
TBD
|
|||||||||||
|
|
||||||||||||
| 12:15 |
Buffet Lunch (provided)
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 4A
|
Congress Hall Sun II
Session 4B
|
Lounge Jupiter
Session 4C
|
Lounge Uranus
Session 4D
|
|||||||||
| 14:00 | Optimality of Frequency Moment Estimation Mark Braverman (Princeton University); Or Zamir (Tel Aviv University) |
Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation Sitan Chen, Weiyuan Gong (Harvard University); Qi Ye, Zhihan Zhang (Tsinghua University) |
Multi-Parameter Mechanisms for Consumer Surplus Maximization Tomer Ezra (Harvard University); Daniel Schoepflin (Rutgers University); Ariel Shaulker (Weizmann Institute) |
|||||||||
| 14:18 | Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration Kiril Bangachev (Massachusetts Institute of Technology); Guy Bresler (MIT) |
Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu (Fudan University); Zhewei Wei (Renmin University of China) |
Single-copy stabilizer testing Marcel Hinsche (Freie Universität Berlin and IBM Quantum Zurich); Jonas Helsen (Centrum Wiskunde & Informatica (CWI) and QuSoft, Amsterdam) |
Approximation guarantees of Median Mechanism in $\mathbb{R}^d$ Nick Gravin, Jianhao Jia (Shanghai University of FInance and Economics, China) |
||||||||
| 14:36 | A sharp version of Talagrand's selector process conjecture and an application to rounding fractional covers Huy Tuan Pham (Institute for Advanced Study) |
Positive bias makes tensor-network contraction tractable Jiaqing Jiang, Jielun Chen (Caltech); Norbert Schuch (University of Vienna); Dominik Hangleiter (UC Berkeley) |
Monotone Contractions Eleni Batziou, John Fearnley, Spencer Gordon (University of Liverpool); Ruta Mehta (University of Illinois at Urbana-Champaign); Rahul Savani (University of Liverpool) |
|||||||||
| 14:54 | Disjoint connected dominating sets in pseudorandom graphs Nemanja Draganic (University of Oxford); Michael Krivelevich (Tel Aviv University) |
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness Elena Gribelyuk (Princeton University); Honghao Lin, David P. Woodruff (Carnegie Mellon University); Huacheng Yu (Princeton University); Samson Zhou (Texas A&M University) |
The state hidden subgroup problem and an efficient algorithm for locating unentanglement Adam Bouland (Stanford University); Tudor Giurgica-Tiron (Stanford); John Wright (The University of California, Berkeley) |
Faster Rates for No-Regret Learning in General Games via Cautious Optimism Ashkan Soleymani (MIT); Georgios Piliouras (Google DeepMind); Gabriele Farina (MIT) |
||||||||
| 15:12 | Minimum degree edge-disjoint Hamilton cycles in random directed graphs Asaf Ferber (University of California, Irvine); Adva Mond (King's College London) |
Efficient Algorithms and New Characterizations for CSP Sparsification Sanjeev Khanna (University of Pennsylvania); Aaron (Louie) Putterman, Madhu Sudan (Harvard University) |
Distributed Quantum Advantage for Local Problems Alkida Balliu (Gran Sasso Science Institute); Sebastian Brandt (CISPA Helmholtz Center for Information Security); Xavier Coiteux-Roy (Technical University of Munich); Francesco d'Amore (Bocconi University, BIDSA); Massimo Equi (Aalto University); François Le Gall (Nagoya University); Henrik Lievonen, Augusto Modanese (Aalto University); Dennis Olivetti (Gran Sasso Science Institute); Marc-Olivier Renou (Inria, Universitée Paris-Saclay, Ecole polytechnique); Jukka Suomela (Aalto University); Lucas Tendick, Isadora Veeren (Inria Paris-Saclay) |
Computational Lower Bounds for No-Regret Learning in Normal-Form Games Ioannis Anagnostides (Carnegie Mellon University); Alkis Kalavasis (Yale University); Tuomas Sandholm (Carnegie Mellon University) |
||||||||
| 15:30 | Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics Jason Gaitonde (MIT); Ankur Moitra (Massachusetts Institute of Technology, USA); Elchanan Mossel (MIT) |
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms Sepehr Assadi (University of Waterloo); Sanjeev Khanna (University of Pennsylvania); Aaron (Louie) Putterman (Harvard University) |
Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games Constantinos Daskalakis (EECS, MIT); Gabriele Farina, Maxwell Fishelson, Charilaos Pipis (MIT); Jon Schneider (Google Research) |
|||||||||
|
|
||||||||||||
| 15:46 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 5A
|
Congress Hall Sun II
Session 5B
|
Lounge Jupiter
Session 5C
|
Lounge Uranus
Session 5D
|
|||||||||
| 16:15 | The Structure of Catalytic Space: Capturing Randomness and Time via Compression James Cook (Toronto); Jiatu Li (Massachusetts Institute of Technology); Ian Mertz (University of Warwick); Edward Pyne (MIT) |
A $(2+\varepsilon)$-Approximation Algorithm for Metric k-Median Vincent Cohen-Addad (Google Research, France); Fabrizio Grandoni (IDSIA, USI-SUPSI); Euiwoong Lee (University of Michigan); Chris Schwiegelshohn (Aarhus University); Ola Svensson (EPFL) |
Asymptotic tensor rank is characterized by polynomials Matthias Christandl (University of Copenhagen); Koen Hoeberechts (University of Amsterdam); Harold Nieuwboer (University of Copenhagen); Peter Vrana (Budapest University of Technology and Economics); Jeroen Zuiddam (University of Amsterdam) |
|||||||||
| 16:33 | Constant-Cost Communication is not Reducible to k-Hamming Distance Yuting Fang (Ohio State University); Mika Göös, Nathaniel Harms (EPFL); Pooya Hatami (The Ohio State University) |
On approximability of the Permanent of PSD matrices Farzam Ebrahimnejad (University of Washington); Ansh Nagda (UC Berkeley); Shayan Oveis Gharan (University of Washington) |
Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes Louis Golowich (UC Berkeley); Ting-Chun Lin (UC San Diego) |
Computing moment polytopes of tensors with applications in algebraic complexity and quantum information Maxim van den Berg (University of Amsterdam and Ruhr-Universität Bochum); Matthias Christandl (University of Copenhagen); Vladimir Lysikov (Ruhr-Universität Bochum); Harold Nieuwboer (University of Copenhagen); Michael Walter (Ruhr-Universität Bochum); Jeroen Zuiddam (University of Amsterdam) |
||||||||
| 16:51 | Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity Simon Mackenzie (None); Abdallah Saffidine (unaffiliated) |
Rounding Large Independent Sets on Expanders Mitali Bafna (MIT); Jun-Ting Hsieh (Carnegie Mellon University); Pravesh Kothari (Princeton University and IAS) |
Good binary quantum codes with transversal CCZ gate Quynh T Nguyen (Harvard University) Joint talk with Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates Louis Golowich, Venkatesan Guruswami (UC Berkeley) |
On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications Joshua Grochow ( University of Colorado—Boulder); Youming Qiao (University of Technology Sydney) Joint talk with On the complexity of isomorphism problems for tensors, groups, and polynomials V: over commutative rings Joshua Grochow (University of Colorado Boulder); Youming Qiao (University of Technology Sydney); Katherine E. Stange (University of Colorado Boulder); Xiaorui Sun (University of Illinois Chicago) |
||||||||
| 17:09 | Lifting to bounded-depth and regular resolutions over parities via games Yaroslav Alekseev (Technion – Israel Institute of Technology); Dmitry Itsykson (Ben-Gurion University of the Negev) |
Optimal rounding for Sparsest Cut Alan Chang (Washington University in St. Louis); Assaf Naor, Kevin Ren (Princeton University) |
Pauli measurements are not optimal for single-copy tomography Jayadev Acharya, Abhilash Dharmavarapu (Cornell University); Yuhan Liu (Rice University); Nengkun Yu (Stony Brook University) |
Error-Correction of Matrix Multiplication Algorithms Shuichi Hirahara (National Institute of Informatics); Nobutaka Shimizu (Institute of Science Tokyo) |
||||||||
| 17:27 | Extractors for Samplable Distributions with Low Min-Entropy Marshall Ball (New York University); Ronen Shaltiel (University of Haifa); Jad Silbak (Northeastern University) |
A 5/4-Approximation for Two-Edge Connectivity Miguel Bosch Calvo (IDSIA, USI-SUPSI); Mohit Garg (Indian Institute of Science); Fabrizio Grandoni (IDSIA); Felix Hommelsheim (University of Bremen); Afrouz Jabal Ameli (TU Eindhoven); Alexander Lindermayr (University of Bremen) |
Quantum fault tolerance with constant-space and logarithmic-time overheads Quynh T Nguyen (Harvard University); Christopher A Pattison (California Institute of Technology) |
Matrix Chaos Inequalities and Chaos of Combinatorial Type Afonso S. Bandeira, Kevin Lucca, Petar Nizic-Nikolac (ETH Zurich); Ramon van Handel (Princeton University) |
||||||||
| 17:45 | Leakage-resilient extractors against number-on-forehead protocols Eshan Chattopadhyay (Cornell University); Jesse Goodman (UT Austin) |
Near-Optimal Dimension Reduction for Facility Location Lingxiao Huang (Nanjing University); Shaofeng H.-C. Jiang (Peking University); Robert Krauthgamer (Weizmann Institute of Science); Di Yue (Peking University) |
||||||||||
|
|
||||||||||||
| 18:30 |
Congress Hall Sun I
Estimathon
|
|||||||||||
|
|
||||||||||||
|
|
||||||||||||
| Wednesday June 25 | ||||||||||||
|
Congress Hall Sun I + II
Workshop C
|
Lounge Jupiter
Workshop D
|
Lounge Uranus
Workshop A
|
||||||||||
| 8:45-10:45 | ||||||||||||
|
|
||||||||||||
| 10:45 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I + II
Plenary talk
|
||||||||||||
| 11:15 |
TBD: TBD
|
|||||||||||
|
|
||||||||||||
| 12:15 |
Buffet Lunch (provided)
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 6A
|
Congress Hall Sun II
Session 6B
|
Lounge Jupiter
Session 6C
|
Lounge Uranus
Session 6D
|
|||||||||
| 14:00 | How to Construct Random Unitaries Fermi Ma (Simons Institute, UC Berkeley); Hsin-Yuan Huang (Google, Caltech) |
Counting random k-SAT near the satisfiability threshold Zongchen Chen, Aditya Lonkar (Georgia Institute of Technology); Chunyang Wang (Nanjing University); Kuan Yang (Shanghai Jiao Tong University); Yitong Yin (Nanjing University) |
Universal SNARGs for NP from Proofs of Completeness Zhengzhong Jin (Northeastern); Yael Kalai (MIT and MSR); Alex Lombardi (Princeton); Surya Mathialagan (MIT) |
Testing Support Size More Efficiently Than Learning Histograms Renato Ferreira Pinto Jr. (University of Waterloo); Nathaniel Harms (EPFL) |
||||||||
| 14:18 | High Rate Multivariate Polynomial Evaluation Codes Mrinal Kumar (TIFR); Harry Sha, Swastik Kopparty (University of Toronto) |
Rapid Mixing at the Uniqueness Threshold Xiaoyu Chen (Nanjing University); Zongchen Chen (Georgia Institute of Technology); Yitong Yin, Xinyuan Zhang (Nanjing University) |
Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness Liyan Chen (Tsinghua University); Cody Freitag, Zhengzhong Jin, Daniel Wichs (Northeastern) |
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model Sourav Chakraborty (Indian Statistical Institute, Kolkata, India); Eldar Fischer (Technion - Israel Institute of Technology); Arijit Ghosh (Indian Statistical Institute, Kolkata, India); Amit Levi (University of Haifa); Gopinath Mishra, Sayantan Sen (National University of Singapore) |
||||||||
| 14:36 | Tensor Concentration Inequalities: A Geometric Approach Afonso S. Bandeira (ETH Zurich); Sivakanth Gopi (Microsoft Research Redmond); Haotian Jiang (University of Chicago); Kevin Lucca (ETH Zurich); Thomas Rothvoss (University of Washington) |
Sharp Phase Transitions in Estimation with Low-Degree Polynomials Youngtak Sohn (Brown University); Alexander S. Wein (University of California, Davis) |
Succinct Non-interactive Arguments of Proximity Liyan Chen (Tsinghua University); Zhengzhong Jin (Northeastern); Daniel Wichs (Northeastern & NTT Research) |
Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning Deeparnab Chakrabarty (Dartmouth College); Xi Chen (Columbia University); Simeon Ristic (University of Pennsylvania); C. Seshadhri (University of California, Santa Cruz); Erik Waingarten (University of Pennsylvania) |
||||||||
| 14:54 | Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier Jun-Ting Hsieh (Carnegie Mellon University); Ting-Chun Lin (UCSD); Sidhanth Mohanty (MIT); Ryan O'Donnell (Carnegie Mellon University); Rachel Yun Zhang (MIT) |
Phase Transitions via Complex Extensions of Markov Chains Jingcheng Liu, Chunyang Wang, Yitong Yin, Yixiao Yu (Nanjing University) |
||||||||||
| 15:12 | Explicit Codes approaching Generalized Singleton Bound using Expanders Fernando Granha Jeronimo (UIUC); Tushant Mittal (Stanford University); Shashank Srivastava (DIMACS and IAS); Madhur Tulsiani (Toyota Technological Institute at Chicago, USA) |
Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses Brice Huang, Sidhanth Mohanty, Amit Rajaraman (MIT); David X Wu (UC Berkeley) |
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?) Lijie Chen (Miller Institute for Basic Research in Science, UC Berkeley); Ron Rothblum (Technion); Roei Tell (University of Toronto) |
Approximately counting and sampling Hamiltonian motifs in sublinear time Reut Levi (Reichman University); Talya Eden (Bar Ilan University); Dana Ron (Tel Aviv University); Ronitt Rubinfeld (MIT) |
||||||||
| 15:30 | List-Decoding Capacity Implies Capacity on the q-ary Symmetric Channel Francisco Pernice (MIT); Oscar Sprumont (School of Computer Science, University of Washington); Mary Wootters (Stanford University, USA) |
Sampling and Integration of Logconcave Functions by Algorithmic Diffusion Yunbum Kook, Santosh S. Vempala (Georgia Institute of Technology) |
A Zero-Knowledge PCP Theorem Tom Gur, Jack O'Connor (University of Cambridge); Nicholas Spooner (Cornell University) |
Stochastic Matching via In-n-Out Local Computation Algorithms Amir Azarmehr, Soheil Behnezhad, Alma Ghafari (Northeastern University); Ronitt Rubinfeld (MIT) |
||||||||
|
|
||||||||||||
| 15:46 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 7A
|
Congress Hall Sun II
Session 7B
|
Lounge Jupiter
Session 7C
|
Lounge Uranus
Session 7D
|
|||||||||
| 16:15 | Characterizing and Testing Principal Minor Equivalence of Matrices Abhranil Chatterjee (Indian Statistical Institute, Kolkata); Sumanta Ghosh (Chennai Mathematical Institute); Rohit Gurjar, Roshan Raj (IIT Bombay) |
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization Niv Buchbinder (Tel-Aviv University, Israel); Moran Feldman (University of Haifa) |
Learning the structure of any Hamiltonian from minimal assumptions Andrew Zhao (Sandia National Laboratories) |
|||||||||
| 16:33 | Primes via Zeros: interactive proofs for testing primality of natural classes of ideals Abhibhav Garg, Rafael Oliveira (University of Waterloo); Nitin Saxena (Indian Institute of Technology Kanpur) |
Learning the closest product state Ainesh Bakshi (MIT); John Bostanci (Columbia University); William Kretschmer (Simons Institute); Zeph Landau (UC Berkeley); Jerry Li (University of Washington); Allen Liu (MIT); Ryan O'Donnell (Carnegie Mellon University); Ewin Tang (UC Berkeley) |
History-Independent Concurrent Hash Tables Hagit Attiya (Technion); Michael Bender (Stony Brook University); Martin Farach-Colton (New York University); Rotem Oshman (Tel-Aviv University); Noa Schiller (Tel Aviv University) |
|||||||||
| 16:51 | Polynomial-Time PIT from (Almost) Necessary Assumptions Robert Andrews (University of Waterloo); Deepanshu Kush, Roei Tell (University of Toronto) |
Solving the Correlation Cluster LP in Nearly Linear Time Nairen Cao (New York University); Vincent Cohen-Addad (Google Research, France); Euiwoong Lee (University of Michigan); Shi Li (Nanjing University); David Rasmussen Lolck (University of Copenhagen); Alantha Newman (Université Grenoble Alpes); Mikkel Thorup (University of Copenhagen); Lukas Vogl (Ecole Polytechnique Federale de Lausanne); Shuyi Yan (University of Copenhagen); Hanwen Zhang (University of Copenhagen, Denmark) |
Improved bounds for testing low stabilizer complexity states Saeed Mehraban (Tufts University); Mehrdad Tahmasbi (UIUC) Joint talk with Polynomial-time tolerant testing stabilizer states Srinivasan Arunachalam, Arkopal Dutt (IBM Quantum) |
Online Locality Meets Distributed Quantum Computing Amirreza Akbari (Aalto University); Xavier Coiteux-Roy (Technical University of Munich & Munich Center for Quantum Science and Technology); Francesco d'Amore (Bocconi University & BIDSA); François Le Gall (Nagoya University); Henrik Lievonen (Aalto University); Darya Melnyk (TU Berlin); Augusto Modanese (Aalto University); Shreyas Pai (IIT Madras); Marc-Olivier Renou (Inria, Universitée Paris-Saclay, Ecole polytechnique); Václav Rozhoň (INSAIT); Jukka Suomela (Aalto University) |
||||||||
| 17:09 | Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets Albert Atserias (Universitat Politecnica de Catalunya); Iddo Tzameret (Imperial College London) |
Fully Dynamic k-Median with Near-Optimal Update Time and Recourse Sayan Bhattacharya, Martin Costa, Ermiya Farokhnejad (University of Warwick) |
Dimension Independent and Computationally Efficient Shadow Tomography Pulkit Sinha (Institute for Quantum Computing, School of Computer Science, University of Waterloo) |
Faster Distributed $\Delta$-Coloring via Ruling Subgraphs Yann Bourreau, Sebastian Brandt, Alexandre Nolin (CISPA - Helmholtz Center for Information Security) |
||||||||
| 17:27 | When Connectivity Is Hard, Random Walks Are Easy With Non-Determinism Dean Doron (Ben Gurion University); Edward Pyne (MIT); Roei Tell (University of Toronto); Ryan Williams (MIT) |
Dynamic Locality Sensitive Orderings in Doubling Metrics An La, Hung Le (University of Massachusetts, Amherst, USA) |
Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation Zongbo Bao (CWI & QuSoft); Philippe van Dordrecht (University of Amsterdam); Jonas Helsen (CWI & QuSoft) |
|||||||||
| 17:45 | Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification Sanjeev Khanna, Huan Li (University of Pennsylvania); Aaron (Louie) Putterman (Harvard University) |
Testing and learning structured quantum Hamiltonians Srinivasan Arunachalam, Arkopal Dutt (IBM); Francisco (CWI Amsterdam) |
||||||||||
|
|
||||||||||||
| 18:30 |
Congress Hall Sun I
Business Meeting
|
|||||||||||
|
|
||||||||||||
|
|
||||||||||||
| Thursday June 26 | ||||||||||||
|
Congress Hall Sun I + II
Workshop C
|
Lounge Jupiter
Workshop B
|
Lounge Uranus
Workshop D
|
||||||||||
| 8:45-10:45 | ||||||||||||
|
|
||||||||||||
| 10:45 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
| 11:15-12:15 |
Congress Hall Sun I + II
|
|||||||||||
|
|
||||||||||||
| 12:15 |
Buffet Lunch (provided)
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 8A
|
Congress Hall Sun II
Session 8B
|
Lounge Jupiter
Session 8C
|
Lounge Uranus
Session 8D
|
|||||||||
| 14:00 | Optimal Proof Systems for Complex Sets are Hard to Find Fabian Egidy, Christian Glaßer (Julius-Maximilians-Universität Würzburg) |
Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations Yuda Feng (Nanjing University); Yang Hu (Tsinghua University); Shi Li (Nanjing University); Ruilong Zhang (Technical University of Munich) |
Quantum Communication Advantage in TFNP Siddhartha Jain (University of Texas at Austin); Mika Göös (EPFL); Tom Gur (University of Cambridge); Jiawei Li (University of Texas at Austin) |
Tractable Agreement Protocols Natalie Collina, Surbhi Goel, Varun Gupta, Aaron Roth (University of Pennsylvania) |
||||||||
| 14:18 | Student-Teacher Constructive Separations and (Un)Provability in Bounded Arithmetic: Witnessing the Gap Stefan Grosser (McGill University); Marco Carmosino (IBM Research) |
The Cost of Consistency: Submodular Maximization with Constant Recourse Paul Duetting (Google); Federico Fusco (Sapienza University of Rome); Silvio Lattanzi (Google); Ashkan Norouzi-Fard (Google Zurich); Ola Svensson (EPFL); Morteza Zadimoghaddam (Google) |
On the Computational Power of QAC0 with Barely Superlinear Ancillae Anurag Anshu (Harvard University); Yangjing Dong, Fengning Ou, Penghui Yao (Nanjing University) |
Share-Based Fairness for Arbitrary Entitlements Moshe Babaioff (Hebrew University); Uriel Feige (Weizmann Institute) |
||||||||
| 14:36 | Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin Lijie Chen (University of California at Berkeley); Jiatu Li (Massachusetts Institute of Technology); Jingxun Liang (Carnegie Mellon University) |
Tight Results for Online Convex Paging Anupam Gupta (New York University, USA); Amit Kumar (IIT Delhi); Debmalya Panigrahi (Duke University) |
Efficient thermalization and universal quantum computing with quantum Gibbs samplers Cambyse Rouze (INRIA Saclay, IPP); Alvaro Alhambra (Instituto de Física Teórica - CSIC); Daniel Stilck França (University of Copenhagen) |
From signaling to interviews in random matching markets Maxwell Allman, Itai Ashlagi, Amin Saberi (Stanford University); Sophie H. Yu (University of Pennsylvania) |
||||||||
| 14:54 | Supercritical Tradeoffs for Monotone Circuits Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov (EPFL) |
Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum Enze Sun (The University of Hong Kong); Zhihao Gavin Tang (Shanghai University of Finance and Economics); Yifan Wang (Georgia Institute of Technology) |
The Jacobi Factoring Circuit: Quantum Factoring in Near-Linear Gates and Sublinear Space Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan (MIT); Katherine Van Kirk (Harvard) |
Metric Distortion of Small-group Deliberation Ashish Goel, Mohak Goyal (Stanford University); Kamesh Munagala (Duke University) |
||||||||
| 15:12 | Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman Susanna F. de Rezende (Lund University); Noah Fleming (Memorial University); Duri Andrea Janett, Jakob Nordström (University of Copenhagen and Lund University); Shuo Pang (University of Copenhagen) |
Single-Sample and Robust Online Resource Allocation Rohan Ghuge (Georgia Institute of Technology); Sahil Singla (Georgia Tech); Yifan Wang (Georgia Institute of Technology) |
Permutation Superposition Oracles for Quantum Query Lower Bounds Christian Majenz (DTU); Giulio Malavolta (Bocconi University); Michael Walter (Ruhr University Bochum) |
Constant-Factor EFX Exists for Chores Jugal Garg, Aniket Murhekar, John Qin (University of Illinois at Urbana-Champaign) |
||||||||
| 15:30 | Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification Josh Alman (Columbia University); Jingxun Liang (CMU) |
Adaptive Approximation Schemes for Matching Queues Alireza Amanihamedani (London Business School); Ali Aouad (Massachusetts Institute of Technology); Amin Saberi (Stanford University) |
QMA vs QCMA and Pseudorandomness Jiahui Liu (Fujitsu Research); Saachi Mutreja, Henry Yuen (Columbia University) |
Six Candidates Suffice to Win a Voter Majority Moses Charikar (Stanford University); Alexandra Lassota (Eindhoven University of Technology); Prasanna Ramakrishnan (Stanford University); Adrian Vetta (McGill University); Kangning Wang (Rutgers University) |
||||||||
|
|
||||||||||||
| 15:46 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 9A
|
Congress Hall Sun II
Session 9B
|
Lounge Jupiter
Session 9C
|
Lounge Uranus
Session 9D
|
|||||||||
| 16:15 | Time and Space Efficient Deterministic Decoders Joshua Cook (University Of Texas at Austin); Dana Moshkovitz (University of Texas at Austin) |
Discrepancy Algorithms for the Binary Perceptron Shuangping Li, Tselil Schramm (Stanford University); Kangjie Zhou (Columbia University) |
On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode-Collapse Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas (Yale University) |
The FPNP versus #P dichotomy for #EO Boning Meng, Juqiu Wang (Chinese Academy of Sciences); Mingji Xia (Chinese Academy of Sciences) |
||||||||
| 16:33 | Redundancy is All You Need Joshua Brakensiek, Venkatesan Guruswami (University of California, Berkeley) |
Entangled Mean Estimation in High Dimensions Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Sihan Liu (UCSD); Thanasis Pittas (UW Madison) |
Provably learning a multi-head attention layer Sitan Chen (Harvard University); Yuanzhi Li (Microsoft Research) |
Locally Sampleable Uniform Symmetric Distributions Daniel M. Kane, Anthony Ostuni (UC San Diego); Kewen Wu (UC Berkeley) |
||||||||
| 16:51 | Strong XOR Lemma for Information Complexity Pachara Sawettamalya, Huacheng Yu (Princeton University) |
SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications Ilias Diakonikolas (UW Madison); Sam Hopkins (MIT); Ankit Pensia (Simons Institute, UC Berkeley); Stefan Tiegel (ETH Zürich) |
Uncloneable quantum states are necessary as proofs and advice Rohit Chatterjee (National University of Singapore); Srijita Kundu (University of Waterloo); Supartha Podder (Stony Brook University) |
|||||||||
| 17:09 | Ideal Pseudorandom Codes Omar Alrabiah (University of California, Berkeley); Prabhanjan Ananth (University of California, Santa Barbara); Miranda Christ (Columbia University); Yevgeniy Dodis (NYU); Sam Gunn (UC Berkeley) |
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More Ilias Diakonikolas (UW Madison); Sam Hopkins (MIT); Ankit Pensia (Simons Institute, UC Berkeley); Stefan Tiegel (ETH Zürich) |
Omnipredicting Single-Index Models with Multi-Index Models Lunjia Hu (Harvard University); Kevin Tian (UT Austin); Chutong Yang (UNIVERSITY OF TEXAS AT AUSTIN) |
Learning quantum states prepared by shallow circuits in polynomial time Zeph Landau (UC Berkeley); Yunchao Liu (Harvard University) |
||||||||
| 17:27 | Improved PIR Schemes using Matching Vectors and Derivatives Fatemeh Ghasemi, Swastik Kopparty (University of Toronto); Madhu Sudan (Harvard) |
Learning the Sherrington-Kirkpatrick Model Even at Low Temperature Gautam Chandrasekaran, Adam Klivans (University of Texas at Austin) |
The 2-Token Theorem: Recognising History-Deterministic Parity Automata Efficiently Karoliina Lehtinen (CNRS, Aix-Marseille Université, LIS, Marseille, France); Aditya Prakash (University of Warwick, Coventry, UK) |
|||||||||
| 17:45 | A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities Joey Rivkin (Stanford); Paul Valiant (Purdue University); Gregory Valiant (Stanford) |
Oblivious Defense in ML Models: Backdoor Removal without Detection Shafi Goldwasser (UC Berkeley and MIT); Jonathan Shafer, Neekon Vafa, Vinod Vaikuntanathan (MIT) |
Reachability in One-Dimensional Pushdown Vector Addition Systems is Decidable Clotilde Bizière (Université de Bordeaux); Wojciech Czerwinski (University of Warsaw) |
|||||||||
|
|
||||||||||||
| 19:00-22:00 |
Klášterní Pivovar Strahov (Strahov Brewery)
Banquet
|
|||||||||||
|
|
||||||||||||
|
|
||||||||||||
| Friday June 27 | ||||||||||||
|
Congress Hall Sun I + II
TCS4All Workshop
|
||||||||||||
| 8:45-10:45 | ||||||||||||
|
|
||||||||||||
| 10:45 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I + II
Plenary talk
|
||||||||||||
| 11:15 |
TBD: TBD
|
|||||||||||
|
|
||||||||||||
| 12:15 |
Buffet Lunch (provided)
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 10A
|
Congress Hall Sun II
Session 10B
|
Lounge Jupiter
Session 10C
|
Lounge Uranus
Session 10D
|
|||||||||
| 14:00 | Cryptographic Characterization of Quantum Advantage Tomoyuki Morimae, Yuki Shirakawa (Kyoto University); Takashi Yamakawa (NTT, Kyoto University) |
Disjoint paths problem with group-expressable constraints Chun-Hung Liu (Texas A&M Univeristy); Youngho Yoo (Texas A&M University) |
Coboundary expansion of coset complexes Izhar Oppenheim (Ben-Gurion University); Tali Kaufman (Bar Ilan University); Shmuel Weinberger (University of Chicago) |
|||||||||
| 14:18 | Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits Damiano Abram, Giulio Malavolta (Bocconi University); Lawrence Roy (Aarhus University) |
Merge-width and First-Order Model Checking Jan Dreier (TU Wien); Szymon Torunczyk (University of Warsaw) |
Breaking the T^(2/3) Barrier for Sequential Calibration Yuval Dagan (Tel Aviv University); Constantinos Daskalakis (EECS, MIT); Maxwell Fishelson, Noah Golowich (MIT); Robert Kleinberg, Princewill Okoroafor (Cornell University) |
Matroid Products via Submodular Coupling Kristóf Bérczi, Boglárka Gehér, András Imolay (Eötvös Loránd University); László Lovász, Balázs Maga (HUN-REN Alfréd Rényi Institute of Mathematics); Tamás Schwarcz (Eötvös Loránd University) |
||||||||
| 14:36 | Protecting Computations Against Continuous Bounded-Communication Leakage Yuval Ishai (Technion); Yifan Song (IIIS, Tsinghua University and Shanghai Qi Zhi Institute) |
All-Pairs Shortest Paths with Few Weights per Node Amir Abboud (Weizmann Institute of Science and INSAIT); Nick Fischer (INSAIT); Ce Jin (MIT); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Zoe Xi (MIT) |
Almost Optimal PAC Learning for k-Means Vincent Cohen-Addad (Google Research, France); Silvio Lattanzi (Google); Chris Schwiegelshohn (Aarhus University) |
Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses Lin Chen, Yuchen Mao, Guochuan Zhang (Zhejiang University) |
||||||||
| 14:54 | A New Approach for LPN-based Pseudorandom Functions: Low-Depth and Key-Homomorphic Youlong Ding (The Hebrew University of Jerusalem); Aayush Jain (CMU); Ilan Komargodski (Hebrew University (Israel) and NTT Research (USA)) |
Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (University of Leeds); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai); Meirav Zehavi (Ben-Gurion University) |
Adaptive and oblivious statistical adversaries are equivalent Guy Blanc, Gregory Valiant (Stanford University) |
Smoothed analysis for graph isomorphism Benjamin Moore, Michael Anastos, Matthew Kwan (Institute of Science and Technology Austria) |
||||||||
| 15:12 | Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations Kiril Bangachev (Massachusetts Institute of Technology); Guy Bresler (MIT); Stefan Tiegel (ETH Zürich); Vinod Vaikuntanathan (MIT CSAIL) |
Subexponential Parameterized Algorithms for Hitting Subgraphs Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (University of Leeds); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai); Meirav Zehavi (Ben-Gurion University) |
On Reductions and Representations of Learning Problems in Euclidean Spaces Bogdan Chornomaz, Shay Moran, Tom Waknine (Technion) |
Statistical inference of a ranked community in a directed graph Dmitriy Kunisky (Johns Hopkins University); Daniel A. Spielman (Yale University); Alexander S. Wein (University of California, Davis); Xifan Yu (Yale University) |
||||||||
| 15:30 | Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy k-XOR Over Expanders Riddhi Ghosal (UCLA); Isaac M Hair (UCSB); Aayush Jain (CMU); Amit Sahai (UCLA) |
Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate k-clique counts faster Keren Censor-Hillel, Tomer Even (Technion); Virginia Vassilevska Williams (Massachusetts Institute of Technology) |
DNF Learning via Locally Mixing Random Walks Josh Alman (Columbia University); Shivam Nadimpalli (MIT); Shyamal Patel, Rocco A. Servedio (Columbia University) |
Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs Elchanan Mossel (MIT); Allan Sly (Princeton); Youngtak Sohn (Brown) |
||||||||
|
|
||||||||||||
| 15:46 |
Coffee Break
|
|||||||||||
|
|
||||||||||||
|
Congress Hall Sun I
Session 11A
|
Congress Hall Sun II
Session 11B
|
Lounge Jupiter
Session 11C
|
Lounge Uranus
Session 11D
|
|||||||||
| 16:15 | Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity Mitali Bafna (MIT); Karthik C. S. (Rutgers University); Dor Minzer (MIT) |
Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm Kim-Manuel Klein (University of Lübeck); Janina Reuter (University of Kiel) |
Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs Itai Boneh (Reichman University and University of Haifa); Shiri Chechik (Tel Aviv University); Shay Golan (Reichman University and University of Haifa); Shay Mozes (Reichman University); Oren Weimann (University of Haifa) |
Approximation Algorithms for the Geometric Multimatching Problem Shinwoo An, Eunjin Oh (POSTECH); Jie Xue (New York University Shanghai) |
||||||||
| 16:33 | Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs Hsien-Chih Chang, Jonathan Conroy (Dartmouth College); Hung Le (University of Massachusetts, Amherst, USA); Shay Solomon (Tel Aviv University); Cuong Than (University of Massachusetts Amherst) |
Constant Approximation of Fr\'echet Distance in Strongly Subquadratic Time Siu-Wing Cheng (Hong Kong University of Science and Technology); Haoqiang Huang (The Hong Kong University of Science and Technology); Shuo Zhang (Renmin University of China) |
||||||||||
| 16:51 | Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH Venkatesan Guruswami (UC Berkeley); Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Kewen Wu (UC Berkeley) |
Accelerated Optimization of Approximate Multi-Commodity Flows on Directed Graphs Li Chen (Independent); Andrei Graur, Aaron Sidford (Stanford University) |
Covering Approximate Shortest Paths with DAGs Sepehr Assadi (University of Waterloo); Gary Hoppenworth, Nicole Wein (University of Michigan) |
Sample-Optimal Private Regression in Polynomial Time Prashanti Anderson, Ainesh Bakshi, Mahbod Majid (MIT); Stefan Tiegel (ETH Zürich) |
||||||||
| 17:09 | A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends Karl Bringmann, Egor Gorbachev (Saarland University and Max Planck Institute for Informatics) |
Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices Adrian Vladu (CNRS & IRIF) |
How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs Jonathan Conroy (Dartmouth College); Arnold Filtser (Bar-Ilan University) |
Privately Evaluating Untrusted Black-Box Functions Ephraim Linder, Sofya Raskhodnikova, Adam Smith (Boston University); Thomas Steinke (Google Research) |
||||||||
| 17:27 | Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights Egor Gorbachev (Saarland University and Max Planck Institute for Informatics); Tomasz Kociumaka (INSAIT, Sofia University "St. Kliment Ohridski") |
Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods Ruichen Jiang, Aryan Mokhtari, Francisco Patitucci Perez (University of Texas at Austin) |
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Chaitanya Nalam, Thatchaphol Saranurak (University of Michigan); Sorrachai Yingchareonthawornchai (The Hebrew University of Jerusalem and ETH Zurich) |
On Differentially Private Linear Algebra Haim Kaplan, Yishay Mansour (Tel Aviv University and Google Research); Shay Moran (Technion and Google Research); Uri Stemmer (Tel Aviv University and Google Research); Nitzan Tur (Google Research) |
||||||||
| 17:45 | Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence Jakob Nogler (ETH Zurich); Adam Polak (Bocconi University); Barna Saha (University of California, San Diego); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu, Christopher Ye (University of California, San Diego) |
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations Joakim Blikstad (KTH Royal Institute of Technology & CWI Amsterdam); Yonggang Jiang (Max Planck Institute for Informatics and Saarland University); Sagnik Mukhopadhyay (University of Birmingham); Sorrachai Yingchareonthawornchai (The Hebrew University of Jerusalem and ETH Zurich) |
Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis Xin Lyu (UC berkeley); Kunal Talwar (Apple) |
|||||||||
|
|
||||||||||||
| The times listed in this table are in European Time. | ||||||||||||