Mrinal Kumar; Ben Lee Volk. A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits.
Pasin Manurangsi; Aviad Rubinstein; Tselil Schramm. The Strongish Planted Clique Hypothesis and Its Consequences.
Nengkun Yu. Sample efficient identity testing and independence testing of quantum states.
Olaf Beyersdorff; Benjamin Böhm. Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution.
William Kretschmer. The Quantum Supremacy Tsirelson Inequality.
Moses Charikar; Shivam Garg; Deborah M. Gordon; Kirankumar Shiragur. A New Model for Ant Trail Formation and its Convergence Properties.
Kimberly Ding; S. Matthew Weinberg. Approximately Strategyproof Tournament Rules in the Probabilistic Setting.
Anup Bhattacharya; Arijit Bishnu; Gopinath Mishra; Anannya Upasana. Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!.
Alek Westover; William Kuszmaul. The Variable-Processor Cup Game.
Neta Dafni; Yuval Filmus; Noam Lifshitz; Nathan Lindzey; Marc Vinyals. Complexity measures on symmetric group and beyond.
Uri Meir. Comparison Graphs: a Unified Method for Uniformity Testing.
Shyam Narayanan; Michael Ren. Circular Trace Reconstruction.
Metger Tony; Vidick Thomas. Self-testing of a single quantum device under computational assumptions.
Xi Chen; Anindya De; Chin Ho Lee; Rocco A. Servedio; Sandip Sinha. Polynomial-time trace reconstruction in the low deletion rate regime.
Sebastien Bubeck; Niv Buchbinder; Christian Coester; Mark Sellke. Metrical Service Systems with Transformations.
Daniel Reichman; Pasin Manurangsi; Subhi Goel; Adam R. Klivans. Tight Hardness Results for Training Depth-2 ReLU Networks.
Pranjal Dutta; Nitin Saxena; Thomas Thierauf. A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization.
Alexander Golovnev; Alexander S. Kulikov; Ryan Williams. Circuit Depth Reductions.
Weiming Feng; Kun He; Xiaoming Sun; Yitong Yin. Dynamic inference in probabilistic graphical models.
Esty Kelman; Subhash Khot; Guy Kindler; Dor Minzer; Muli Safra. Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality.
Mark Braverman; Subhash Khot; Dor Minzer. On Rich 2-to-1 Games.
Pierre Fraigniaud; François Le Gall; Harumichi Nishimura; Ami Paz. Distributed Quantum Proofs for Replicated Data.
Mikito Nanashima. On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions.
Boaz Barak; Chi-Ning Chou; Xun Gao. Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits.
Joshua A. Grochow; Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness.
Gregory Rosenthal. Bounds on the QAC0 Complexity of Approximating Parity.
Noga Ron-Zewi; Ronen Shaltiel; Nithin Varma. Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists).
Jay Mardia. Is the space complexity of planted clique recovery the same as that of detection?.
Joshua Lau; Angus Ritossa. Algorithms and Hardness for Multidimensional Range Updates and Queries.
Dorit Aharonov; Alex B. Grilo. Two combinatorial MA-complete problems.
Irit Dinur; Yuval Filmus; Prahladh Harsha; Madhur Tulsiani. Explicit SoS lower bounds from high-dimensional expanders.
Nima Anari; Nathan Hu; Amin Saberi; Aaron Schild. Sampling Arborescences in Parallel.
Zachary Remscrim. Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines.
Jiabao Lin. On the Complexity of #CSP^d.
Jonathan Shafer; Guy N. Rothblum; Shafi Goldwasser; Amir Yehudayoff. Interactive Proofs for Verifying Machine Learning.
Yuval Filmus; Or Meir; Avishay Tal. Shrinkage under random projections, and cubic formula lower bounds in AC^0.
Omri Ben-Eliezer; Eldar Fischer; Amit Levi; Yuichi Yoshida. Ordered Graph Limits and Their Applications.
Ofer Grossman; Justin Holmgren. Error Correcting Codes for Uncompressed Messages.
Daniel Mitropolsky; Christos Papadimitriou; Robert Kleinberg. Total Functions in the Polynomial Hierarchy.
Noah Burrell; Grant Schoenebeck. Relaxing Common Belief for Social Networks.
Itai Ashlagi; Mark Braverman; Clayton Thomas; Geng Zhao. Tiered Random Matching Markets: Rank is Proportional to Popularity.
Geoffroy Couteau; Pooya Farshim; Mohammad Mahmoody. Black-Box Uselessness: Composing Separations in Cryptography.
Venkatesan Guruswami; Vinayak Kumar. Pseudobinomiality of the Sticky Random Walk.
Lior Eldar. Robust Quantum Entanglement at (nearly) Room Temperature.
Abhijit Mudigonda; Ryan Williams. Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers.
Spyros Angelopoulos. Online Search With a Hint.
Moshe Babaioff; Richard Cole; Jason Hartline; Nicole Immorlica; Brendan Lucier. Non-quasi-linear Agents in Quasi-linear Mechanisms.
Pál András Papp; Roger Wattenhofer. Sequential Defaulting in Financial Networks.
Ankit Garg; Robin Kothari; Praneeth Netrapalli; Suhail Sherif. No quantum speedup over gradient descent for non-smooth convex optimization.
Uma Girish; Ran Raz; Avishay Tal. Quantum versus Randomized Communication Complexity, with Efficient Players.
Kush Bhatia; Peter L. Bartlett; Anca Dragan; Jacob Steinhardt. Agnostic learning with unknown utilities.
Lijie Chen; Badih Ghazi; Ravi Kumar; Pasin Manurangsi. On Distributed Differential Privacy and Counting Distinct Elements.
Noam Solomon; Shay Solomon. A Generalized Matching Reconfiguration Problem.
Yuichi Yoshida; Samson Zhou. Sensitivity Analysis of the Maximum Matching Problem.
Vijay Vazirani; Mihalis Yannakakis. Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets.
Rajko Nenadov; Angelika Steger; Pascal Su. An O(n) time algorithm for finding Hamilton cycles with high probability.
Srinivasan Arunachalam; Supartha Podder. Communication memento: Memoryless communication complexity.
Michael B. Cohen; Aaron Sidford; Kevin Tian. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.
Binghui Peng; Zhao Song; Jan van den Brand; Omri Weinstein. Training (Overparametrized) Neural Networks in Near-Linear Time.
Jeremiah Blocki; Mike Cinkoske. A New Connection Between Node and Edge Depth Robust Graphs.
Anthony Leverrier; Vivien Londe; Gilles Zémor. Towards local testability for quantum coding.
Peter Dixon; A Pavan; N. V. Vinodchandran. Complete Problems for Multi-Pseudodeterministic Computations.
Yuval Emek; Shay Kutten; Yangguang Shi. Online Paging with a Vanishing Regret.
José Correa; Paul Dütting; Felix Fischer; Kevin Schewior; Bruno Ziliotto. Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility.
Ilan Komargodski; Elaine Shi. Differentially Oblivious Turing Machines.
Shivam Nadimpalli; Rocco A. Servedio; Anindya De. A new approach to quantitative correlation inequalities.
Benjamin Rossman. Shrinkage of Decision Lists and DNF Formulas.
Kunal Mittal; Ran Raz. Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines.
Stefan Dziembowski; Grzegorz Fabiański; Sebastian Faust; Siavash Riahi. Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma.
Sander Borst; Daniel Dadush; Neil Olver; Makrand Sinha. Majorizing Measures for the Optimizer.
Hedyeh Beyhaghi; Eva Tardos. Randomness and Fairness in Two-Sided Matching with Limited Interviews.
Justin Holmgren; Alexander S. Wein. Counterexamples to the Low-Degree Conjecture.