147
IRUS Total
Downloads
  Altmetric

The complexity and applications of circuit minimization

File Description SizeFormat 
Myrisiotis-D-2021-PhD-Thesis.pdfThesis1.6 MBAdobe PDFView/Open
Title: The complexity and applications of circuit minimization
Authors: Myrisiotis, Dimitrios
Item Type: Thesis or dissertation
Abstract: The main topic of this thesis is the study of the Minimum Circuit Size Problem (MCSP). MCSP is a decision problem: Given the truth table of a finite Boolean function and a size parameter 0 <= theta <= 2^n - 1 (in binary), is there a Boolean circuit C of size at most theta such that C computes f? MCSP is an important problem due to its unexpected connections to many other areas of complexity theory, such as learning, pseudorandomness, and average-case complexity. In a similar manner, Kolmogorov complexity poses the following question: Given a string x, what is the size of the smallest program that outputs x when run on the empty string? While Kolmogorov complexity cannot be computed, in general, there are resource-bounded versions of Kolmogorov complexity that are computable and have been very influential in complexity theory, just like MCSP is. In this work, we study MCSP and some of its Kolmogorov complexity counterparts, and answer the following two questions. 1. What is the complexity of MCSP? That is, how easy or difficult is it to compute MCSP? We prove MCSP lower bounds against several restricted models of computation. These, among others, include formulas, branching programs, constant-depth circuits, and one-tape Turing machines. Almost all of the above lower bounds are the first of their kind for MCSP, and almost match the state-of-the-art lower bounds against these models. 2. What are some interesting applications of MCSP? Here, we show that the average-case hardness of a conditional Kolmogorov complexity counterpart of MCSP is almost equivalent to the existence of one-way functions (OWFs). Along with the concurrent and independent work by Liu and Pass, this is one of the first natural NP-complete problems whose average-case hardness is shown to be (almost) equivalent to the existence of OWFs.
Content Version: Open Access
Issue Date: May-2021
Date Awarded: Oct-2021
URI: http://hdl.handle.net/10044/1/92835
DOI: https://doi.org/10.25560/92835
Copyright Statement: Creative Commons Attribution NonCommercial Licence
Supervisor: Cheraghchi, Mahdi
Department: Computing
Publisher: Imperial College London
Qualification Level: Doctoral
Qualification Name: Doctor of Philosophy (PhD)
Appears in Collections:Computing PhD theses



This item is licensed under a Creative Commons License Creative Commons