{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/147560"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/147560","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Better Hardness via Algorithms, and New Forms of Hardness versus Randomness","abstract":"One central theme of complexity theory is the rich interplay between hardness (the existence of functions that are hard to compute) and pseudorandomness (the procedure that converts randomized algorithms into equivalent deterministic algorithms). In one direction, from the classic works of Nisan-Widgerson and Impagliazzo-Widgerson, we know certain hardness hypothesis (circuit lower bounds) implies that all randomized algorithms can be derandomized with a polynomial overhead. In another direction, A decade ago, Williams have proved that certain circuit lower bounds follows from non-trivial derandomization. In this thesis we establish many new connections between hardness and pseudorandomness, strengthening and refining the classic works mentioned above. • New circuit lower bounds from non-trivial derandomization. Following Williams’ algorithmic method, we prove several new circuit lower bounds using various non-trivial derandomization algorithms, including almost-everywhere and strongly average-case lower bound against ACC0 circuits and a new construction of rigid matrices. • Superfast and non-black-box derandomization from plausible hardness assumptions. Under plausible hardness hypotheses, we obtain almost optimal worst-case derandomization of both randomized algorithms and constant-round Arthur-Merlin protocols. We also propose a new framework for non-black-box derandomization and demonstrate its usefulness by showing (1) it connects derandomization to a new type of hardness assumptions that is against uniform algorithms and (2) (from plausible assumptions) it gives derandomization of both randomized algorithms and constant-round doubly efficient proof systems with almost no overhead such that no polynomial-time adversary can find a mistake.","abstract_html":"One central theme of complexity theory is the rich interplay between hardness (the existence of functions that are hard to compute) and pseudorandomness (the procedure that converts randomized algorithms into equivalent deterministic algorithms). In one direction, from the classic works of Nisan-Widgerson and Impagliazzo-Widgerson, we know certain hardness hypothesis (circuit lower bounds) implies that all randomized algorithms can be derandomized with a polynomial overhead. In another direction, A decade ago, Williams have proved that certain circuit lower bounds follows from non-trivial derandomization. In this thesis we establish many new connections between hardness and pseudorandomness, strengthening and refining the classic works mentioned above. • New circuit lower bounds from non-trivial derandomization. Following Williams’ algorithmic method, we prove several new circuit lower bounds using various non-trivial derandomization algorithms, including almost-everywhere and strongly average-case lower bound against ACC0 circuits and a new construction of rigid matrices. • Superfast and non-black-box derandomization from plausible hardness assumptions. Under plausible hardness hypotheses, we obtain almost optimal worst-case derandomization of both randomized algorithms and constant-round Arthur-Merlin protocols. We also propose a new framework for non-black-box derandomization and demonstrate its usefulness by showing (1) it connects derandomization to a new type of hardness assumptions that is against uniform algorithms and (2) (from plausible assumptions) it gives derandomization of both randomized algorithms and constant-round doubly efficient proof systems with almost no overhead such that no polynomial-time adversary can find a mistake.","abstract_has_math":false,"creators":["Chen, Lijie"],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Williams, Ryan"],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-09","date_published":"2022-09","updated_at":"2026-07-22T22:22:15Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/147560","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Williams, Ryan"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Chen, Lijie"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-01-19T19:58:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-01-19T19:58:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-09"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral","Doctor of Philosophy"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/147560"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["One central theme of complexity theory is the rich interplay between hardness (the existence of functions that are hard to compute) and pseudorandomness (the procedure that converts randomized algorithms into equivalent deterministic algorithms). In one direction, from the classic works of Nisan-Widgerson and Impagliazzo-Widgerson, we know certain hardness hypothesis (circuit lower bounds) implies that all randomized algorithms can be derandomized with a polynomial overhead. In another direction, A decade ago, Williams have proved that certain circuit lower bounds follows from non-trivial derandomization. In this thesis we establish many new connections between hardness and pseudorandomness, strengthening and refining the classic works mentioned above. • New circuit lower bounds from non-trivial derandomization. Following Williams’ algorithmic method, we prove several new circuit lower bounds using various non-trivial derandomization algorithms, including almost-everywhere and strongly average-case lower bound against ACC0 circuits and a new construction of rigid matrices. • Superfast and non-black-box derandomization from plausible hardness assumptions. Under plausible hardness hypotheses, we obtain almost optimal worst-case derandomization of both randomized algorithms and constant-round Arthur-Merlin protocols. We also propose a new framework for non-black-box derandomization and demonstrate its usefulness by showing (1) it connects derandomization to a new type of hardness assumptions that is against uniform algorithms and (2) (from plausible assumptions) it gives derandomization of both randomized algorithms and constant-round doubly efficient proof systems with almost no overhead such that no polynomial-time adversary can find a mistake."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Better Hardness via Algorithms, and New Forms of Hardness versus Randomness"]}]}],"canonical_facts":{"dc:contributor.advisor":["Williams, Ryan"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Chen, Lijie"],"dc:date.accessioned":["2023-01-19T19:58:36Z"],"dc:date.available":["2023-01-19T19:58:36Z"],"dc:date.issued":["2022-09"],"dc:description.abstract":["One central theme of complexity theory is the rich interplay between hardness (the existence of functions that are hard to compute) and pseudorandomness (the procedure that converts randomized algorithms into equivalent deterministic algorithms). In one direction, from the classic works of Nisan-Widgerson and Impagliazzo-Widgerson, we know certain hardness hypothesis (circuit lower bounds) implies that all randomized algorithms can be derandomized with a polynomial overhead. In another direction, A decade ago, Williams have proved that certain circuit lower bounds follows from non-trivial derandomization. In this thesis we establish many new connections between hardness and pseudorandomness, strengthening and refining the classic works mentioned above. • New circuit lower bounds from non-trivial derandomization. Following Williams’ algorithmic method, we prove several new circuit lower bounds using various non-trivial derandomization algorithms, including almost-everywhere and strongly average-case lower bound against ACC0 circuits and a new construction of rigid matrices. • Superfast and non-black-box derandomization from plausible hardness assumptions. Under plausible hardness hypotheses, we obtain almost optimal worst-case derandomization of both randomized algorithms and constant-round Arthur-Merlin protocols. We also propose a new framework for non-black-box derandomization and demonstrate its usefulness by showing (1) it connects derandomization to a new type of hardness assumptions that is against uniform algorithms and (2) (from plausible assumptions) it gives derandomization of both randomized algorithms and constant-round doubly efficient proof systems with almost no overhead such that no polynomial-time adversary can find a mistake."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/147560"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Better Hardness via Algorithms, and New Forms of Hardness versus Randomness"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral","Doctor of Philosophy"]},"updated_at":"2026-07-22T22:22:15Z"}