Analyzing monotone space complexity via the switching network model

Space complexity is the study of how much space/memory it takes to solve problems. Unfortunately, proving general lower bounds on space complexity is notoriously hard. Thus, we instead consider the restricted case of monotone algorithms, which only make deductions based on what is in the input and not what is missing. In this thesis, we develop techniques for analyzing monotone space complexity via a model called the monotone switching network model. Using these techniques, we prove tight bounds on the minimal size of monotone switching networks solving the directed connectivity, generation, and k-clique problems. These results separate monotone analgoues of L and NL and provide an alternative proof of the separation of the monotone NC hierarchy first proved by Raz and McKenzie. We then further develop these techniques for the directed connectivity problem in order to analyze the monotone space complexity of solving directed connectivity on particular input graphs.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Potechin, Aaron H

Advisor dc:contributor.advisor

• Jonathan A. Kelner.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/99066

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99066