Asaf Shapira and Lior Gishboliner.
Efficient Testing without Efficient Regularity
Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair and Michael Kowalczyk. A Complexity Trichotomy for $k$-Regular Asymmetric Spin Systems Using Number Theory
Paul Goldberg and Christos Papadimitriou. Towards a Unified Complexity Theory of Total Functions
Srikanth Srinivasan and Madhu Sudan. Local decoding and testing of polynomials over grids
Lucas Boczkowski, Ofer Feinerman, Amos Korman and Emanuele Natale. Limits for Rumor Spreading in stochastic populations
Yuqing Kong and Grant Schoenebeck. Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity
Keren Censor-Hillel, Ran Gelles and Bernhard Haeupler. Making Asynchronous Distributed Computations Robust to Noise
Avrim Blum and Yishay Mansour. On Price versus Quality
Pooya Hatami and Avishay Tal. Pseudorandom Generators for Low Sensitivity Functions
Aditya Bhaskara and Silvio Lattanzi. Non-Negative Sparse Regression and Column Subset Selection with $L_1$ Error
Shafi Goldwasser, Ofer Grossman and Dhiraj Holden. Pseudo-Deterministic Proofs
Aviad Rubinstein, Tselil Schramm and S. Matthew Weinberg. Computing exact minimum cuts without knowing the graph
Bill Fefferman and Cedric Lin. A Complete Characterization of Unitary Quantum Space
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal and Amit Kumar. Approximate Clustering with Same-Cluster Queries
Olaf Beyersdorff, Joshua Blinkhorn and Luke Hinde. Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs
Mark Braverman and Young Kun Ko. Information Value of the Game
Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meissner. Scheduling with Explorable Uncertainty
Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt and José Verschae. A Local-Search Algorithm for Steiner Forest
Mingda Qiao and Gregory Valiant. Learning Discrete Distributions from Untrusted Batches
Qingqing Huang, Sham M. Kakade, Weihao Kong and Gregory Valiant. Recovering Structured Probability Matrices
Itay Berman, Ron Rothblum and Vinod Vaikuntanathan. Zero-Knowledge Proofs of Proximity
Georgios Piliouras and Leonard Schulman. Learning Dynamics and the Co-Evolution of Competing Sexual Species
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru and David P. Woodruff. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff and Hongyang Zhang. Matrix Completion and Related Problems via Strong Duality
Greg Yang. A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma
Robert Legenstein, Wolfgang Maass, Christos Papadimitriou and Santosh Vempala. Long-term Memory and the Densest K-Subgraph Problem
Alessandro Chiesa and Tom Gur. Proofs of Proximity for Distribution Testing
Lior Eldar and Michael Ben-Or. A Quasi-Random Approach to Matrix Spectral Analysis
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh
and Meirav Zehavi. Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
Tom Gur, Govind Ramnarayan and Ron Rothblum. Relaxed Locally Correctable Codes
Jon Kleinberg and Manish Raghavan. Selection Problems in the Presence of Implicit Bias
Frieder Smolny, Karl Däubel, Aaron Bernstein, Max Klimm, Yann Disser and Torsten Mütze. Distance-preserving graph contractions
Rafael Frongillo and Bo Waggoner. An Axiomatic Study of Scoring Rule Markets
Oded Goldreich and Guy Rothblum. Simple doubly-efficient interactive proof systems for locally-characterizable sets
Amir Abboud and Aviad Rubinstein. Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
Dana Moshkovitz and Michal Moshkovitz. Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning
Noah Fleming, Robert Robere, Paul Beame, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov and Toniann Pitassi. Stabbing Planes
Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter and Avi Wigderson. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
Vedat Levi Alev, Nima Anari, Lap Chi Lau and
Shayan Oveis Gharan. Graph Clustering using Effective Resistance
Klim Efremenko, Ankit Garg, Rafael Oliveira and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity
Mark Braverman, Anat Ganor, Gillat Kol and Ran Raz. A Candidate for a Strong Separation of Information and Communication
Pravesh K Kothari and Roi Livni. Learning by Refuting
Victor Balcer
and Salil Vadhan. Differential Privacy on Finite Computers
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch and Virginia Williams. Fine-grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian and Makrand Sinha. Edge Estimation with Independent Set Oracles
Yishay Mansour, Aleksandrs Slivkins and Zhiwei Steven Wu. Competing bandits: learning under competition
Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin and Stefano Tessaro. Foundations of Homomorphic Secret Sharing
Eric Allender, Joshua A. Grochow,
Dieter van Melkebeek, Cristopher Moore and Andrew Morgan. Minimum Circuit Size, Graph Isomorphism, and Related Problems
Josh Alman and Virginia Vassilevska Williams. Further limitations of the known approaches for matrix multiplication
Srinivasan Arunachalam, Jop Briet
and Carlos Palazuelos. Quantum Query Algorithms are Completely Bounded Forms
Yuqing Kong
and Grant Schoenebeck. Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case