{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/91856"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/91856","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Trace reconstruction problem","abstract":"In the setting of the trace reconstruction problem, a uniform random binary sequence w [epsilon] {0, 1}n yields a collection of traces, such that each subsequence is obtained by independently deleting each bit with a public probability parameter p. In this thesis we explore a restricted version of this problem, in which each trace is a random subsequence of one of two original known sequences. Given a series of traces, we would like to device a method that allows to us to decide from which sequence, from the pair of known public sequences w, w', do all the traces come from. The question we will try to solve in this thesis is to know if such a method, operating with high probability and polynomially many samples, is possible in practice. Among other things, we show that if the two strings are drawn uniformly at random there is an algorithm that allows to efficiently distinguish with high probability the traces they produce, failing only on an exponentially small proportion of the random pairs. Additionally we explore variants of this problem and their connections with a number theoretic known as the Prouhet-Tarry-Escott problem.","abstract_html":"In the setting of the trace reconstruction problem, a uniform random binary sequence w [epsilon] {0, 1}n yields a collection of traces, such that each subsequence is obtained by independently deleting each bit with a public probability parameter p. In this thesis we explore a restricted version of this problem, in which each trace is a random subsequence of one of two original known sequences. Given a series of traces, we would like to device a method that allows to us to decide from which sequence, from the pair of known public sequences w, w', do all the traces come from. The question we will try to solve in this thesis is to know if such a method, operating with high probability and polynomially many samples, is possible in practice. Among other things, we show that if the two strings are drawn uniformly at random there is an algorithm that allows to efficiently distinguish with high probability the traces they produce, failing only on an exponentially small proportion of the random pairs. Additionally we explore variants of this problem and their connections with a number theoretic known as the Prouhet-Tarry-Escott problem.","abstract_has_math":false,"creators":["Pacchiano, Aldo"],"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":["Constantinos Daskalakis."],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-07-22T22:21:38Z","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/91856","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Constantinos Daskalakis."]},{"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":["Pacchiano, Aldo"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-11-24T18:40:18Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-11-24T18:40:18Z"]},{"key":"dc:date.issued","label":"Date","values":["2014"]},{"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/91856"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.","Cataloged from PDF version of thesis.","Includes bibliographical references (page 95)."]},{"key":"dc:description.abstract","label":"Abstract","values":["In the setting of the trace reconstruction problem, a uniform random binary sequence w [epsilon] {0, 1}n yields a collection of traces, such that each subsequence is obtained by independently deleting each bit with a public probability parameter p. In this thesis we explore a restricted version of this problem, in which each trace is a random subsequence of one of two original known sequences. Given a series of traces, we would like to device a method that allows to us to decide from which sequence, from the pair of known public sequences w, w', do all the traces come from. The question we will try to solve in this thesis is to know if such a method, operating with high probability and polynomially many samples, is possible in practice. Among other things, we show that if the two strings are drawn uniformly at random there is an algorithm that allows to efficiently distinguish with high probability the traces they produce, failing only on an exponentially small proportion of the random pairs. Additionally we explore variants of this problem and their connections with a number theoretic known as the Prouhet-Tarry-Escott problem."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M. Eng."]},{"key":"dc:title","label":"Title","values":["Trace reconstruction problem"]}]}],"canonical_facts":{"dc:contributor.advisor":["Constantinos Daskalakis."],"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":["Pacchiano, Aldo"],"dc:date.accessioned":["2014-11-24T18:40:18Z"],"dc:date.available":["2014-11-24T18:40:18Z"],"dc:date.issued":["2014"],"dc:description":["Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014.","Cataloged from PDF version of thesis.","Includes bibliographical references (page 95)."],"dc:description.abstract":["In the setting of the trace reconstruction problem, a uniform random binary sequence w [epsilon] {0, 1}n yields a collection of traces, such that each subsequence is obtained by independently deleting each bit with a public probability parameter p. In this thesis we explore a restricted version of this problem, in which each trace is a random subsequence of one of two original known sequences. Given a series of traces, we would like to device a method that allows to us to decide from which sequence, from the pair of known public sequences w, w', do all the traces come from. The question we will try to solve in this thesis is to know if such a method, operating with high probability and polynomially many samples, is possible in practice. Among other things, we show that if the two strings are drawn uniformly at random there is an algorithm that allows to efficiently distinguish with high probability the traces they produce, failing only on an exponentially small proportion of the random pairs. Additionally we explore variants of this problem and their connections with a number theoretic known as the Prouhet-Tarry-Escott problem."],"dc:description.degree":["M. Eng."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/91856"],"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":["Trace reconstruction problem"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:38Z"}