Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds
In this thesis we study satisfiability algorithms and connections between algorithms and circuit lower bounds. We give new results in the following three areas: Oracles and Algorithmic Methods for Proving Lower Bounds: We give an equivalence between relativizing circuit lower bounds (circuit lowe...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/150213 https://orcid.org/0000-0002-4055-7693 |