Counterexample
AI-Assisted Channel Separates Zero Capacity from PPT and Antidegradability
Chengkai Zhu, Xin Wang · frontier LLM modelsRead report →
Open problems in Theoretical Computer Science
To illuminate the frontier of theoretical computer science and accelerate progress on the questions that shape it.
Featured News
Open problems
Design and analysis of algorithmsGraph algorithms analysis · Coloring great-circle arrangement graphs
3-Colorability of Arrangements of Great Circles
Determine whether the graph induced by any simple arrangement of great circles on the sphere is vertex 3-colorable.
Computational complexity and cryptographyProblems, reductions and completeness · Structural 3-decomposition Conjecture
3-decomposition Conjecture
First postulated by Hoffmann-Ostenhof (approx. 2010). conjecture: Every connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching.
Design and analysis of algorithmsGraph algorithms analysis · Low-bend orthogonal graph drawings
3D Minimum-Bend Orthogonal Graph Drawings
Determine whether every graph of maximum degree at most six has a crossing-free three-dimensional orthogonal drawing with at most two bends per edge.
Computational complexity and cryptographyProblems, reductions and completeness · Fine-grained complexity of 3SUM
3SUM Hard Problems
The 3SUM decision problem asks whether three integer sets contain elements a, b, and c satisfying a+b=c. The open question is whether 3SUM and the problems to which it reduces admit algorithms with a polynomial saving over quadratic time. Algorithms with logarithmic-factor improvements are known, but such an exponent saving is conjectured to be impossible even in expectation.
LogicEquational logic and rewriting · Fixed-point combinators from restricted bases
A Fixed-Point Combinator from B and ω
Does the combinatory basis consisting only of and contain a fixed-point combinator? The stronger requirement that the fixed-point equation hold by reduction is known to be impossible, while the equational version remains open in the source.
Formal languages and automata theoryAutomata extensions · A Streaming Machine Model for Polyregular Functions
A Streaming Machine Model for Polyregular Functions
The class of polyregular functions corresponds to the class of functions accepted by reversible, two-way pebble transducers. The question therefore is to come up with a streaming model with "controlled copying" which will be closed under composition, and which can define squaring as well as iterated reverse.