Low-depth circuit size bounds using combinatorial methods

Thesis

This thesis focuses on constant-depth circuit size lower bounds for the clique, threshold and parity functions. The thesis is centred around the combinatorial tools and questions relevant for attacking these circuit size lower bound problems.

First, the analysis will focus on the maximum one-sided correlation achievable between polynomial-sized, constant-depth circuits and the clique function. Expressing the AND of edges in a given clique provides a $\binom{n}{k}^{-1}$ one-sided correl...

Expand abstract

Authors: Bodnár, L

• DOI: 10.5287/ora-8j0450erz
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: extremal combinatorics; flag algebras; circuit complexity
• Subjects: Combinatorial analysis; Computational complexity