Searching for PCP theorem : 3 results found | RSS Feed for this search

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT) 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT)

Description

Includes audio/video content: AV lectures. 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions). Includes audio/video content: AV lectures. 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

Subjects

NP-completeness | NP-completeness | 3SAT | 3SAT | 3-partition | 3-partition | Hamiltonicity | Hamiltonicity | PSPACE | PSPACE | EXPTIME | EXPTIME | EXPSPACE | EXPSPACE | games | games | puzzles | puzzles | computation | computation | Tetris | Tetris | Nintendo | Nintendo | Super Mario Bros. | Super Mario Bros. | The Legend of Zelda | The Legend of Zelda | Metroid | Metroid | Pokémon | Pokémon | constraint logic | constraint logic | Sudoku | Sudoku | Nikoli | Nikoli | Chess | Chess | Go | Go | Othello | Othello | board games | board games | inapproximability | inapproximability | PCP theorem | PCP theorem | OPT-preserving reduction | OPT-preserving reduction | APX-hardness | APX-hardness | vertex cover | vertex cover | Set-cover hardness | Set-cover hardness | Group Steiner tree | Group Steiner tree | k-dense subgraph | k-dense subgraph | label cover | label cover | Unique Games Conjecture | Unique Games Conjecture | independent set | independent set | fixed-parameter intractability | fixed-parameter intractability | parameter-preserving reduction | parameter-preserving reduction | W hierarchy | W hierarchy | clique-hardness | clique-hardness | 3SUM-hardness | 3SUM-hardness | exponential time hypothesis | exponential time hypothesis | counting problems | counting problems | solution uniqueness | solution uniqueness | game theory | game theory | Existential theory of the reals | Existential theory of the reals | undecidability | undecidability

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allavcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT)

Description

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

Subjects

NP-completeness | 3SAT | 3-partition | Hamiltonicity | PSPACE | EXPTIME | EXPSPACE | games | puzzles | computation | Tetris | Nintendo | Super Mario Bros. | The Legend of Zelda | Metroid | mon | constraint logic | Sudoku | Nikoli | Chess | Go | Othello | board games | inapproximability | PCP theorem | OPT-preserving reduction | APX-hardness | vertex cover | Set-cover hardness | Group Steiner tree | k-dense subgraph | label cover | Unique Games Conjecture | independent set | fixed-parameter intractability | parameter-preserving reduction | W hierarchy | clique-hardness | 3SUM-hardness | exponential time hypothesis | counting problems | solution uniqueness | game theory | Existential theory of the reals | undecidability

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.405J Advanced Complexity Theory (MIT)

Description

This graduate-level course focuses on current research topics in computational complexity theory. Topics include: Nondeterministic, alternating, probabilistic, and parallel computation models; Boolean circuits; Complexity classes and complete sets; The polynomial-time hierarchy; Interactive proof systems; Relativization; Definitions of randomness; Pseudo-randomness and derandomizations;Interactive proof systems and probabilistically checkable proofs.

Subjects

18.405 | 6.841 | Polynomial hierarchy | time-space lower bounds | approximate counting | ?s Theorem | Relativization | Baker-Gill-Solovay | switching lemma | Razborov-Smolensky | NEXP vs. ACC0 | Communication complexity | PCP theorem | Hadamard code | Gap amplification | Natural proofs

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata