Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

Using Random Restrictions to Prove Lower Bounds for Constant-Depth Threshold Circuits

Abstract

A critical challenge in complexity theory is establishing lower bounds on the size, depth, and complexity of Boolean circuits that compute explicit functions. General Boolean circuits, however, have proven resistant to such lower bounds. Consequently, the community has focused on proving lower bounds for more restricted families of circuits, such as bounded-depth circuits over various bases. A notable success in this area is the use of random restrictions, a method where input variables are fixed according to a probability distribution to simplify the circuit. This thesis explores the application of random restriction techniques to circuits and is structured to provide a thorough understanding of how random restrictions can also bee modified and refined to prove more general results.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View