2021/09/18 by Bruce Changlong Xu, Xu, Bruce Changlong
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2109.13917
openalex publication_date 2021/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This was submitted as a final project for CS254B, taught by Li Yang Tan and Tom Knowles. The field of Circuit Complexity utilises careful analysis of Boolean Circuit Functions in order to extract meaningful information about a range of complexity classes. In particular, the complexity class P / Poly has played a central role in much of the historical attempts to tackle the problem of whether solution and verification are equivalent i.e. the central P versus NP problem. Whilst circuits can potentially be easier to analyse than Turing Machines due to their non-uniform nature of computation (program size is allowed to depend on the input size), it is notoriously hard to establish lower bounds for them. In this report, we will touch upon several results published by Hastad, Sipser and Razborov that will highlight a dynamic interplay between circuit complexity and many of the central ideas of modern-day complexity theory, and in particular the central importance of Hastad's Switching Lemma.