{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/106089"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/106089","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Algebraic methods in pseudorandomness and circuit complexity","abstract":"In this thesis, we apply tools from algebra and algebraic geometry to prove new results concerning extractors for algebraic sets, AC⁰-pseudorandomness, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over F₂ of substantially higher degree than the previous state-of-the-art construction. We exhibit a collection of natural functions that behave pseudorandomly with regards to AC⁰ tests. We also exactly determine the F₂-polynomial degree of the recursive Fourier sampling problem and use this to provide new partial results towards a circuit lower bound for this problem. Finally, we answer a question posed in [MR15] concerning VC dimension, interpolation degree and the Hilbert function.","abstract_html":"In this thesis, we apply tools from algebra and algebraic geometry to prove new results concerning extractors for algebraic sets, AC⁰-pseudorandomness, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over F₂ of substantially higher degree than the previous state-of-the-art construction. We exhibit a collection of natural functions that behave pseudorandomly with regards to AC⁰ tests. We also exactly determine the F₂-polynomial degree of the recursive Fourier sampling problem and use this to provide new partial results towards a circuit lower bound for this problem. Finally, we answer a question posed in [MR15] concerning VC dimension, interpolation degree and the Hilbert function.","abstract_has_math":false,"creators":["Remscrim, Zachary (Zachary N.)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Michael Sipser."],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016","date_published":"2016","updated_at":"2026-07-22T22:21:13Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/106089","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Michael Sipser."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Remscrim, Zachary (Zachary N.)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-12-22T16:28:33Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-12-22T16:28:33Z"]},{"key":"dc:date.issued","label":"Date","values":["2016"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/106089"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 93-96)."]},{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis, we apply tools from algebra and algebraic geometry to prove new results concerning extractors for algebraic sets, AC⁰-pseudorandomness, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over F₂ of substantially higher degree than the previous state-of-the-art construction. We exhibit a collection of natural functions that behave pseudorandomly with regards to AC⁰ tests. We also exactly determine the F₂-polynomial degree of the recursive Fourier sampling problem and use this to provide new partial results towards a circuit lower bound for this problem. Finally, we answer a question posed in [MR15] concerning VC dimension, interpolation degree and the Hilbert function."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Algebraic methods in pseudorandomness and circuit complexity"]}]}],"canonical_facts":{"dc:contributor.advisor":["Michael Sipser."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Remscrim, Zachary (Zachary N.)"],"dc:date.accessioned":["2016-12-22T16:28:33Z"],"dc:date.available":["2016-12-22T16:28:33Z"],"dc:date.issued":["2016"],"dc:description":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2016.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 93-96)."],"dc:description.abstract":["In this thesis, we apply tools from algebra and algebraic geometry to prove new results concerning extractors for algebraic sets, AC⁰-pseudorandomness, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over F₂ of substantially higher degree than the previous state-of-the-art construction. We exhibit a collection of natural functions that behave pseudorandomly with regards to AC⁰ tests. We also exactly determine the F₂-polynomial degree of the recursive Fourier sampling problem and use this to provide new partial results towards a circuit lower bound for this problem. Finally, we answer a question posed in [MR15] concerning VC dimension, interpolation degree and the Hilbert function."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/106089"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Algebraic methods in pseudorandomness and circuit complexity"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:13Z"}