{"id":158394,"date":"2009-10-02T00:00:00","date_gmt":"2009-10-02T00:00:00","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/msr-research-item\/optimal-testing-of-reed-muller-codes\/"},"modified":"2018-10-16T19:58:34","modified_gmt":"2018-10-17T02:58:34","slug":"optimal-testing-of-reed-muller-codes","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/optimal-testing-of-reed-muller-codes\/","title":{"rendered":"Optimal testing of Reed-Muller codes"},"content":{"rendered":"<div class=\"asset-content\">\n<p>We consider the problem of testing if a given function f:Fn 2F 2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. proposed and analyzed a natural 2d+1-query test for this property and showed that it accepts every degree d polynomial with probability 1, while rejecting functions that are (1)-far with probability (1(d2d)) . We give an asymptotically optimal analysis of their test showing that it rejects functions that are (even only) (2\u2212d)-far with (1)-probability (so the rejection probability is a universal constant independent of d and n). Our proof works by induction on n, and yields a new analysis of even the classical Blum-Luby-Rubinfeld linearity test, for the setting of functions mapping Fn 2 to F 2. The optimality follows from a tighter analysis of counterexamples to the \u201cinverse conjecture for the Gowers norm\u201d constructed by . Our result gives a new relationship between the (d+1)st-Gowers norm of a function and its maximal correlation with degree d polynomials. For functions highly correlated with degree d polynomials, this relationship is asymptotically optimal. Our improved analysis of the -test also improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson. Finally, the optimality of our result also implies a \u201cquery-hierarchy\u201d result for property testing of linear-invariant properties: For every function q(n), it gives a linear-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of for graph properties.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>We consider the problem of testing if a given function f:Fn 2F 2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. proposed and analyzed a natural 2d+1-query test for this property and showed that it accepts every degree d polynomial with probability 1, [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"ECCC Technical Report","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"MSR-TR-2009-145","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"The documents contained in the ECCC Reports Series are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. The papers in the ECCC ReportsSeries have the status of technical reports. There is no copyright transfere from the Author to the Colloquium. Authors permit the Colloquium to store their works in the digital library of ECCC. Except this, all rights are held by the authors, their institutions, or their designees.The author may withdraw the paper from the digital library of ECCC iff the paper is accepted for publication elsewhere. In particular, it is the responsibility of the author to do this if he\/she signs a copyright agreement which does not allow electronic distribution by ECCC.Users must abide all copyright restrictions specified directly on the reports. In addition, use of the ECCC reports for commercial purpose is strictly forbidden; no one may sell copies of reports without explicitely written permission of the copyright holders. Access to ECCC reports is limited to interactive viewing and\/or printing for personal use. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.","msr_conference_name":"","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2009-10-02","msr_highlight_text":"","msr_notes":"ECCC Technical Report","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":2009,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13546],"msr-publication-type":[193718],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-158394","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-computational-sciences-mathematics","msr-locale-en_us"],"msr_publishername":"","msr_edition":"ECCC Technical Report","msr_affiliation":"","msr_published_date":"2009-10-02","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"MSR-TR-2009-145","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"ECCC Technical Report","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"222289","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","title":"RM.pdf","viewUrl":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2009\/10\/RM.pdf","id":222289,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[{"id":222289,"url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2009\/10\/RM.pdf"}],"msr-author-ordering":[{"type":"text","value":"Arnab Bhattacharyya","user_id":0,"rest_url":false},{"type":"text","value":"Swastik Kopparty","user_id":0,"rest_url":false},{"type":"text","value":"Grant Schoenebeck","user_id":0,"rest_url":false},{"type":"user_nicename","value":"madhu","user_id":32768,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=madhu"},{"type":"text","value":"David Zuckerman","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"techreport","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/158394","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/158394\/revisions"}],"predecessor-version":[{"id":516131,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/158394\/revisions\/516131"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=158394"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=158394"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=158394"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=158394"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=158394"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=158394"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=158394"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=158394"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=158394"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=158394"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=158394"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=158394"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=158394"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}