NDLI: Space Complexity Vs. Query Complexity

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

Space Complexity Vs. Query Complexity

Content Provider	Springer Nature Link
Author	Lachish, Oded Newman, Ilan Shapira, Asaf
Copyright Year	2008
Abstract	Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2Ω(s(n)).Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.
Starting Page	70
Ending Page	93
Page Count	24
File Format	PDF
ISSN	10163328
Journal	Computational complexity
Volume Number	17
Issue Number	1
e-ISSN	14208954
Language	English
Publisher	SP Birkhäuser Verlag Basel
Publisher Date	2008-04-02
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Bounded space complexity lower bounds property testing Computational Mathematics and Numerical Analysis 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

Property Testing Lower Bounds via Communication Complexity

Lower bounds for testing triangle-freeness in Boolean functions

Inductive Time-Space Lower Bounds for Sat and Related Problems

On Uniformity and Circuit Lower Bounds

The Complexity of Boolean Functions in Different Characteristics

Query Complexity in Errorless Hardness Amplification

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

2-Local Random Reductions to 3-Valued Functions

Comparing the strength of query types in property testing: The case of k-colorability

Space Complexity Vs. Query Complexity

Similar Documents

Property Testing Lower Bounds via Communication Complexity

Lower bounds for testing triangle-freeness in Boolean functions

Inductive Time-Space Lower Bounds for Sat and Related Problems

On Uniformity and Circuit Lower Bounds

The Complexity of Boolean Functions in Different Characteristics

Query Complexity in Errorless Hardness Amplification

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

2-Local Random Reductions to 3-Valued Functions

Comparing the strength of query types in property testing: The case of k-colorability

Space Complexity Vs. Query Complexity