Home

Open Problem Garden

  • Help
  • About
  • Contact
  login/create account
Home » Subject

Theoretical Computer Science


TitleAuthor(s)Imp.¹Rec.²Topic » Subtopicsort iconPosted by
Sums of independent random variables with unbounded varianceFeige✭✭0cwenner
P vs. NPCook; Levin✭✭✭✭0Algorithmszitterbewegung
Exponential Algorithms for KnapsackLipton✭✭1Algorithmsdick lipton
The robustness of the tensor productBen-Sasson; Sudan✭✭✭0Coding Theoryormeir
Subset-sums equality (pigeonhole version)✭✭✭0Complexitymdevos
Complexity of square-root sumGoemans✭✭0Complexityabie
Linear-size circuits for stable $0,1 < 2$ sorting?Regan✭✭1ComplexityKWRegan
Discrete Logarithm Problem✭✭✭0Complexitycplxphil
P vs. PSPACEFolklore✭✭✭0Complexitycwenner
One-way functions exist✭✭✭✭0Complexityporton
Unconditional derandomization of Arthur-Merlin gamesShaltiel; Umans✭✭✭0Complexity » Derandomizationormeir
P vs. BPPFolklore✭✭✭0Complexity » DerandomizationCharles R Great...
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)Feige✭✭✭0Complexity » Hardness of Approximationcwenner

Imp.¹: Importance (Low ✭, Medium ✭✭, High ✭✭✭, Outstanding ✭✭✭✭)
Rec.²: Recommended for undergraduates.

Note: Resolved problems from this section may be found in Solved problems.

Syndicate content

Navigate

  • Subject
    • Algebra (295)
    • Analysis (5)
    • Combinatorics (35)
    • Geometry (29)
    • Graph Theory (228)
    • Group Theory (5)
    • Logic (10)
    • Number Theory (49)
    • PDEs (0)
    • Probability (1)
    • Theoretical Comp. Sci. (13)
      • Algorithms (2)
      • Coding Theory (1)
      • Complexity (9)
      • Cryptography (0)
    • Topology (40)
    • Unsorted (1)
  • Author index
  • Keyword index
  • more

Recent Activity

  • Nowhere-zero flows
  • Shuffle-Exchange Conjecture
  • Algebra
  • Seagull problem
  • Solution to the Lonely Runner Conjecture
more
Powered by  Drupal                       Hosted by  CSI of Charles University                       Content distributed under                       Disclaimer