Connections between circuit analysis problems and circuit lower bounds
Thesis: Ph. D. in Computer Science and Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
Main Author: | Murray, Cody (Cody Daniel) |
---|---|
Other Authors: | Ryan Williams. |
Format: | Thesis |
Language: | eng |
Published: |
Massachusetts Institute of Technology
2019
|
Subjects: | |
Online Access: | http://hdl.handle.net/1721.1/120467 |
Similar Items
-
Easiness amplification and uniform circuit lower bounds
by: Williams, Richard Ryan, et al.
Published: (2021) -
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
by: Murray, Cody (Cody Daniel), et al.
Published: (2021) -
Relations and equivalences between circuit lower bounds and Karp-Lipton theorems
by: Williams, Richard Ryan, et al.
Published: (2021) -
Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
by: Williams, Richard Ryan, et al.
Published: (2021) -
Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
by: Murray, Cody D, et al.
Published: (2021)