| Title | Authors |
| Giant Components in Random Temporal Graphs | Ruben Becker (Ca’ Foscari University of Venice, Italy), Arnaud Casteigts (LaBRI, University of Bordeaux, France), Pierluigi Crescenzi (Gran Sasso Science Institute, L’Aquila, Italy), Bojana Kodric (Ca’ Foscari University of Venice, Italy), Michael Raskin (LaBRI, University of Bordeaux, France), Malte Renken (Technical University of Berlin, Germany), Viktor Zamaraev (University of Liverpool, UK) |
| On Connectivity in Random Graph Models with Limited Dependencies | Johannes Lengler (ETH Zurich), Anders Martinsson (ETH Zurich), Kalina Petrova (ETH Zurich), Patrick Schnider (ETH Zurich), Raphael Steiner (ETH Zurich), Simon Weber (ETH Zurich), Emo Welzl (ETH Zurich) |
| Synergy between Circuit Obfuscation and Circuit Minimization | Russell Impagliazzo (University of California, San Diego), Valentine Kabanets (Simon Fraser University), Ilya Volkovich (Boston College) |
| Interactive Error Correcting Codes: New Constructions and Impossibility Bounds | Meghal Gupta (UC Berkeley), Rachel Yun Zhang (MIT) |
| Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees | Charilaos Efthymiou (University of Warwick), Thomas P. Hayes (University at Buffalo), Daniel Stefankovic (University of Rochester), Eric Vigoda (University of California, Santa Barbara) |
| Superpolynomial Lower Bounds for Learning Monotone Classes | Nader Bshouty (Technion) |
| An embarrassingly parallel optimal-space cardinality estimation algorithm | Emin Karayel (Technische Universität München, Germany) |
| Sampling and Certifying Symmetric Functions | Yuval Filmus (Technion – Israel Institute of Technology), Itai Leigh (Tel-Aviv University; University of Copenhagen), Artur Riazanov (EPFL), Dmitry Sokolov (EPFL) |
| Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes | Huck Bennett (Oregon State University), Chris Peikert (University of Michigan (Ann Arbor)) |
| Perfect Sampling for Hard Spheres from Strong Spatial Mixing | Konrad Anand (Queen Mary, University of London), Andreas Göbel (Hasso Plattner Institute, University of Potsdam), Marcus Pappik (Hasso Plattner Institute, University of Potsdam), Will Perkins (Georgia Institute of Technology) |
| Subset Sum in time $2^{n/2} / poly(n)$ | Xi Chen (Columbia University), Yaonan Jin (Columbia University), Tim Randolph (Columbia University), Rocco A. Servedio (Columbia University) |
| On Optimization and Counting of Non-Broken Bases of Matroids | Dorna Abdolazimi (University of Washington), Kasper Lindberg (University of Washington), Shayan Oveis Gharan (University of Washington) |
| Low-Degree Testing Over Grids | Prashanth Amireddy (Harvard University), Srikanth Srinivasan (Aarhus University), Madhu Sudan (Harvard University) |
| Improved Local Computation Algorithms for Constructing Spanners | Rubi Arviv (Efi Arazi School of Computer Science, Reichman University), Lily Chung (MIT), Reut Levi (Efi Arazi School of Computer Science, Reichman University), Edward Pyne (MIT) |
| Classical simulation of one-query quantum distinguishers | Andrej Bogdanov (University of Ottawa), Tsun Ming Cheung (McGill University), Krishnamoorthy Dinesh (Indian Institute of Technology, Palakkad), John C. S. Lui (The Chinese University of Hong Kong) |
| On the Power of Regular and Permutation Branching Programs | Chin Ho Lee (Harvard University), Edward Pyne (MIT), Salil Vadhan (Harvard University) |
| Private Data Stream Analysis for Universal Symmetric Norm Estimation | Vladimir Braverman (Rice University), Joel Manning (Carnegie Mellon University), Zhiwei Steven Wu (Carnegie Mellon University), Samson Zhou (UC Berkeley and Rice University) |
| Testing versus estimation of graph properties, revisited | Lior Gishboliner (ETH Zurich), Nick Kushnir (Tel Aviv University), Asaf Shapira (Tel Aviv University) |
| Efficient Interactive Proofs for Non-Deterministic Bounded Space | Joshua Cook (University of Texas at Austin), Ron Rothblum (Technion) |
| On the Complexity of Triangle Counting using Emptiness Queries | Arijit Bishnu (Indian Statistical Institute, Kolkata, India), Arijit Ghosh (Indian Statistical Institute, Kolkata, India), Gopinath Mishra (University of Warwick, UK) |
| Fine Grained Analysis of High Dimensional Random Walks | Roy Gotlib (Bar-Ilan University), Tali Kaufman (Bar-Ilan University) |
| A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble | Venkatesan Guruswami (University of California, Berkeley), Shilun Li (University of California, Berkeley) |
| NP-hardness of Almost Coloring Almost 3-Colorable Graphs | Yahli Hecht (Tel Aviv University), Dor Minzer (MIT), Muli Safra (Tel Aviv University) |
| Extracting Mergers and Projections of Partitions | Swastik Kopparty (University of Toronto), Vishvajeet N (University of Edinburgh) |
| Rapid mixing of global Markov chains via spectral independence: the unbounded degree case | Antonio Blanca (Pennsylvania State University), Xusheng Zhang (Pennsylvania State University) |
| The full rank condition for sparse random matrices | Amin Coja-Oghlan (TU Dortmund), Jane Gao (University of Waterloo), Max Hahn-Klimroth (TU Dortmund University), Joon Lee (EPFL), Noela Muller (Eindhoven University of Technology), Maurice Rolvien (TU Dortmund) |
| Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE | Joshua Cook (University Of Texas at Austin), Dana Moshkovitz (UT Austin) |
| Robustness for Space-Bounded Statistical Zero Knowledge | Eric Allender (Rutgers University), Jacob Gray (University of Massachusetts), Saachi Mutreja (University Of California, Berkeley), Harsha Tirumala (Rutgers University), Pengxiang Wang (University of Michigan) |
| On Constructing Spanners from Random Gaussian Projections | Sepehr Assadi (Rutgers University), Michael Kapralov (EPFL), Huacheng Yu (Princeton University) |
| Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance | Vikrant Ashvinkumar (Rutgers University), Sepehr Assadi (Rutgers University), Chengyuan Deng (Rutgers University), Jie Gao (Rutgers University), Chen Wang (Rutgers University) |
| How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity | Jeremiah Blocki (Purdue University), Elena Grigorescu (Purdue University), Tamalika Mukherjee (Purdue University), Samson Zhou (UC Berkeley and Rice University) |
| Fast Decoding of Explicit almost Optimal $\epsilon$-balanced $q$-ary Codes and Fast Approximation of Expanding $k$-CSPs | Fernando Granha Jeronimo (IAS) |
| Directed Poincaré Inequalities and $L^1$ Monotonicity Testing of Lipschitz Functions | Renato Ferreira Pinto Jr. (University of Waterloo) |
| Bias Reduction for Sum Estimation | Talya Eden (Bar Ilan University), Jakob Houen (University of Copenhagen), Shyam Narayanan (Massachusetts Institute of Technology), Will Rosenbaum (Amherst College), Jakub Tƒõtek (University of Copenhagen) |
| On the Composition of Randomized Query Complexity and Approximate Degree | Sourav Chakraborty (Indian Statistical Institute, Kolkata), Chandrima Kayal (Indian Statistical Institute, Kolkata), Rajat Mittal (Indian Institute of Technology Kanpur), Manaswi Paraashar (Aarhus University), Swagato Sanyal (IIT Kharagpur), Nitin Saurabh (International Institute of Information Technology, Hyderabad) |
| Sampling from the Random Cluster model on random regular graphs at all temperatures via Glauber dynamics | Andreas Galanis (University of Oxford), Leslie Ann Goldberg (University of Oxford), Paulina Smolarova (University of Oxford) |
| Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms | Karthik Gajulapalli (Georgetown University), Alexander Golovnev (Georgetown University), Satyajeet Nagargoje (Georgetown University), Sidhant Saraogi (Georgetown University) |
| Testing Connectedness of Images | Piotr Berman, Meiram Murzabulatov (Nazarbayev University, Kazakhstan), Sofya Raskhodnikova (Boston University), Dragos Ristache (Boston University) |
RANDOM: THE CONFERENCE 