Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation
| dc.contributor.advisor | Gál, A. (Anna) | en |
| dc.creator | Trifonov, Vladimir Traianov | en |
| dc.date.accessioned | 2008-08-28T23:19:37Z | en |
| dc.date.available | 2008-08-28T23:19:37Z | en |
| dc.date.issued | 2006 | en |
| dc.description | text | en |
| dc.description.abstract | The subject of computational complexity theory is to analyze the difficulty of solving computational problems within different models of computation. Proving lower bounds is easier in less powerful models and proving upper bounds is easier in the more powerful models. This dissertation studies techniques for analyzing the power of models of computation which are at the frontier of currently existing methods. First, we study the power of certain classes of depth-three circuits. The power of such circuits is largely not understood and studying them under further restrictions has received a lot of attention. We prove exponential lower bounds on the size of certain depth-three circuits computing parity. Our approach is based on relating the lower bounds to correlation between parity and modular polynomials, and expressing the correlation with exponential sums. We show a new expression for the exponential sum which involves a certain affine space corresponding to the polynomial. This technique gives a unified treatment and generalization of bounds which include the results of Goldmann on linear polynomials and Cai, Green, and Thierauf on symmetric polynomials. We obtain bounds on the exponential sums for lasses of polynomials of large degree and with a large number of terms, which previous techniques did not apply to. Second, we study the space complexity of undirected st- connectivity. We prove an O(log n log log n) upper bound on the space complexity of undirected st-connectivity. This improves the previous O(log4=3 n) bound due to Armoni et al. and is a big step towards the conjectured optimal O(log n) bound. Independently of our work and using different techniques recently Reingold proved the optimal bound. Interest in this question comes from the fact that undirected st-connectivity is complete for SL, a class of problems between L and NL. It has been noticed that questions in the space context tend to be easier to answer than the corresponding questions in the time context. Since understanding the power of non-determinism over determinism presents a major challenge to complexity theory, studying complexity lasses between L and NL, which are the smallest natural classes capturing deterministic and non-deterministic space-bounded computation, is important. | |
| dc.description.department | Computer Science | |
| dc.format.medium | electronic | en |
| dc.identifier | b68655368 | en |
| dc.identifier.oclc | 166306538 | en |
| dc.identifier.uri | http://hdl.handle.net/2152/2975 | en |
| dc.language.iso | eng | en |
| dc.rights | Copyright is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works. | en |
| dc.subject.lcsh | Computational complexity | en |
| dc.subject.lcsh | Algorithms | en |
| dc.title | Techniques for analyzing the computational power of constant-depth circuits and space-bounded computation | en |
| dc.type.genre | Thesis | en |
| thesis.degree.department | Computer Sciences | en |
| thesis.degree.discipline | Computer Sciences | en |
| thesis.degree.grantor | The University of Texas at Austin | en |
| thesis.degree.level | Doctoral | en |
| thesis.degree.name | Doctor of Philosophy | en |