Loading...
Please wait, while we are loading the content...
Similar Documents
Algorithms versus Circuit Lower Bounds
| Content Provider | arXiv |
|---|---|
| Author | Oliveira, Igor C. |
| Date of Submission | 2013-09-01 |
| Abstract | Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability algorithms. We also cover the connection between circuit lower bounds and useful properties, a notion that turns out to be fundamental in the context of these transference theorems. Along the way, we obtain a few new results, simplify several proofs, and show connections involving different frameworks. We hope that our presentation will serve as a self-contained introduction for those interested in pursuing research in this area. |
| Related Links | https://arxiv.org/pdf/1309.0249.pdf |
| Page Count | 32 |
| arXiv | 1309.0249 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Computational Complexity Computer Science - Discrete Mathematics Computer Science - Data Structures and Algorithms Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
