Theory of Computing Report

@theory.report

[bridged from https://theory.report/ on the web: https://fed.brid.gy/web/theory.report ]

38 followers0 following420 stories

Longform Stories

TR26-097 | A symmetric determinantal lower bound for diagonal power sums\\ via polar degree | Karthik Sheshadri

15h ago·2 min read·312 words

Bayesian Probing on Graphs

1d ago·2 min read·235 words

The price of incrementality in k-center clustering

1d ago·2 min read·212 words

Complexity and Algorithms for Unary Translocation Distance

1d ago·2 min read·253 words

Kronecker products and iterated matrix multiplication

1d ago·1 min read·166 words

Engineering Scalable Distributed List Ranking

1d ago·1 min read·169 words

Quantum Cut Sparsifiers

1d ago·2 min read·225 words

Blow-ups of order types of positive density

1d ago·1 min read·147 words

Quantum Kravchuk Transform using $\mathfrak{su}(2)$ fast-forwarding

1d ago·1 min read·117 words

Fixed-Parameter Tractability of $t$-Uniform Hypergraphicality

1d ago·1 min read·185 words

Probabilistically Checking Quantum Proofs, with Interaction

1d ago·2 min read·258 words

The Objective Pursuit of Knowledge

1d ago·5 min read·962 words

TR26-096 | The dream XOR lemma is false | Emanuele Viola

1d ago·1 min read·36 words

Towards Implementable Quantum Divide and Conquer: A TSP Solver with Improved Exponential Base over Held-Karp

2d ago·2 min read·264 words

Online Span Minimization for Flexible Uniform Jobs

2d ago·2 min read·221 words

On the Hardness of Optimal Motion on Trees

2d ago·2 min read·261 words

Towards Tight Bounds for Streaming Attention

2d ago·2 min read·260 words

Earliest query answering over streamed trees

2d ago·2 min read·220 words

Odd Cycle Transversal in $P_k$-Free Graphs

2d ago·1 min read·181 words

Adjacency Spectral Radius Under Laplacian Sparsification: Deterministic and Probabilistic Bounds

2d ago·1 min read·134 words

HRsR: Hierarchical Rotation System Reconstruction

2d ago·1 min read·140 words

Tomography of quantum states with bounded extent

2d ago·2 min read·245 words

TR26-092 | Exponential Quantum Space Advantage for Approximating Max-$k$SAT in the Streaming Setting | Guangxu Yang

6d ago·1 min read·128 words

TR26-091 | Non-Levin NP-Hardness of Implicit MCSP and PAC Learning under Few Assumptions | Valentine Kabanets, Halley Goldberg, Mandar Juvekar

6d ago·2 min read·339 words

Lean 4 Machine-Verified Proof of P = NP via the Pedigree Polytope Membership Problem

Jun 3·2 min read·252 words

Ranked MSO-enumeration over compressed words

Jun 3·1 min read·170 words

The Grothendieck Constant is Less Than $\fracπ{2 \log (1+ \sqrt{2})} - 10^{-5}$

Jun 3·1 min read·51 words

Planar Perfect Matching Counting is as Hard as Determinants

Jun 3·1 min read·160 words

Towards Efficient Synthesis of Quantum Graph States by Fusing Graph Motifs

Jun 3·2 min read·246 words

Optimizing Explicit Unit-Distance Lower-Bound Certificates

Jun 3·2 min read·235 words

Scaling Laws for Neural-Network Quantum States

Jun 3·2 min read·231 words

Quantum-Classical Equivalence for AND-Functions

Jun 3·2 min read·206 words

Collision Resistance of Single-Layer Neural Nets

Jun 3·2 min read·216 words

APX-Hardness of Computing Lipschitz Constants for Multi-Parametric Quadratic Programs

Jun 3·1 min read·150 words

Aspects of Coherence in Dependence Logic

Jun 1·2 min read·293 words

Incremental BPE Tokenization

Jun 1·1 min read·172 words

Retriever Portfolios: A Principled Approach to Adaptive RAG

Jun 1·1 min read·157 words

Stepsize Hedging: an Alternative Mechanism for Accelerating Gradient Descent

Jun 1·1 min read·45 words

An Optimal Algorithm for Binary Closest String

Jun 1·1 min read·124 words

Neuro-symbolic Syntactic Parsing: Shaping a Neural Network with the CYK Algorithm

Jun 1·1 min read·121 words

Tree Containment Parameterized by Scanwidth

Jun 1·1 min read·177 words

How Many Slopes Does Polynomial Area Cost?

Jun 1·1 min read·120 words

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't

Jun 1·2 min read·203 words

Diffusion-Robust Optimization over Graphs

Jun 1·2 min read·224 words

Mathematics of the impossible: book is done

May 31·2 min read·221 words

AI is a Meteor. Don’t be a Dinosaur.

May 30·2 min read·336 words

TR26-089 | Near Optimal Extractors for Samplable Sources under Nondeterministic Hardness | Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Yunya Zhao

May 29·2 min read·240 words

Sharing different heartbeats

May 29·5 min read·916 words

TR26-088 | A digest of the work of Rothblum, Vadhan, and Wigderson (2013) | Oded Goldreich

May 29·1 min read·90 words

TR26-087 | Tight Bounds for Sketching Intersecting Sets, with Applications | Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Erasmo Tani, Andrew Tomkins

May 29·1 min read·187 words

On Language Generation in the Limit with Bounded Memory

May 29·2 min read·288 words

Elfs, transducers and quantum walks

May 29·1 min read·133 words

Low-degree estimation thresholds in planted hypergraphs and tensor PCA

May 29·2 min read·284 words

Quantum encodings that preserve persistent homology

May 29·1 min read·199 words

SWORD: Spectral Wasserstein Online Regime Detection in Dynamic Networks

May 29·2 min read·210 words

S2MDF: A Plug-And-Play Layer for Intersection-Free Multi-Object Signed Distance Fields

May 29·1 min read·159 words

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

May 29·1 min read·157 words

Research Fellow in AI Security and Alignment at MATS Research (apply by June 7, 2026)

May 28·1 min read·78 words

Making a talk, without and with AI

May 27·8 min read·1402 words

Authorship in the AI Age

May 27·3 min read·597 words

Two Erdos Problems on Points in the Plane and AI

May 24·7 min read·1371 words

The Branch and the Wish

May 23·1 min read·198 words

Exact Uniform L1 Spacing for Solow-Polasky Diversity on Lines and Ordered Pareto Fronts

May 22·2 min read·231 words

A geometric modelling framework to support the design of heterogeneous lattice structures with non-linearly varying geometry

May 22·2 min read·201 words

Maximum-Weight Two Boxes Symmetric Difference Problem

May 22·1 min read·124 words

A Simple Sub-Polynomial Degree Coboundary Expander

May 22·1 min read·119 words

Quoridor is PSPACE-Hard

May 22·1 min read·112 words

A sharp interaction-degree threshold for simulating QAOA

May 22·1 min read·91 words

Optimal Testing of Reed-Muller Codes with an Online Adversary

May 22·2 min read·292 words

Asymptotic Rank Speedup Theorems, Revisited

May 22·2 min read·245 words

On the Parameterized Complexity of Min-Sum-Radii

May 22·2 min read·304 words

Bifunction and Interlevel Delaunay Trifiltrations

May 22·1 min read·141 words

News for April 2026

May 19·8 min read·1425 words

TR26-082 | Pseudorandomness Beating the Hybrid Argument for Insensitive Algorithms | Dean Doron, David Zuckerman, Dana Moshkovitz, Justin Oh

May 17·3 min read·427 words

Can AI do Theory @ STOC 2026

May 17·1 min read·74 words

Scott Aaronson wins Trevisan Award? Prize? Medal? Statue?

May 17·3 min read·409 words

TR26-081 | Hard-to-Sample Distributions from Robust Extractors | Anthony Ostuni, Daniel Kane, Jackson Morris, Farzan Byramji

May 17·1 min read·184 words

TR26-080 | Maximum Matching and Related Problems in Catalytic Logspace | SRIJAN CHAKRABORTY, Samir Datta, Aryan Kusre, Partha Mukhopadhyay, Amit Sinhababu

May 17·2 min read·271 words

Fast Simplex on a Fixed View Schedule

May 17·1 min read·80 words

TR26-079 | On the LSH Distortion of Ulam and Cayley Similarities | Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Erasmo Tani

May 17·1 min read·173 words

TR26-078 | Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size | Susanna F. de Rezende, David Engström, Yassine Ghannane, Kilian Risse

May 17·1 min read·149 words

Two New Preprints: Balanced Separators for (Fat) Minor-Free Graphs

May 17·9 min read·1654 words

Linkage

May 15·3 min read·541 words

TR26-077 | Redundancy Is All You Need (for CSP Sparsification) | Joshua Brakensiek, Venkatesan Guruswami

May 15·2 min read·340 words

Extensive long-range magic in non-Abelian topological orders

May 15·1 min read·172 words

Min-1-Planarity is NP-Hard

May 15·1 min read·80 words

Non-Redundancy of Low-Arity Symmetric Boolean CSPs

May 15·2 min read·247 words

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model

May 15·1 min read·142 words

Fast and Robust Mesh Simplification for Generated and Real-World 3D Assets

May 15·2 min read·248 words

Meschers: Geometry Processing of Impossible Objects

May 15·1 min read·186 words

Enhanced and Efficient Reasoning in Large Learning Models

May 15·2 min read·311 words

The Complexity of Nested Reset Counter Systems

May 15·2 min read·243 words

Extending CDCL to disjunctions of parity equations

May 15·2 min read·250 words

On the Limits of PAC Learning of Networks from Opinion Dynamics

May 15·1 min read·172 words

Workshop “Frontiers in Complexity Lower Bounds”

May 13·1 min read·6 words

No more NYT cooperation: my dog-rape red line

May 13·1 min read·8 words

TR26-075 | On the Advantage of Adaptivity for Sampling with Cell Probes | Anthony Ostuni, Daniel Kane, Farzan Byramji, Jackson Morris

May 13·1 min read·21 words

Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach

May 13·1 min read·9 words

Layer-Based Width for PAFP

May 13·1 min read·4 words

A proximal gradient algorithm for composite log-concave sampling

May 13·1 min read·8 words

Performance bounds for nearest neighbor search with k-d trees

May 13·1 min read·9 words

Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing

May 13·1 min read·9 words

Two Results on Outer-String Graphs

May 13·1 min read·5 words

Feedback Set Problems on Bounded-Degree (Planar) Graphs

May 13·1 min read·7 words

Strong Inapproximability for a Promise Rank Problem

May 13·1 min read·7 words

Proof Systems Based on Structured Circuits

May 13·1 min read·6 words

TR26-072 | An Improved Construction of Variety-Evasive Subspace Families | Robert Andrews, Abhibhav Garg

May 10·1 min read·14 words

TR26-070 | Hard CNF Instances for Ideal Proof Systems | Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

May 10·1 min read·17 words

Fast decremental tree sums in forests

May 8·1 min read·6 words

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs

May 8·1 min read·10 words

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet

May 8·1 min read·9 words

Planar morphometry via functional shape data analysis and quasi-conformal mappings

May 8·1 min read·10 words

A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D

May 8·1 min read·10 words

Geometry-Aware Simplicial Message Passing

May 8·1 min read·4 words

Scalable GPU Construction of 3D Voronoi and Power Diagrams

May 8·1 min read·9 words

Partial Evidence Bench: Benchmarking Authorization-Limited Evidence in Agentic Systems

May 8·1 min read·9 words

An Improved Construction of Variety-Evasive Subspace Families

May 8·1 min read·7 words

On the Parameterized Approximability of (Mergeable) Sum of Radii Clustering

May 8·1 min read·10 words

The Rationality of the Language Machines

May 7·1 min read·6 words

Rigid homotopies for sampling from algebraic varieties: a Waring structure complexity model

May 7·1 min read·12 words

Faster Algorithms for Shortest Unique or Absent Substrings

May 7·1 min read·8 words

Block Permutation Routing on Ramanujan Hypergraphs for Fault-Tolerant Quantum Computing

May 7·1 min read·10 words

Online Orthogonal Vectors Revisited

May 7·1 min read·4 words

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces

May 7·1 min read·14 words

The Scaling Properties of Implicit Deductive Reasoning in Transformers

May 7·1 min read·9 words

Hard CNF Instances for Ideal Proof Systems

May 7·1 min read·7 words

Average Attention Transformers and Arithmetic Circuits

May 7·1 min read·6 words

Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete

May 7·1 min read·7 words

Robustness and Transferability of Pix2Geomodel for Bidirectional Facies Property Translation in a Complex Reservoir

May 6·1 min read·14 words

Quantum Multi-Level Estimation of Functionals of Discrete Distributions

May 6·1 min read·8 words

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth

May 6·1 min read·13 words

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs

May 6·1 min read·10 words

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases

May 6·1 min read·9 words

Computing Planar Convex Hulls with a Promise

May 6·1 min read·7 words

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time

May 6·1 min read·9 words

Optimal Union Probability Interval Is NP-Hard

May 6·1 min read·6 words

A Critical Comment on 'Entropy Computing: A Paradigm for Optimization in Open Photonic Systems'

May 6·1 min read·14 words

On the Induced Norms of Matrices and Grothendieck problems

May 6·1 min read·9 words

Exponential speedups in fault-tolerant processing of quantum experiments

May 5·1 min read·8 words

Witness Set: A Visibility Problem in $NP\cap XP$

May 5·1 min read·8 words

Spherical Geometrical Bases of Spherical Origami

May 5·1 min read·6 words

A greedy maximal sweepline algorithm for a Jordan curve

May 5·1 min read·9 words

Manifold k-NN: Accelerated k-NN Queries for Manifold Point Clouds

May 5·1 min read·9 words

Implicit Minimal Surfaces for Bijective Correspondences

May 5·1 min read·6 words

On Sampling Lower Bounds for Polynomials

May 5·1 min read·6 words

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions

May 5·1 min read·11 words

Lower Bounds for Approximate Sign Rank

May 5·1 min read·6 words

The Complexity of Stoquastic Sparse Hamiltonians

May 5·1 min read·6 words

Imperial Research Fellowships at Imperial College London (apply by June 15, 2026)

May 4·1 min read·12 words

TR26-068 | Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time | John Hitchcock

May 4·1 min read·14 words

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching

May 4·1 min read·9 words

Matroid Algorithms Under Size-Sensitive Independence Oracles

May 4·1 min read·6 words

The Impact of Approximation on Algorithmic Progress

May 4·1 min read·7 words

Brief announcement: A special case of maximum flow over time with network changes

May 4·1 min read·13 words

Set Parameterized Matching via Multi-Layer Hashing

May 4·1 min read·6 words

Unlearning Offline Stochastic Multi-Armed Bandits

May 4·1 min read·5 words

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs

May 4·1 min read·13 words

Upward-Planar Drawings with Bounded Span

May 4·1 min read·5 words

Smallest Enclosing Disk Queries Using Farthest-Point Voronoi Diagrams

May 4·1 min read·8 words

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank

May 4·1 min read·12 words

A Question

May 3·1 min read·2 words

TR26-066 | On Sampling Lower Bounds for Polynomials | Mohammad Mahdi Khodabandeh, Igor Shinkar

May 2·1 min read·14 words

TR26-065 | Partial Derivative Complexity of a Product of Linearly Independent Quadratics | Nir Shalmon, Amir Shpilka

May 2·1 min read·17 words

An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication

May 1·1 min read·10 words

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD

May 1·1 min read·15 words

Strongly Refuting Random CSP without Literals

May 1·1 min read·6 words

Toward a Characterization of Simulation Between Arithmetic Theories

May 1·1 min read·8 words

Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference

May 1·1 min read·12 words

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant

May 1·1 min read·11 words

Computing Equilibrium beyond Unilateral Deviation

May 1·1 min read·5 words

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size

May 1·1 min read·13 words

Distributed Santa Claus via Global Rounding

May 1·1 min read·6 words

Succinct Graph Representations and Algorithmic Applications

May 1·1 min read·6 words

STOC 2026 Student Travel Grants

Apr 30·1 min read·5 words

TR26-064 | Toward Improving Nisan’s PRG via Deweightization | ben chen, Gil Cohen, Dean Doron, Yuval Khaskelberg, Amnon Ta-Shma

Apr 30·1 min read·19 words

Linkage

Apr 30·1 min read·1 words

TR26-063 | When Majority Fails: Tight Bounds for Correlation Distillation Conjectures | Pritish Kamath, Ravi Kumar, Pasin Manurangsi

Apr 30·1 min read·18 words

TR26-062 | Toward a Characterization of Simulation Between Arithmetic Theories | Hunter Monroe

Apr 30·1 min read·13 words

A stellated tetrahedron that is probably not Rupert

Apr 30·1 min read·8 words

Small Independent Sets versus Small Separator in Geometric Intersection Graphs

Apr 30·1 min read·10 words

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases

Apr 30·1 min read·12 words

Strict Hierarchy for Quantum Channel Certification to Unitary

Apr 30·1 min read·8 words

Conic locus of inversive Poncelet circumcenter and two points of invariant circle power

Apr 30·1 min read·13 words

Calibrated Persistent Homology Tests for High-dimensional Collapse Detection

Apr 30·1 min read·8 words

The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem

Apr 30·1 min read·15 words

A proof of Jordan curve theorem based on the sweepline algorithm for trapezoidal decomposition of a polygon

Apr 30·1 min read·17 words

Hard-to-Sample Distributions from Robust Extractors

Apr 30·1 min read·5 words

En Route to a Standard QMA1 vs. QCMA Oracle Separation

Apr 30·1 min read·10 words

Groups, Expanders and Codes – Celebrating the 70’s birthday of Alex Lubotzky

Apr 28·1 min read·12 words

Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves

Apr 28·1 min read·18 words

Second gonality of smooth aCM curves on quartic surfaces in $\mathbb{P}^3$

Apr 28·1 min read·11 words

On the Hardness of Finding Temporally Connected Subgraphs of Any Size

Apr 28·1 min read·11 words

Constructive Separations from Gate Elimination

Apr 28·1 min read·5 words

Polynomial-time completion of phylogenetic tree sets

Apr 28·1 min read·6 words

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs

Apr 28·1 min read·11 words

Maximum Matching and Related Problems in Catalytic Logspace

Apr 28·1 min read·8 words

Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs

Apr 28·1 min read·12 words

Learning to Think from Multiple Thinkers

Apr 28·1 min read·6 words

P vs. NP animation

Apr 27·1 min read·4 words

An Argmin Events Calendar

Apr 27·1 min read·4 words

Dynamic Planar Graph Isomorphism is in DynFO

Apr 27·1 min read·7 words

Cuts and Gauges for Submodular Width

Apr 27·1 min read·6 words

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding

Apr 27·1 min read·13 words

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams

Apr 27·1 min read·13 words

Counting All Lattice Rectangles in the Square Grid in Near-Linear Time

Apr 27·1 min read·11 words

Boolean PCSPs through the lens of Fourier Analysis

Apr 27·1 min read·8 words

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings

Apr 27·1 min read·9 words

The Exact Replica Threshold for Nonlinear Moments of Quantum States

Apr 27·1 min read·10 words

From Simplex to Complex

Apr 26·1 min read·4 words

Workshops, Tutorials, and Community Events at COLT 2026

Apr 24·1 min read·8 words

TR26-061 | Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings | Ran Raz

Apr 23·1 min read·14 words

Algorithms and Complexity Workshop @ Warwick

Apr 23·1 min read·6 words

Engineering Architecture: A Syllabus?

Apr 23·1 min read·4 words

Latency cost of censorship resistance

Apr 23·1 min read·5 words

Deconstructing Simplex

Apr 23·1 min read·2 words

Formal Primal-Dual Algorithm Analysis

Apr 23·1 min read·4 words

Dynamic Construction of the Lovász Local Lemma

Apr 23·1 min read·7 words

A continuum of Künneth theorems for persistence modules

Apr 23·1 min read·8 words

Optimization of Constrained Quasiconformal Mapping for Origami Design

Apr 23·1 min read·8 words

Border subrank of higher order tensors and algebras

Apr 23·1 min read·8 words

A Quadratic Lower Bound for Noncommutative Circuits

Apr 23·1 min read·7 words

Cluster Vertex Deletion on Chordal Graphs

Apr 23·1 min read·6 words

A weighted angle distance on strings

Apr 23·1 min read·6 words

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Apr 23·1 min read·7 words

Designing Approximate Binary Trees for Trees

Apr 23·1 min read·6 words

Postdoc at Brown University (apply by April 30, 2026)

Apr 21·1 min read·9 words

On quantum functionals for higher-order tensors

Apr 21·1 min read·6 words

Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches

Apr 21·1 min read·12 words

On the volume of the elliptope and related metric polytopes

Apr 21·1 min read·10 words

Peeling Rotten Potatoes for a Faster Approximation of Convex Cover

Apr 21·1 min read·10 words

The Magnitude of Dominated Sets: A Pareto Compliant Indicator Grounded in Metric Geometry

Apr 21·1 min read·13 words

$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants

Apr 21·1 min read·10 words

Demystifying the unreasonable effectiveness of online alignment methods

Apr 21·1 min read·8 words

Metastability-Containing Turing Machines

Apr 21·1 min read·3 words

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks

Apr 21·1 min read·9 words

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers

Apr 21·1 min read·11 words

AI Fellow at Korea Institute for Advanced Study (apply by May 20, 2026)

Apr 20·1 min read·13 words

Online Trading as a Secretary Problem Variant

Apr 20·1 min read·7 words

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants

Apr 20·1 min read·10 words

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

Apr 20·1 min read·10 words

Towards Universal Convergence of Backward Error in Linear System Solvers

Apr 20·1 min read·10 words

Fast and Memory Efficient Multimodal Journey Planning with Delays

Apr 20·1 min read·9 words

Parallelizing the branch-and-bound with isomorphism pruning algorithm for classifying orthogonal arrays

Apr 20·1 min read·11 words

Finding Patient Zero via Low-Dimensional Geometric Embeddings

Apr 20·1 min read·7 words

Apple Peel Unfolding of Archimedean and Catalan Solids

Apr 20·1 min read·8 words

Accessible Quantum Correlations Under Complexity Constraints

Apr 20·1 min read·6 words

TR26-059 | Locally Computable High Independence Hashing | Yevgeniy Dodis, Shachar Lovett, Daniel Wichs

Apr 19·1 min read·14 words

TR26-058 | Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets | Zeyu Guo, Chong Shangguan, Roshan Raj, Zihan Zhang

Apr 19·1 min read·26 words

TR26-057 | Explicit Constant-Alphabet Subspace Design Codes | Rohan Goyal, Venkatesan Guruswami, Jun-Ting Hsieh

Apr 16·1 min read·14 words

Purposeful Predictions

Apr 13·1 min read·2 words

TR26-055 | Res$(\log)$ Proves Bounded-Depth Frege Lower Bounds | Ben Davis, Robert Robere

Apr 10·1 min read·13 words

Calibrated Games

Apr 10·1 min read·2 words

PhD student at Lund University (apply by April 15, 2026)

Apr 8·1 min read·10 words

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard

Apr 8·1 min read·12 words

Improved space-time tradeoff for TSP via extremal set systems

Apr 8·1 min read·9 words

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics

Apr 8·1 min read·9 words

Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences

Apr 8·1 min read·10 words

Distributed Quantum Property Testing with Communication Constraints

Apr 8·1 min read·7 words

$k$-Clustering via Iterative Randomized Rounding

Apr 8·1 min read·5 words

Learning $\mathsf{AC}^0$ Under Graphical Models

Apr 8·1 min read·5 words

Realizing Planar Linkages in Polygonal Domains

Apr 8·1 min read·6 words

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks

Apr 8·1 min read·13 words

TR26-051 | Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity | Yanyi Liu, Noam Mazor, Rafael Pass

Apr 7·1 min read·18 words

TR26-050 | Witness-Indistinguishable Arguments of Knowledge and One-Way Functions | Gal Arnon, Noam Mazor, Rafael Pass, Jad Silbak

Apr 7·1 min read·18 words

Unreal Is Here

Apr 7·1 min read·3 words

TR26-049 | No Constant-Cost Protocol for Point–Line Incidence | Mika Göös, Nathaniel Harms, Florian Richter, Anastasia Sofronova

Apr 7·1 min read·17 words

RANDOM 2026 Call For Papers

Apr 6·1 min read·5 words

Zero-Freeness of the Hard-Core Model with Bounded Connective Constant

Apr 6·1 min read·9 words

Optimal Pricing with Unreliable Signals

Apr 6·1 min read·5 words

Engineering Algorithms for Dynamic Greedy Set Cover

Apr 6·1 min read·7 words

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated

Apr 6·1 min read·7 words

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling

Apr 6·1 min read·8 words

Stochastic Function Certification with Correlations

Apr 6·1 min read·5 words

Online Drone Coverage of Targets on a Line

Apr 6·1 min read·8 words

Robust Learning with Optimal Error

Apr 6·1 min read·5 words

Non-Signaling Locality Lower Bounds for Dominating Set

Apr 6·1 min read·7 words

TR26-048 | Optimal Random Self-Reductions for All Linear Problems | Shuichi Hirahara, Nobutaka Shimizu

Apr 5·1 min read·14 words

TR26-047 | An $\Omega ( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures | Young Kun Ko

Apr 5·1 min read·24 words

TR26-046 | Black-Box Separation Between Multi-Collision Resistance and Collision Resistance | Xinyu Mao, Jiapeng Zhang

Apr 5·1 min read·15 words

TR26-045 | Using Hardness vs Randomness to Design Low-Space Algorithms | Edward Pyne, Roei Tell

Apr 5·1 min read·15 words

TR26-044 | Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling | Vahid Reza Asadi, Richard Cleve

Apr 5·1 min read·16 words

News for March 2026

Apr 3·1 min read·4 words

Arbitrary Geometry

Apr 3·1 min read·2 words

Estonian-Latvian Computer Science Theory Days 2026

Apr 3·1 min read·6 words

Polymath Plus AI

Apr 3·1 min read·3 words

Breadth-First Search Trees with Many or Few Leaves

Apr 2·1 min read·8 words

Asymptotically Optimal Sequential Testing with Heterogeneous LLMs

Apr 2·1 min read·7 words

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support

Apr 2·1 min read·8 words

Engineering Fully Dynamic Convex Hulls

Apr 2·1 min read·5 words

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points

Apr 2·1 min read·11 words

Stable algorithms cannot reliably find isolated perceptron solutions

Apr 2·1 min read·8 words

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields

Apr 2·1 min read·11 words

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds

Apr 2·1 min read·11 words

A General Framework for Computational Lower Bounds in Nontrivial Norm Approximation

Apr 2·1 min read·11 words

Learning and Generating Mixed States Prepared by Shallow Channel Circuits

Apr 2·1 min read·10 words

I helped the Pope's with his latest Encyclical (His Math Background Helped)

Apr 1·1 min read·12 words

TR26-043 | An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds | Deepanshu Kush

Apr 1·1 min read·16 words

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time

Apr 1·1 min read·11 words

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs

Apr 1·1 min read·6 words

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs

Apr 1·1 min read·9 words

Beyond Bits: An Introduction to Computation over the Reals

Apr 1·1 min read·9 words

Certifying and learning local quantum Hamiltonians

Apr 1·1 min read·6 words

Denoising data reduction algorithm for Topological Data Analysis

Apr 1·1 min read·8 words

Computing Topological Transition Sets for Line-Line-Circle Trisectors in $R^3$

Apr 1·1 min read·9 words

Near-Optimal Encodings of Cardinality Constraints

Apr 1·1 min read·5 words

Voronoi-Based Vacuum Leakage Detection in Composite Manufacturing

Apr 1·1 min read·7 words

A Strong Linear Programming Relaxation for Weighted Tree Augmentation

Apr 1·1 min read·9 words

The state of AI safety in four fake graphs

Mar 30·1 min read·9 words

PhD and Postdoc positions at Centre for Credible AI, Warsaw University of Technology (apply by April 19, 2026)

Mar 30·1 min read·18 words

TR26-042 | Entanglement-Dependent Error Bounds for Hamiltonian Simulation | Prateek Kulkarni

Mar 29·1 min read·11 words

(Senior) Research Fellow at National University of Singapore (apply by December 31, 2026)

Mar 27·1 min read·13 words

Bounded Independence Edge Sampling for Combinatorial Graph Properties

Mar 27·1 min read·8 words

Fast Spanning Tree Sampling in Broadcast Congested Clique

Mar 27·1 min read·8 words

Fast Iteration of Spaced k-mers

Mar 27·1 min read·5 words

The Geometry of Efficient Nonconvex Sampling

Mar 27·1 min read·6 words

Advances in Exact and Approximate Group Closeness Centrality Maximization

Mar 27·1 min read·9 words

Shortest Paths in Geodesic Unit-Disk Graphs

Mar 27·1 min read·6 words

Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution

Mar 27·1 min read·8 words

Inconsistency Probability of Sparse Equations over F2

Mar 27·1 min read·7 words

The Self-Replication Phase Diagram: Mapping Where Life Becomes Possible in Cellular Automata Rule Space

Mar 27·1 min read·14 words

The Poetics of Bureaucracy

Mar 26·1 min read·4 words

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics

Mar 26·1 min read·11 words

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth

Mar 26·1 min read·10 words

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier

Mar 26·1 min read·9 words

Coordinating Spot and Contract Supply in Freight Marketplaces

Mar 26·1 min read·8 words

Complexity of basic boolean operators for digital circuit design

Mar 26·1 min read·9 words

Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations

Mar 26·1 min read·12 words

Detection of local geometry in random graphs: information-theoretic and computational limits

Mar 26·1 min read·11 words

The Unsolvability of the Homeomorphism Problem

Mar 26·1 min read·6 words

Efficient Equilibrium Computation in Symmetric First-Price Auctions

Mar 26·1 min read·7 words

2nd Quantum Cambridge-Oxford-Warwick Colloquium (QCOW)

Mar 25·1 min read·5 words

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication

Mar 25·1 min read·9 words

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs

Mar 25·1 min read·9 words

Dynamic k-center clustering with lifetimes

Mar 25·1 min read·5 words

Dynamic Light Spanners in Doubling Metrics

Mar 25·1 min read·6 words

Testing Properties of Edge Distributions

Mar 25·1 min read·5 words

ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics

Mar 25·1 min read·12 words

Product Range Search Problem

Mar 25·1 min read·4 words

Simple but not Simpler: A Surface-Sliding Method for Finding the Minimum Distance between Two Ellipsoids

Mar 25·1 min read·15 words

Linear time single-source shortest path algorithms in Euclidean graph classes

Mar 25·1 min read·10 words

Covering and Partitioning Complex Objects with Small Pieces

Mar 25·1 min read·8 words

Information Transit Got the Wrong Man

Mar 24·1 min read·6 words

Critical window for approximate counting in dense Ising models

Mar 24·1 min read·9 words

Bollobás-Meir TSP Conjecture Holds Asymptotically

Mar 24·1 min read·5 words

Online Packing of Orthogonal Polygons

Mar 24·1 min read·5 words

Separators for intersection graphs of spheres

Mar 24·1 min read·6 words

Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Mar 24·1 min read·10 words

Classification of Non-redundancy of Boolean Predicates of Arity 4

Mar 24·1 min read·9 words

The Descriptive Complexity of Relation Modification Problems

Mar 24·1 min read·7 words

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding

Mar 24·1 min read·14 words

Topological Collapse: P = NP Implies #P = FP via Solution-Space Homology

Mar 24·1 min read·12 words

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds

Mar 23·1 min read·13 words

GeoLAN: Geometric Learning of Latent Explanatory Directions in Large Language Models

Mar 23·1 min read·11 words

Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

Mar 23·1 min read·8 words

Locality Sensitive Hashing in Hyperbolic Space

Mar 23·1 min read·6 words

Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells

Mar 23·1 min read·15 words

The Voronoi Diagram of Four Lines in $\mathbb{R}^3$

Mar 23·1 min read·8 words

On the size of k-irreducible triangulations

Mar 23·1 min read·6 words

Communication Complexity of Disjointness under Product Distributions

Mar 23·1 min read·7 words

Constrained Nonnegative Gram Feasibility is $\exists\mathbb{R}$-Complete

Mar 23·1 min read·6 words

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)

Mar 23·1 min read·8 words

A $100 dollar gift care could be legit. A $1000 is obviously a Scam. What should scammers do?

Mar 22·1 min read·18 words

Starting Today: Kazhdan Sunday seminar: “Boolean Functions, Hypercontractivity, and Applications”

Mar 22·1 min read·10 words

Five AI-related PhD/Postdoc Positions at Reykjavik University

Mar 20·1 min read·7 words

Complexity of Auctions with Interdependence

Mar 20·1 min read·5 words

Regret Bounds for Competitive Resource Allocation with Endogenous Costs

Mar 20·1 min read·9 words

Turnpike with Uncertain Measurements: Triangle-Equality ILP with a Deterministic Recovery Guarantee

Mar 20·1 min read·11 words

Central Triangulation under Parallel Flip Operations: The CG:SHOP Challenge 2026

Mar 20·1 min read·10 words

Hardness of High-Dimensional Linear Classification

Mar 20·1 min read·5 words

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation

Mar 20·1 min read·5 words

Axis-Aligned Relaxations for Mixed-Integer Nonlinear Programming

Mar 20·1 min read·6 words

On the Duality of Coverings in Hilbert Geometry

Mar 20·1 min read·8 words

Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs

Mar 20·1 min read·9 words

Learning Decision-Sufficient Representations for Linear Optimization

Mar 20·1 min read·6 words

Small World Models

Mar 16·1 min read·3 words

Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings

Mar 16·1 min read·11 words

Extending Exact Integrality Gap Computations for the Metric TSP

Mar 16·1 min read·9 words

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling

Mar 16·1 min read·13 words

Pairwise Exchanges of Freely Replicable Goods with Negative Externalities

Mar 16·1 min read·9 words

Weighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation

Mar 16·1 min read·11 words

Early Pruning for Public Transport Routing

Mar 16·1 min read·6 words

ExpanderGraph-128: A Novel Graph-Theoretic Block Cipher with Formal Security Analysis and Hardware Implementation

Mar 16·1 min read·13 words

Optimal Enumeration of Eulerian Trails in Directed Graphs

Mar 16·1 min read·8 words

Linkage with plum blossoms

Mar 15·1 min read·4 words

𝗣𝗼𝘀𝘁-𝗗𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀𝗵𝗶𝗽𝘀 at Indian Insti tute of Science (IISc), Bengaluru (apply by February 28, 2026)

Feb 11·1 min read·15 words

TR26-014 | A Fourier-Analytic Switching Lemma over F_p and the AC^0 Lower Bound for Generalized Parity | Yipin Wang

Feb 9·1 min read·19 words

I used to think historians in the future will have too much to work with. I could be wrong

Feb 9·1 min read·19 words

Induced Cycles of Many Lengths

Feb 9·1 min read·5 words

Circuit Diameter of Polyhedra is Strongly Polynomial

Feb 9·1 min read·7 words

Revisiting the Sliced Wasserstein Kernel for persistence diagrams: a Figalli-Gigli approach

Feb 9·1 min read·11 words

Graph-Based Nearest-Neighbor Search without the Spread

Feb 9·1 min read·6 words

Gromov-Wasserstein at Scale, Beyond Squared Norms

Feb 9·1 min read·6 words

Makespan Minimization in Split Learning: From Theory to Practice

Feb 9·1 min read·9 words

The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth

Feb 9·1 min read·15 words

Towards Efficient Data Structures for Approximate Search with Range Queries

Feb 9·1 min read·10 words

Danish Data Science Academy postdoc positions at University of Copenhagen (apply by March 4, 2026)

Feb 8·1 min read·15 words

TR26-013 | Quantum–Classical Equivalence for AND-Functions | Sreejata Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

Feb 8·1 min read·17 words

Trevisan Award for Expository Work

Feb 8·1 min read·5 words

Secrets of Intelligence Services

Feb 6·1 min read·4 words

News for January 2026

Feb 6·1 min read·4 words

The Quantum Message Complexity of Distributed Wake-Up with Advice

Feb 6·1 min read·9 words

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs

Feb 6·1 min read·7 words

Adaptive Hashing: Faster Hash Functions with Fewer Collisions

Feb 6·1 min read·8 words

Location-Aware Dispersion on Anonymous Graphs

Feb 6·1 min read·5 words

Competitive Analysis of Online Facility Assignment Algorithms on Discrete Grid Graphs: Performance Bounds and Remediation Strategies

Feb 6·1 min read·16 words

Certifiable Boolean Reasoning Is Universal

Feb 6·1 min read·5 words

Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm

Feb 6·1 min read·14 words

Challenges in Solving Sequence-to-Graph Alignment with Co-Linear Structure

Feb 6·1 min read·8 words

Tight FPT Approximations for Fair $k$-center with Outliers

Feb 6·1 min read·8 words

A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem

Feb 6·1 min read·13 words

On the Complexity of Vertex-Splitting Into an Interval Graph

Feb 5·1 min read·9 words

Minimizing Makespan in Sublinear Time via Weighted Random Sampling

Feb 5·1 min read·9 words

QuadRank: Engineering a High Throughput Rank

Feb 5·1 min read·6 words

Improved Sparse Recovery for Approximate Matrix Multiplication

Feb 5·1 min read·7 words

Simple 2-approximations for bad triangle transversals and some hardness results for related problems

Feb 5·1 min read·13 words

Incongruity-sensitive access to highly compressed strings

Feb 5·1 min read·6 words

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach

Feb 5·1 min read·12 words

The Needle is a Thread: Finding Planted Paths in Noisy Process Trees

Feb 5·1 min read·12 words

The matrix-vector complexity of $Ax=b$

Feb 5·1 min read·5 words

The Complexity of Min-Max Optimization with Product Constraints

Feb 5·1 min read·8 words