Rigidity for Monogamy-of-Entanglement Games
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
Online Learning and Bandits with Queried Hints
Improved Monotonicity Testing Over the Hypergrid via Hypercube Embedddings
Learning Reserve Prices in Second-Price Auctions
Symmetric Formulas for Products of Permutations
Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
Strategyproof Scheduling with Predictions
Learning versus Pseudorandom Generators in Constant Parallel Time
Exact Completeness of LP Hierarchies for Linear Codes
Proofs of Quantumness from Trapdoor Permutations
Exponential separations using guarded extension variables
Quantum algorithms and the power of forgetting
On Interactive Proofs of Proximity with Proof-Oblivious Queries
Matrix multiplication via matrix groups
A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems
Making Decisions under Outcome Performativity
Loss Minimization through the lens of Outcome Indistinguishability
The Time Complexity of Consensus Under Oblivious Message Adversaries
Necessary Conditions in Multi-Server Differential Privacy
On Oracles and Algorithmic Methods for Proving Lower Bounds
Beyond Worst-Case Budget-Feasible Mechanism Design
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
Unitary property testing lower bounds by polynomials
Incompressiblity and Next-Block Pseudoentropy
PPP-Completeness and Extremal Combinatorics
Beeping Shortest Paths via Hypergraph Bipartite Decomposition
Expander Decomposition in Dynamic Streams
Fractional certificates for bounded functions
Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP
Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More
Kolmogorov Complexity Characterizes Statistical Zero Knowledge
Vertex Sparsification for Edge Connectivity in Polynomial Time
On the computational hardness needed for quantum cryptography
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Rounding via Low Dimensional Embeddings
Certification with an NP Oracle
Unsplittable Euclidean Capacitated Vehicle Routing: A $(2+\epsilon)$-Approximation Algorithm
Efficient algorithms for certifying lower bounds on the discrepancy of random matrices
Matroid Partition Property and the Secretary Problem
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
Asynchronous Multi-Party Quantum Computation
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
Karchmer-Wigderson Games for Hazard-free Computation
Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
Garland’s Technique for Posets and High Dimensional Grassmannian Expanders
Bit Complexity of Jordan Normal Form and Spectral Factorization
Epic Fail: Emulators can tolerate some edge faults for free
On computing homological hitting sets
Decision Making under Miscalibration
Graph Searching with Predictions
Making Auctions Robust to Aftermarkets
HappyMap: A Generalized Multicalibration Method
Is Untrusted Randomness Helpful?
Worst-Case to Expander-Case Reductions
On disperser/lifting properties of the Index and Inner-Product functions
Counting Subgraphs in Somewhere Dense Graphs
Consensus Division in an Arbitrary Ratio
Quantum Proofs of Deletion for Learning with Errors
Differentially Private Continual Releases of Streaming Frequency Moment Estimations
Generalized Private Selection and Testing with High Confidence
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
List Agreement Expansion from Coboundary Expansion
TFNP Characterizations of Proof Systems and Monotone Circuits
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
What Can Cryptography Do For Decentralized Mechanism Design?
The Complexity of Infinite-Horizon General-Sum Stochastic Games
Black-box Constructive Proofs are Unavoidable
Online Pen Testing
False Consensus, Information Theory, and Prediction Markets
Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence
New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method
Recovery from Non-Decomposable Distance Oracles
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field
Rigidity in Mechanism Design and its Applications
Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
Secure Distributed Network Optimization Against Eavesdroppers
Private Counting of Distinct and k-Occurring Items in Time Windows
Is This Correct? Let's Check!
Efficiently Testable Circuits
Clustering Permutations: New Techniques with Streaming Applications
Certificate games
The Strength of Equality Oracles in Communication
Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
An Improved Lower Bound for Matroid Intersection Prophet Inequalities
Quantum majority vote
Downward self-reducibility in TFNP
On Low-End Obfuscation and Learning
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers
An Algorithmic Bridge Between Hamming and Levenshtein Distances
Lifting to Parity Decision Trees via Stifling
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly
Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds
Constant-depth sorting networks
Algorithms with More Granular Differential Privacy Guarantees
Bootstrapping Homomorphic Encryption via Functional Encryption
On Flipping the Fréchet distance
Communication Complexity of Inner Product in Symmetric Normed Spaces
Is it easier to count communities than find them?