NDLI: Sunflowers and Testing Triangle-Freeness of Functions

Please wait, while we are loading the content...

Sunflowers and Testing Triangle-Freeness of Functions

Content Provider	Springer Nature Link
Author	Haviv, Ishay Xie, Ning
Copyright Year	2016
Abstract	A function $${f : {\mathbb F}_{2}^{n} \rightarrow {\{0,1\}}}$$ is triangle-free if there are no $${x_{1},x_{2},x_{3} \in {\mathbb F}_{2}^{n}}$$ satisfying $${x_{1} + x_{2} + x_{3} = 0}$$ and $${f(x_{1}) = f(x_{2}) = f(x_{3}) = 1}$$ . In testing triangle-freeness, the goal is to distinguish with high probability triangle-free functions from those that are $${\varepsilon}$$ -far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on $${\varepsilon}$$ (Green 2005); however, the best-known upper bound is a tower-type function of $${1/\varepsilon}$$ . The best known lower bound on the query complexity of the canonical tester is $${1/\varepsilon^{13.239}}$$ (Fu & Kleinberg 2014).In this work we introduce a new approach to proving lower bounds on the query complexity of triangle-freeness. We relate the problem to combinatorial questions on collections of vectors in $${{\mathbb Z}_D^n}$$ and to sunflower conjectures studied by Alon, Shpilka & Umans (2013). The relations yield that a refutation of the Weak Sunflower Conjecture over $${{\mathbb Z}_{4}}$$ implies a super-polynomial lower bound on the query complexity of the canonical tester for triangle-freeness. Our results are extended to testing k-cycle-freeness of functions with domain $${{\mathbb F}_p^n}$$ for every $${k \ge 3}$$ and a prime p. In addition, we generalize the lower bound of Fu and Kleinberg to k-cycle-freeness for $${k \geq 4}$$ by generalizing the construction of uniquely solvable puzzles due to Coppersmith & Winograd (1990).
Ending Page	530
Page Count	34
Starting Page	497
File Format	PDF
ISSN	10163328
e-ISSN	14208954
Journal	Computational complexity
Issue Number	2
Volume Number	26
Language	English
Publisher	Springer International Publishing
Publisher Date	2016-05-30
Publisher Place	Cham
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Analysis of algorithms and problem complexity Computational Mathematics and Numerical Analysis Randomized algorithms triangle-freeness property testing Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) sunflowers Analysis of algorithms Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Lower bounds for testing triangle-freeness in Boolean functions

Property Testing Lower Bounds via Communication Complexity

Testing Triangle-Freeness in General Graphs

Sunflowers and Testing Triangle-Freeness of Functions

Inapproximability of the Tutte polynomial of a planar graph

The complexity of multiple-precision arithmetic

Testing list H-homomorphisms

Toward a Model for Backtracking and Dynamic Programming

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

Sunflowers and Testing Triangle-Freeness of Functions

Similar Documents

Lower bounds for testing triangle-freeness in Boolean functions

Property Testing Lower Bounds via Communication Complexity

Testing Triangle-Freeness in General Graphs

Sunflowers and Testing Triangle-Freeness of Functions

Inapproximability of the Tutte polynomial of a planar graph

The complexity of multiple-precision arithmetic

Testing list H-homomorphisms

Toward a Model for Backtracking and Dynamic Programming

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

Sunflowers and Testing Triangle-Freeness of Functions