Thesis
The complexity of meta-computational problems
- Abstract:
-
This thesis focuses on problems which themselves encode questions about circuits or algorithms, also called meta-computational problems. The thesis is centered on meta-computational problems like C-MCSP (minimum circuit size problem), C-Learnability and C-Satisfiability, for some circuit class C. We study mathematical questions pertaining to such problems, and their deep connections to the theory of lower bounds, which is a general theme that has attracted a lot of interest in recent years...
Expand abstract
Actions
Access Document
- Files:
-
-
(Preview, Dissemination version, pdf, 1.1MB, Terms of use)
-
Authors
Contributors
+ Santhanam, R
- Institution:
- University of Oxford
- Division:
- MPLS
- Department:
- Computer Science
- Role:
- Supervisor
+ European Research Council
More from this funder
- Funder identifier:
- http://dx.doi.org/10.13039/501100000781
- Funding agency for:
- Santhanam, R
- Grant:
- 615075
- Programme:
- ERC Consolidator Grant
- DOI:
- Type of award:
- DPhil
- Level of award:
- Doctoral
- Awarding institution:
- University of Oxford
- Language:
-
English
- Keywords:
- Subjects:
- Deposit date:
-
2022-08-18
- ARK identifier:
Terms of use
- Copyright holder:
- Rajgopal, N
- Copyright date:
- 2020
If you are the owner of this record, you can report an update to it here: Report update to this record