cstheory.com

Longform Stories

Some Complexity Results for Robustness Verification for Binarized Neural Networks

13h ago·1 min read·79 words

Tractable Gap-Constraint Languages for Complex Event Recognition

13h ago·2 min read·327 words

Learning Augmented Exact Exponential Algorithms

13h ago·1 min read·166 words

Compact Geometric Representations of Hierarchies

13h ago·2 min read·261 words

On (Non-)Isomorphism of Self-Dual Lattices and Codes

13h ago·2 min read·276 words

Tangent Spheres and Integer Distances

13h ago·1 min read·177 words

Guarded Epoch Bloom Filters for Sliding-Window Membership

13h ago·2 min read·207 words

A Neural Network Framework for Geodesic-Like Curve Computation on Parametric Surfaces

13h ago·1 min read·115 words

Patnaik-Pearson intrinsic dimension for internal representations of neural networks

13h ago·2 min read·208 words

Depth Lower Bounds for ReLU Networks with Binary Inputs

13h ago·1 min read·194 words

On the Complexity of the Circuit Width Problem

1d ago·1 min read·169 words

High-Fidelity 3D Geometric Reconstruction of Pelvic Organs from MRI: A Hybrid Deep Learning and Iterative Optimization Approach

1d ago·2 min read·268 words

Blended Chart Surfaces: A Seamless Explicit Representation for Smooth Surface Fitting

1d ago·2 min read·267 words

Non-negative Matrix Factorisation with Topological Regularisation

1d ago·1 min read·141 words

Online Connectivity Augmentation

1d ago·1 min read·174 words

Agent Utilities over Generalized Voronoi Regions and their Gradients

1d ago·2 min read·220 words

Greedy Vector Balancing

1d ago·2 min read·314 words

Directed Reachability-Preserving Minimum Edge Cut: Approximation and Planar Hardness

1d ago·1 min read·178 words

A Counterexample to Wegner's Conjecture for Axis-Parallel Rectangles

1d ago·2 min read·210 words

Three Interviews

Jun 6·5 min read·975 words

Information-Theoretic Kuplex

Jun 5·1 min read·83 words

Efficient Computation of Distance Functions for Navigation Vector Fields in Lie Groups

Jun 5·2 min read·206 words

RedZeD: Computing persistent homology by Reduction to Zero Differentials

Jun 5·1 min read·70 words

Efficient Mean Curvature Computation on High-Dimensional Data Manifolds

Jun 5·2 min read·295 words

Analytic patch trees: branch interface inheritance and fractal dimension fields

Jun 5·1 min read·193 words

Bridging CAD and Data-Driven Design: Attributed Feature Graphs for Engineering Design

Jun 5·2 min read·234 words

Polynomial-time satisfiability for a special case of Positive$\wedge$Negative

Jun 5·1 min read·142 words

Quantum Algorithms for Triangle Cut Sparsification

Jun 5·1 min read·190 words

Quantum enhanced rare event discovery and sampling

Jun 5·1 min read·172 words

Temporal matching in trees

Jun 5·2 min read·235 words

A Class of Multipartite Entangled States Based on State Transitions

Jun 5·1 min read·125 words

STOC TheoryFest 2026 Online Poster Session – Call for Posters

Jun 4·1 min read·80 words

We're Computerizing and Don't Need You

Jun 4·7 min read·1209 words

Sharp Low-Degree Thresholds for Planted-vs-Planted Testing

Jun 4·1 min read·145 words

Token Rankings are Unforgeable Language Model Signatures

Jun 4·2 min read·204 words

Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

Jun 4·2 min read·224 words

Randomized separations in black-box TFNP

Jun 4·1 min read·78 words

Quantum Time Lower Bounds by Permutation Invariance

Jun 4·2 min read·251 words

Dispatches from the possibly last days of human relevance

May 28·7 min read·1388 words

Privately Estimating Monotone Statistics in Polynomial Time

May 28·1 min read·162 words

Quantum principal component analysis without eigenvector recovery

May 28·2 min read·263 words

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs

May 28·2 min read·269 words

A Deterministic Separation Lemma

May 28·1 min read·144 words

Gauge Geometry of Hodge Zero-Mode Transport in Parameter-Dependent Topological Data Analysis

May 28·2 min read·222 words

Disjunctive Sum of Squares

May 28·1 min read·191 words

A Fresh Look at Lamarckian Evolution and the Baldwin Effect

May 28·2 min read·256 words

Powers and Limitations of Synchronous Self-Assembly

May 28·1 min read·200 words

High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing

May 28·2 min read·208 words

Polynomial-time isomorphism test for groups with abelian Sylow subgroups

May 27·1 min read·121 words

2-ASP(Q) programs with weak constraints: Complexity and efficient implementation

May 27·1 min read·153 words

Where to Split and When to Charge: Optimal Route Construction from Customer Permutations in Electric Vehicle Routing

May 27·2 min read·254 words

Parsimonious Learning-Augmented Online Metric Matching

May 27·1 min read·142 words

Euclidean Steiner Shallow-Light Trees in Higher Dimensions

May 27·1 min read·73 words

On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions

May 27·2 min read·217 words

Improved Hardness Results for Nash Social Welfare, Budgeted Allocation and GAP via the Unique Games Conjecture

May 27·2 min read·210 words

Virtual-Memory Powersort

May 27·1 min read·143 words

Low Soundness Linearity Testing on the Half-Slice

May 27·2 min read·262 words

Only One Company Makes the Game Monopoly

May 26·7 min read·1361 words

The complexity of frugal digraph homomorphisms

May 26·1 min read·94 words

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting

May 26·2 min read·250 words

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs

May 26·2 min read·258 words

On the Complexity of Bilevel Independent Set Problem

May 26·1 min read·164 words

A computational phase transition for learning-to-sample from Ising models

May 26·2 min read·217 words

Approximate Algorithms for Chamfer Distance Under Translation

May 26·2 min read·206 words

A Note on Approximability of Densest At-Least-k-Subgraph

May 26·2 min read·232 words

TopoAlign: Topology-Aware Visual Representation Alignment

May 26·2 min read·215 words

A Parameterized Algorithm for Testing whether the Limit of a Diagram is Empty

May 26·1 min read·185 words

Rounding Almost Commuting Hamiltonians

May 26·1 min read·172 words

Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains

May 25·2 min read·284 words

Beyond the Half-Approximation: Fair and Efficient Online Class Matching

May 25·2 min read·247 words

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs

May 25·2 min read·269 words

Optimal Dimension-Free Sampling for Regularized Classification

May 25·2 min read·206 words

Dynamic Query Modification for Binary Locality Sensitive Hashing

May 25·2 min read·307 words

The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems

May 25·2 min read·277 words

Query Lower Bounds for Correlation Clustering under Memory Constraints

May 25·1 min read·156 words

On the Approximate Non-Deterministic Degree of Total Boolean Functions

May 25·2 min read·237 words

Probabilistically checkable proofs for the Existential Theory of the Reals

May 25·2 min read·216 words

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)

May 25·1 min read·158 words

Individual Experience vs. The Cochrane Review

May 20·5 min read·982 words

Lutris: Safe Composition of Broadcast and Consensus

May 20·1 min read·83 words

From Single-Shot Simplex to Chained Simplex

May 20·1 min read·81 words

More cool results about the complexity of distributions

May 18·1 min read·86 words

More efficient PBWT prefix-array access via batching

May 18·2 min read·253 words

Exploration of $k$-edge-deficient temporal graphs in linear time

May 18·2 min read·250 words

Complexity of Non-Log-Concave Sampling in Fisher Information

May 18·1 min read·164 words

Optimizing Line Segment Inspection with Limited-Range Drones

May 18·2 min read·211 words

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand

May 18·2 min read·210 words

On the parameterized complexity of Broadcast Independence and Broadcast Packing

May 18·2 min read·324 words

An improved boundary-focused adaptive quadtree algorithm for circle-polygon intersection area approximation

May 18·2 min read·210 words

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems

May 18·1 min read·155 words

One-Sided Differential Privacy

May 15·14 min read·2696 words

TCS for All Spotlight Workshop at STOC 2026: Conference registration grants and call for speaker nominations

May 15·1 min read·92 words

Upper Bounds for Symmetric Approximate Bounded Indistinguishability

May 14·1 min read·7 words

Min-Max Optimization Requires Exponentially Many Queries

May 14·1 min read·6 words

Topology-Preserving Neural Operator Learning via Hodge Decomposition

May 14·1 min read·7 words

Quantum state isomorphism problems for groups

May 14·1 min read·6 words

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size

May 14·1 min read·14 words

LFPL: Revisited and Mechanized

May 14·1 min read·4 words

Decision Tree Learning on Product Spaces

May 14·1 min read·6 words

Diversity of Extensions in Abstract Argumentation

May 14·1 min read·6 words

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem

May 14·1 min read·7 words

Polyhedral Instability Governs Regret in Online Learning

May 14·1 min read·7 words

PhD/Masters at Tennessee Tech University (apply by May 31, 2026)

May 12·1 min read·10 words

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity

May 12·1 min read·10 words

Towards infinite PCSP: a dichotomy for monochromatic cliques

May 12·1 min read·8 words

Multi-Prover Interactive Proof Systems with Leakage

May 12·1 min read·6 words

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

May 12·1 min read·10 words

The two clocks and the innovation window: When and how generative models learn rules

May 12·1 min read·14 words

Hardness Amplification for (Sparse) LPN

May 12·1 min read·5 words

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses

May 12·1 min read·12 words

Continuous Defensive Domination Problems

May 12·1 min read·4 words

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?

May 12·1 min read·13 words

Constant Inapproximability for Fisher Markets

May 12·1 min read·5 words

The Quantification Trap

May 11·1 min read·3 words

A Note on Non-Negative $L_1$-Approximating Polynomials

May 11·1 min read·6 words

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial

May 11·1 min read·13 words

Touring a Sequence of Orthogonal Polygons

May 11·1 min read·6 words

Coordinated Motion Planning is FPT on Discretized Simple Polygons

May 11·1 min read·9 words

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets

May 11·1 min read·11 words

Computing bases in Hermite normal form of lattices of integer relations

May 11·1 min read·11 words

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts

May 11·1 min read·9 words

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist

May 11·1 min read·9 words

CARMEN: CORDIC-Accelerated Resource-Efficient Multi-Precision Inference Engine for Deep Learning

May 11·1 min read·9 words

Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides

May 11·1 min read·15 words

When do we know someone has died

May 6·1 min read·7 words

Point Group Symmetry of Polyhedral Diagrams in Graphic Statics

Apr 29·1 min read·9 words

New Parameterized and Exact Exponential Time Algorithms for Strongly Connected Steiner Subgraph

Apr 29·1 min read·12 words

From Gödel incompleteness to the consistency of circuit lower bounds

Apr 29·1 min read·10 words

Testing Robustness of Temporal Transportation Networks via Interval Separators

Apr 29·1 min read·9 words

Two Efficient Message-passing Exclusive Scan Algorithms

Apr 29·1 min read·6 words

SimdQuickHeap: The QuickHeap Reconsidered

Apr 29·1 min read·4 words

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width

Apr 29·1 min read·9 words

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study

Apr 29·1 min read·10 words

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs

Apr 29·1 min read·7 words

Unrestrictions and concise secant varieties

Apr 29·1 min read·5 words

Beyond censorship resistance: hiding, simultaneous binding, and accountable last look

Apr 27·1 min read·10 words

Complexity Classes Arising from Circuits over Finite Algebraic Structures

Apr 24·1 min read·9 words

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches

Apr 24·1 min read·10 words

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability

Apr 24·1 min read·10 words

Efficient generation of expected-degree graphs via edge-arrivals

Apr 24·1 min read·7 words

A simple $(2+ε)$-approximation for knapsack interdiction

Apr 24·1 min read·6 words

Kernelization Bounds for Constrained Coloring

Apr 24·1 min read·5 words

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold

Apr 24·1 min read·14 words

A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations

Apr 24·1 min read·9 words

Characterizing Streaming Decidability of CSPs via Non-Redundancy

Apr 24·1 min read·7 words

Rabin has just passed away

Apr 22·1 min read·5 words

Freedom From Choice

Apr 22·1 min read·3 words

Greedy Routing in a Sequentially Grown One-Dimensional Random Graph

Apr 22·1 min read·9 words

Quantum embedding of graphs for subgraph counting

Apr 22·1 min read·7 words

Lions and Contamination: Trees and General Graphs

Apr 22·1 min read·7 words

Parity Tests with Ties

Apr 22·1 min read·4 words

Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems

Apr 22·1 min read·10 words

Qubit Routing for (Almost) Free

Apr 22·1 min read·5 words

Parameterized Capacitated Vertex Cover Revisited

Apr 22·1 min read·5 words

Local Depth-Based Corrections to Maxmin Landmark Selection for Lazy Witness Persistence

Apr 22·1 min read·11 words

Monotile kirigami

Apr 22·1 min read·2 words

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane

Apr 22·1 min read·12 words

May 26-29 at Columbia: Summer School on the Theory and Practice of Blockchain Consensus

Apr 20·1 min read·14 words

Walk the Marble Malls

Apr 20·1 min read·4 words

Faculty & Research Positions in Artificial Intelligence at Capital Normal University (apply by April 24, 2028)

Apr 17·1 min read·16 words

Structured Uncertainties

Apr 17·1 min read·2 words

Reverse-Robust Computation with Chemical Reaction Networks

Apr 17·1 min read·6 words

Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

Apr 17·1 min read·10 words

On the Expressive Power and Limitations of Multi-Layer SSMs

Apr 17·1 min read·9 words

A Hypergraph Container Method on Spread SAT: Approximation and Speedup

Apr 17·1 min read·10 words

Complexity of Fungal Automaton Prediction

Apr 17·1 min read·5 words

Explicit Constant-Alphabet Subspace Design Codes

Apr 17·1 min read·5 words

IQP circuits for 2-Forrelation

Apr 17·1 min read·4 words

The Parameterized Complexity of Coloring Mixed Graphs

Apr 17·1 min read·7 words

Postdoc at University of Antwerp (apply by June 1, 2026)

Apr 16·1 min read·10 words

APPROX 2026 Call for Papers

Apr 16·1 min read·5 words

Postdoc at West Virginia University (apply by May 31, 2026)

Apr 16·1 min read·10 words

Block-Based Pathfinding: A Minecraft System for Visualizing Graph Algorithms

Apr 16·1 min read·9 words

Max Cut with Small-Dimensional SDP Solutions

Apr 16·1 min read·6 words

Parallel Algorithms for Group Isomorphism via Code Equivalence

Apr 16·1 min read·8 words

NP-Hardness and a PTAS for the Pinwheel Problem

Apr 16·1 min read·8 words

Fast Time-Varying Contiguous Cartograms Using Integral Images

Apr 16·1 min read·7 words

Reachability Constraints in Variational Quantum Circuits: Optimization within Polynomial Group Module

Apr 16·1 min read·11 words

On the Decidability of Verification under Release/Acquire

Apr 16·1 min read·7 words

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model

Apr 16·1 min read·11 words

Lawler-Moore Speedups via Additive Combinatorics

Apr 16·1 min read·5 words

Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs

Apr 16·1 min read·11 words

Reticulating Splines

Apr 15·1 min read·2 words

PhD student at University of Salzburg (apply by May 6, 2026)

Apr 15·1 min read·11 words

Symmetric subrank and its border analogue

Apr 15·1 min read·6 words

Longest Common Extension of a Dynamic String in Parallel Constant Time

Apr 15·1 min read·11 words

Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertising

Apr 15·1 min read·8 words

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs

Apr 15·1 min read·7 words

Dequantizing Short-Path Quantum Algorithms

Apr 15·1 min read·4 words

The Parameterized Complexity of Vertex-Coloring Edge-Weighting

Apr 15·1 min read·6 words

Topology Understanding of B-Spline Surface/Surface Intersection with Mapper

Apr 15·1 min read·8 words

A Relativizing MIP for BQP

Apr 15·1 min read·5 words

From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index

Apr 15·1 min read·11 words

A complexity phase transition at the EPR Hamiltonian

Apr 15·1 min read·8 words

TCS+ talk: Wednesday, April 22 — Yichuan Wang, UC Berkeley

Apr 14·1 min read·10 words

Maximum Independent Sets in Disk Graphs with Disks in Convex Position

Apr 14·1 min read·11 words

Any 3D Scene is Worth 1K Tokens: 3D-Grounded Representation for Scene Generation at Scale

Apr 14·1 min read·14 words

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs

Apr 14·1 min read·10 words

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting

Apr 14·1 min read·9 words

The Borsuk number of a graph

Apr 14·1 min read·6 words

Complexity Theory meets Ordinary Differential Equations

Apr 14·1 min read·6 words

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic

Apr 14·1 min read·9 words

Differentially Private Verification of Distribution Properties

Apr 14·1 min read·6 words

Strips as Tokens: Artist Mesh Generation with Native UV Segmentation

Apr 13·1 min read·10 words

Speed Thrills: Visceral Demonstrations That Get Students Excited About Efficient Algorithms

Apr 13·1 min read·11 words

Packing Compact Subgraphs with Applications to Districting

Apr 13·1 min read·7 words

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs

Apr 13·1 min read·8 words

Parametric Shortest Paths in a Linearly Interpolated Graph

Apr 13·1 min read·8 words

Fast Isotopy Computation for T-Curves

Apr 13·1 min read·5 words

Planted clique detection and recovery from the hypergraph adjacency matrix

Apr 13·1 min read·10 words

Parameterized Complexity Of Representing Models Of MSO Formulas

Apr 13·1 min read·8 words

Revisiting Fair and Efficient Allocations for Bivalued Goods

Apr 10·1 min read·8 words

Vulnerability Abundance: A formal proof of infinite vulnerabilities in code

Apr 10·1 min read·10 words

Rapid mixing for high-temperature Gibbs states with arbitrary external fields

Apr 10·1 min read·10 words

Quantum Property Testing for Bounded-Degree Directed Graphs

Apr 10·1 min read·7 words

Exponential quantum advantage in processing massive classical data

Apr 10·1 min read·8 words

The Boolean surface area of polynomial threshold functions

Apr 10·1 min read·8 words

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid

Apr 10·1 min read·14 words

Differentially Private Language Generation and Identification in the Limit

Apr 10·1 min read·9 words

Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It

Apr 10·1 min read·13 words

postdoc at Nagoya University (apply by April 30, 2026)

Apr 9·1 min read·9 words

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems

Apr 9·1 min read·10 words

An Algebraic Introduction to Persistence

Apr 9·1 min read·5 words

The Josehedron: A space-filling plesiohedron based on the Fischer-Koch S Triply Periodic Minimal Surface

Apr 9·1 min read·14 words

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures

Apr 9·1 min read·9 words

How Does Machine Learning Manage Complexity?

Apr 9·1 min read·6 words

Multiple Planted Structures Below $\sqrt{n}$: An SoS Integrality Gap and an SQ Lower Bound

Apr 9·1 min read·14 words

Toward a Tractability Frontier for Exact Relevance Certification

Apr 9·1 min read·8 words

On the Price of Privacy for Language Identification and Generation

Apr 9·1 min read·10 words

Optimal Lower Bounds for Symmetric Modular Circuits

Apr 7·1 min read·7 words

Surface Quadrilateral Meshing from Integrable Odeco Fields

Apr 7·1 min read·7 words

Separator for $c$-Packed Segments and Curves

Apr 7·1 min read·6 words

Signotopes Induce Unique Sink Orientations on Grids

Apr 7·1 min read·7 words

VisACD: Visibility-Based GPU-Accelerated Approximate Convex Decomposition

Apr 7·1 min read·6 words

No Constant-Cost Protocol for Point--Line Incidence

Apr 7·1 min read·6 words

Expanders Meet Reed--Muller: Easy Instances of Noisy k-XOR

Apr 7·1 min read·8 words

Learning from Equivalence Queries, Revisited

Apr 7·1 min read·5 words

Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations

Apr 7·1 min read·7 words

Failure of the strong feasible disjunction property

Apr 7·1 min read·7 words

SHARC: Reference point driven Spherical Harmonic Representation for Complex Shapes

Apr 3·1 min read·10 words

Bipartite Exact Matching in P

Apr 3·1 min read·5 words

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization

Apr 3·1 min read·11 words

Topology-First B-Rep Meshing

Apr 3·1 min read·3 words

The edge of the asymptotic spectrum of tensors

Apr 3·1 min read·8 words

Near-Optimal Space Lower Bounds for Streaming CSPs

Apr 3·1 min read·7 words

Quantum polymorphism characterisation of commutativity gadgets in all quantum models

Apr 3·1 min read·10 words

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms

Apr 3·1 min read·11 words

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians

Apr 3·1 min read·10 words

King Chasing Problem in Chinese Chess is NP-hard

Apr 3·1 min read·8 words

Should Have Known Better

Apr 2·1 min read·4 words

TCS+ talk: Wednesday, April 8 — Rahul Ilango, MIT

Apr 2·1 min read·9 words

You Play to Win the Game

Mar 31·1 min read·6 words

On the Complexity of Determinations

Mar 31·1 min read·5 words

Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry

Mar 31·1 min read·12 words

Bribery's Influence on Ranked Aggregation

Mar 31·1 min read·5 words

Neural Approximation of Generalized Voronoi Diagrams

Mar 31·1 min read·6 words

Time Series Correlations and Kolmogorov Complexity: A Hausdorff Dimension Perspective

Mar 31·1 min read·10 words

Proximity Alert: Ipelets for Neighborhood Graphs and Clustering

Mar 31·1 min read·8 words

Automated Reencoding Meets Graph Theory

Mar 31·1 min read·5 words

The Ice Sheet State and Parameter Estimator (ICESEE) Library (v1.0.0): Ensemble Kalman Filtering for Ice Sheet Models

Mar 31·1 min read·17 words

NP-hardness of SVP in Euclidean Space

Mar 31·1 min read·6 words

Near-Optimal Bounds for Parameterized Euclidean k-means

Mar 31·1 min read·6 words

Proofdoors and Efficiency of CDCL Solvers

Mar 30·1 min read·6 words

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements

Mar 30·1 min read·13 words

Distances in Planar Graphs are Almost for Free!

Mar 30·1 min read·8 words

On merge-models

Mar 30·1 min read·2 words

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs

Mar 30·1 min read·12 words

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures

Mar 30·1 min read·17 words

Optimal b-Colourings and Fall Colourings in $H$-Free Graphs

Mar 30·1 min read·8 words

Dynamic Nearest-Neighbor Searching Under General Metrics in ${\mathbb R}^3$ and Its Applications

Mar 30·1 min read·12 words

Surfaces without quasi-isometric simplicial triangulations

Mar 30·1 min read·5 words

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness

Mar 30·1 min read·9 words

My Oxford Term

Mar 25·1 min read·3 words

Strong Chain Quality

Mar 23·1 min read·3 words

PhD Position at BITS × RMIT (apply by March 28, 2026)

Mar 20·1 min read·11 words

Cosma Shalizi Is Aware of All Internet Traditions

Mar 20·1 min read·8 words

Smaller Depth-2 Linear Circuits for Disjointness Matrices

Mar 17·1 min read·7 words

Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization

Mar 17·1 min read·9 words

Improved Online Hitting Set Algorithms for Structured and Geometric Set Systems

Mar 17·1 min read·11 words

The Counting General Dominating Set Framework

Mar 17·1 min read·6 words

The Compilability Thresholds of 2-CNF to OBDD

Mar 17·1 min read·7 words

Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time

Mar 17·1 min read·11 words

Minimal enclosing balls via geodesics

Mar 17·1 min read·5 words

Decision Quotient: A Regime-Sensitive Complexity Theory of Exact Relevance Certification

Mar 17·1 min read·10 words

Towards Parameterized Hardness on Maintaining Conjunctive Queries

Mar 17·1 min read·7 words

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

Mar 17·1 min read·13 words

On the Computational Hardness of Transformers

Mar 13·1 min read·6 words

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation

Mar 13·1 min read·11 words

Bounding the Fragmentation of B-Trees Subject to Batched Insertions

Mar 13·1 min read·9 words

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints

Mar 13·1 min read·11 words

Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Mar 13·1 min read·9 words

Fast and exact visibility on digitized shapes and application to saliency-aware normal estimation

Mar 13·1 min read·13 words

On the maximum number of tangencies among $1$-intersecting curves

Mar 13·1 min read·9 words

On strictly output sensitive color frequency reporting

Mar 13·1 min read·7 words

Space-Efficient Approximate Spherical Range Counting in High Dimensions

Mar 13·1 min read·8 words

Visibly Recursive Automata

Mar 13·1 min read·3 words

TCS+ talk: Wednesday, March 18 — Chris Gartland, UNC Charlotte

Mar 12·1 min read·10 words

Simple minimally unsatisfiable subsets of 2-CNFs

Mar 12·1 min read·6 words

Linear-Scaling Tensor Train Sketching

Mar 12·1 min read·4 words

Separating Oblivious and Adaptive Differential Privacy under Continual Observation

Mar 12·1 min read·9 words

Instruction set for the representation of graphs

Mar 12·1 min read·7 words

Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements

Mar 12·1 min read·8 words

Large chirotopes with computable numbers of triangulations

Mar 12·1 min read·7 words

The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory

Mar 12·1 min read·13 words

Huffman-Bucket Sketch: A Simple $O(m)$ Algorithm for Cardinality Estimation

Mar 12·1 min read·9 words

PhD position at Uppsala University (apply by April 7, 2026)

Mar 11·1 min read·10 words

Tetris is Hard with Just One Piece Type

Mar 11·1 min read·8 words

The Spanning Ratio of the Directed $Θ_6$-Graph is 5

Mar 11·1 min read·9 words

Simultaneous Embedding of Two Paths on the Grid

Mar 11·1 min read·8 words

Prismatoid Band-Unfolding Revisited

Mar 11·1 min read·3 words

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree

Mar 11·1 min read·8 words

d-QBF with Few Existential Variables Revisited

Mar 11·1 min read·6 words

Reinforced Generation of Combinatorial Structures: Ramsey Numbers

Mar 11·1 min read·7 words

A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation

Mar 11·1 min read·12 words

The framework to unify all complexity dichotomy theorems for Boolean tensor networks

Mar 11·1 min read·12 words

Has quantum advantage been achieved?

Mar 11·1 min read·5 words

Scott Aaronson’s View of my View About Quantum Computing

Mar 10·1 min read·9 words

Doctoral student at West Virginia University (apply by March 31, 2026)

Mar 10·1 min read·11 words

Benchmarking Culture

Mar 10·1 min read·2 words

Quantum information advantage based on Bell inequalities

Mar 10·1 min read·7 words

Intrinsic Sequentiality in P: Causal Limits of Parallel Computation

Mar 10·1 min read·9 words