Home

Open Problem Garden

  • Help
  • About
  • Contact
  login/create account
Home » Subject » Theoretical Comp. Sci.

Complexity


TitleAuthor(s)Imp.¹Rec.²Subtopicsort iconPosted by
Subset-sums equality (pigeonhole version)✭✭✭0mdevos
Complexity of square-root sumGoemans✭✭0abie
Linear-size circuits for stable $0,1 < 2$ sorting?Regan✭✭1KWRegan
Discrete Logarithm Problem✭✭✭0cplxphil
P vs. PSPACEFolklore✭✭✭0cwenner
Unconditional derandomization of Arthur-Merlin gamesShaltiel; Umans✭✭✭0Derandomizationormeir
Refuting random 3SAT-instances on $O(n)$ clauses (weak form)Feige✭✭✭0Hardness 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 (9)
    • Analysis (5)
    • Combinatorics (32)
    • Geometry (22)
    • Graph Theory (216)
    • Group Theory (5)
    • Logic (11)
    • Number Theory (47)
    • Theoretical Comp. Sci. (11)
      • Algorithms (2)
      • Coding Theory (1)
      • Complexity (7)
        • Derandomization (1)
        • Hardness Amplification (0)
        • Hardness of Approximation (1)
        • Interactive Proofs (0)
        • PCP (0)
      • Cryptography (0)
    • Topology (31)
    • Unsorted (3)
  • Author index
  • Keyword index
    • more

Recent Activity

  • http://uk12monthpaydayloans6.co.uk
  • http://3monthpaydayloansworld.co.uk/@3monthpaydayloans
  • http://12and6monthpaydayloans.co.uk
  • 3 Month Payday Loans @ http://e-paydayloansinuk.co.uk/
  • 3 month loans option @ http://e-24hourloans.co.uk
more
Powered by  Drupal                       Hosted by  CSI of Charles University                       Content distributed under                       Disclaimer