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-351 Uniqueness of Equilibria in Rank-One Bimatrix Games
- CS-352 Proximity and Sparsity of Optimal Integer Solutions
- CS-353 Convergence Rates for Convex-Body Bounds
- CS-354 Fast Low-Rank Maximum-Weight Assignment
- CS-355 Integrality Gaps for Directed Linear k-Cut
- CS-356 Hardness of Root-Dependent Spanning-Tree Optimization
- CS-357 Hardness of Path-Cost Arborescence Optimization
- CS-358 Polynomial-Time Comparison of Sparse Algebraic Power Sums
- CS-359 Degree-Utility Optimization in Graphs
- CS-360 Real Tau Conjecture for Depth-Four Circuits
- CS-361 Karchmer–Raz–Wigderson Composition Conjecture
- CS-362 Subquadratic Approximation for Longest Common Subsequences
- CS-363 Geometric Explanations and Polynomial Pivot Rules for Simplex
- CS-364 Sharp Smoothed Complexity of Simplex Pivot Rules
- CS-365 Theta Invariants and New Families of MRD Codes
- CS-366 Explicit RIP Matrices Beyond Square-Root Sparsity
- CS-367 Square-Root Sparsity for Explicit RIP Matrices
- CS-368 Sample Complexity of Vertex-Distribution-Free Graph Testing
- CS-369 Complexity of Approximate Counting in Spin Systems
- CS-370 Exact Higher-Order Matrix Decomposability
- CS-371 Semidefinite Hierarchies for Equiangular Line Bounds
- CS-372 Computational Recognition of Polytope Face Vectors and Cones
- CS-373 Recognition of Virtually Special Hyperbolic Three-Manifolds
- CS-374 Minimum Crossing Realizations of Spatial Polygon Angle Sequences
- CS-375 Submultiplicativity Gaps for Stabilizer Extent
- CS-376 Complexity of Submodular $k$-Partition
- CS-377 Integer Programming with Bounded Subdeterminants
- CS-378 Extension Complexity of Inscribed Fixed-Dimensional Polytopes
- CS-379 Arborescences Induced by Linear-Programming Pivot Rules
- CS-380 Near-Optimal Algorithms for Mixed-Integer Convex Optimization
- CS-381 Linear Bounds for Minimally Integer-Infeasible Systems
- CS-382 Approximating Maximum Nonsymmetric Principal Subdeterminants
- CS-383 Better-Than-Two Approximation for Multiplicative Connectivity Augmentation
- CS-384 Balanced Signings in the Subtour Polytope
- CS-385 Compact Representations of Four-Thirds Near-Mincuts
- CS-386 Better Approximations for Unrelated Graph Balancing
- CS-387 Deterministic Optimization of Top-$k$ Perfect-Matching Edges
- CS-388 Property Testing for Noncommutative Quantum Functions
- CS-389 Algebraic and Graph-Property Tests for Quantum Functions
- CS-390 Canonical Paths Versus Spectral Independence
- CS-391 Good Locally Testable Quantum Codes and Linear-Rate PCPs
- CS-392 Convergence and Effective Rates of Unwinding Series
- CS-393 Phase Retrieval from Gabor and Wavelet Magnitudes
- CS-394 Optimal Neural-Network Depth for Sparse Recovery
- CS-395 LOCAL Coloring Complexity and Constant-Round Decidability on Trees
- CS-396 Algebraic Complexity of Borel Constraint Problems
- CS-397 Determinacy Methods in LOCAL and Borel Coloring
- CS-398 Local-to-Global Tensorization of Information Functionals
- CS-399 Capacity Criteria for Arbitrarily Varying Channels with Causal State Information
- CS-400 Decidability of Linear Information Inequalities