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?