{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/78457"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/78457","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Testing k-wise independent distributions","abstract":"A probability distribution over {0, 1}' is k-wise independent if its restriction to any k coordinates is uniform. More generally, a discrete distribution D over E1 x ... x E, is called (non-uniform) k-wise independent if for any subset of k indices {ii, . . . , ik} and for any zi E Ei 1, .. , Zk E Eik , PrX~D [Xi 1 - - -Xi, = Z1 .. z] = PrX-D[Xi 1 = zi] ... PrX~D [Xik = Zk]. k-wise independent distributions look random \"locally\" to an observer of only k coordinates, even though they may be far from random \"globally\". Because of this key feature, k-wise independent distributions are important concepts in probability, complexity, and algorithm design. In this thesis, we study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the problem of distinguishing k-wise independent distributions supported on the Boolean cube from those that are 6-far in statistical distance from any k-wise independent distribution, we upper bound the number of required samples by O(nk/6 2 ) and lower bound it by Q (n 2 /6) (these bounds hold for constant k, and essentially the same bounds hold for general k). To achieve these bounds, we use novel Fourier analysis techniques to relate a distribution's statistical distance from k-wise independence to its biases, a measure of the parity imbalance it induces on a set of variables. The relationships we derive are tighter than previously known, and may be of independent interest. We then generalize our results to distributions over larger domains. For the uniform case we show an upper bound on the distance between a distribution D from k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust based on our results for the uniform case. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size of the distribution when k is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences.","abstract_html":"A probability distribution over {0, 1}' is k-wise independent if its restriction to any k coordinates is uniform. More generally, a discrete distribution D over E1 x ... x E, is called (non-uniform) k-wise independent if for any subset of k indices {ii, . . . , ik} and for any zi E Ei 1, .. , Zk E Eik , PrX~D [Xi 1 - - -Xi, = Z1 .. z] = PrX-D[Xi 1 = zi] ... PrX~D [Xik = Zk]. k-wise independent distributions look random "locally" to an observer of only k coordinates, even though they may be far from random "globally". Because of this key feature, k-wise independent distributions are important concepts in probability, complexity, and algorithm design. In this thesis, we study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the problem of distinguishing k-wise independent distributions supported on the Boolean cube from those that are 6-far in statistical distance from any k-wise independent distribution, we upper bound the number of required samples by O(nk/6 2 ) and lower bound it by Q (n 2 /6) (these bounds hold for constant k, and essentially the same bounds hold for general k). To achieve these bounds, we use novel Fourier analysis techniques to relate a distribution's statistical distance from k-wise independence to its biases, a measure of the parity imbalance it induces on a set of variables. The relationships we derive are tighter than previously known, and may be of independent interest. We then generalize our results to distributions over larger domains. For the uniform case we show an upper bound on the distance between a distribution D from k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust based on our results for the uniform case. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size of the distribution when k is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences.","abstract_has_math":false,"creators":["Xie, Ning, Ph. D. Massachusetts Institute of Technology"],"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":["Ronitt Rubinfeld."],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-07-22T22:21:24Z","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/78457","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Ronitt Rubinfeld."]},{"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":["Xie, Ning, Ph. D. Massachusetts Institute of Technology"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2013-04-12T19:25:53Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2013-04-12T19:25:53Z"]},{"key":"dc:date.issued","label":"Date","values":["2012"]},{"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/78457"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 119-123)."]},{"key":"dc:description.abstract","label":"Abstract","values":["A probability distribution over {0, 1}' is k-wise independent if its restriction to any k coordinates is uniform. More generally, a discrete distribution D over E1 x ... x E, is called (non-uniform) k-wise independent if for any subset of k indices {ii, . . . , ik} and for any zi E Ei 1, .. , Zk E Eik , PrX~D [Xi 1 - - -Xi, = Z1 .. z] = PrX-D[Xi 1 = zi] ... PrX~D [Xik = Zk]. k-wise independent distributions look random \"locally\" to an observer of only k coordinates, even though they may be far from random \"globally\". Because of this key feature, k-wise independent distributions are important concepts in probability, complexity, and algorithm design. In this thesis, we study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the problem of distinguishing k-wise independent distributions supported on the Boolean cube from those that are 6-far in statistical distance from any k-wise independent distribution, we upper bound the number of required samples by O(nk/6 2 ) and lower bound it by Q (n 2 /6) (these bounds hold for constant k, and essentially the same bounds hold for general k). To achieve these bounds, we use novel Fourier analysis techniques to relate a distribution's statistical distance from k-wise independence to its biases, a measure of the parity imbalance it induces on a set of variables. The relationships we derive are tighter than previously known, and may be of independent interest. We then generalize our results to distributions over larger domains. For the uniform case we show an upper bound on the distance between a distribution D from k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust based on our results for the uniform case. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size of the distribution when k is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Testing k-wise independent distributions"]}]}],"canonical_facts":{"dc:contributor.advisor":["Ronitt Rubinfeld."],"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":["Xie, Ning, Ph. D. Massachusetts Institute of Technology"],"dc:date.accessioned":["2013-04-12T19:25:53Z"],"dc:date.available":["2013-04-12T19:25:53Z"],"dc:date.issued":["2012"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2012.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 119-123)."],"dc:description.abstract":["A probability distribution over {0, 1}' is k-wise independent if its restriction to any k coordinates is uniform. More generally, a discrete distribution D over E1 x ... x E, is called (non-uniform) k-wise independent if for any subset of k indices {ii, . . . , ik} and for any zi E Ei 1, .. , Zk E Eik , PrX~D [Xi 1 - - -Xi, = Z1 .. z] = PrX-D[Xi 1 = zi] ... PrX~D [Xik = Zk]. k-wise independent distributions look random \"locally\" to an observer of only k coordinates, even though they may be far from random \"globally\". Because of this key feature, k-wise independent distributions are important concepts in probability, complexity, and algorithm design. In this thesis, we study the problem of testing (non-uniform) k-wise independent distributions over product spaces. For the problem of distinguishing k-wise independent distributions supported on the Boolean cube from those that are 6-far in statistical distance from any k-wise independent distribution, we upper bound the number of required samples by O(nk/6 2 ) and lower bound it by Q (n 2 /6) (these bounds hold for constant k, and essentially the same bounds hold for general k). To achieve these bounds, we use novel Fourier analysis techniques to relate a distribution's statistical distance from k-wise independence to its biases, a measure of the parity imbalance it induces on a set of variables. The relationships we derive are tighter than previously known, and may be of independent interest. We then generalize our results to distributions over larger domains. For the uniform case we show an upper bound on the distance between a distribution D from k-wise independent distributions in terms of the sum of Fourier coefficients of D at vectors of weight at most k. For the non-uniform case, we give a new characterization of distributions being k-wise independent and further show that such a characterization is robust based on our results for the uniform case. Our results yield natural testing algorithms for k-wise independence with time and sample complexity sublinear in terms of the support size of the distribution when k is a constant. The main technical tools employed include discrete Fourier transform and the theory of linear systems of congruences."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/78457"],"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":["Testing k-wise independent distributions"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:24Z"}