Computer Science
Open problems, research attempts and community review.
The Top Open Problems editorial order restricted to Computer Science, followed by cross-listed economics entries. Existing relative order is retained, with provisional placements for new game-learning questions; most entries have no individual difficulty assessment. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
918 records · Search and filter
- CS-101 10 Lectures and 42 Open Problems — Random Partial Discrete Fourier Transform
- CS-102 10 Lectures and 42 Open Problems — The Paley ETF Conjecture
- CS-103 10 Lectures and 42 Open Problems — Gilbert-Varshamov bound
- CS-104 10 Lectures and 42 Open Problems — The Deletion Channel
- CS-105 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
- CS-106 Dynamic Planar Nearest Neighbors
- CS-107 10 Lectures and 42 Open Problems — Mutually Unbiased Bases
- CS-108 Finite-field factorization and sparse-polynomial root testing
- CS-109 Prime-factor advice in power-residue quotients
- CS-110 Three zeta-like products, degree-count inversion, and the factorization boundary
- CS-111 Arithmetic-Formula Lower Bounds for Permanent and Determinant
- CS-112 Decidability of Rational Points over Number Fields
- CS-113 Unique Games Approximation-Threshold Conjecture
- CS-114 Polynomial Algorithms for Mean-Payoff Games and Linear Programming
- CS-115 $d$-to-$1$ Games Conjecture
- CS-116 Analytical Performance Theory for QAOA and RQAOA
- CS-117 Finite-field polynomial multiplication and integer-multiplication lower bounds
- CS-118 Polynomial switch-chain mixing for all degree sequences
- CS-119 Matrix-multiplication improvement over every field
- CS-120 Exact uniform sampling of arbitrary-margin contingency tables
- CS-121 Bounded additive gap for the bin-packing configuration LP
- CS-122 FPRAS for cell-bounded contingency tables
- CS-123 FPRAS for common integer polymatroid bases
- CS-124 FPRAS for common matroid bases
- CS-125 Complex square and rectangular multiplication bounds
- CS-126 Complex matrix multiplication at exponent nine-fourths
- CS-127 Hellinger contraction with biased Boolean outputs
- CS-128 Sharp binary-channel information contraction on the cube
- CS-129 Constant-factor hardness of directed feedback vertex set
- CS-130 Almost-linear edit-distance approximation scheme
- CS-131 Counting-hierarchy upper bound for existential-universal real sentences
- CS-132 Explicit super-square-root-exponential depth-three circuits
- CS-133 Memory–precision lower bounds for exact Gaussian regression
- CS-134 Unconditional time lower bounds for fixed-dimensional WL
- CS-135 FPRAS for perfect matchings in general graphs
- CS-136 Quasipolynomial trace samples for arbitrary symbols
- CS-137 Depth-five homogeneous lower bounds for iterated matrix multiplication
- CS-138 Integer multiplication below n log n
- CS-139 Exponential semidefinite complexity for perfect matching
- CS-140 Optimal Max-Cut approximation hardness
- CS-141 Quasipolynomial mean-payoff/parity winning sets
- CS-142 Metric k-median at factor one plus two over e
- CS-143 Metric k-median strictly below factor two
- CS-144 Constant-factor hardness of Min-UnCut
- CS-145 Hitting lists for noncommutative rational formulas
- CS-146 One-sample matroid prophet selection
- CS-147 Polynomial deterministic two-way simulation of one-way NFAs
- CS-148 Two-fifths-power space simulation for one writable tape
- CS-149 Deterministic quasipolynomial mean-payoff games
- CS-150 Perfect-completeness two-to-one hardness