✦ LIBER ✦

Query complexity of membership comparable sets

✍ Scribed by Till Tantau

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 217 KB
Volume: 302
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(03)00082-3

No coin nor oath required. For personal study only.

✦ Synopsis

This paper investigates how many queries to k-membership comparable sets are needed in order to decide all (k + 1)-membership comparable sets. For k ¿ 2 this query complexity is at least linear and at most cubic. As a corollary, we obtain that more languages are O(log n)-membership comparable than truth-table reducible to P-selective sets.

📜 SIMILAR VOLUMES

On Membership Comparable Sets

✍ D. Sivakumar 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 130 KB

A set A is k(n) membership comparable if there is a polynomial-time computable function that, given k(n) instances of A of length at most n, excludes one of the 2 k(n) possibilities for the memberships of the given strings in A. We show that if SAT is O(log n) membership comparable, then the NP-hard

The Quantum Complexity of Set Membership

✍ Radhakrishnan; Sen; Venkatesh 📂 Article 📅 2002 🏛 Springer 🌐 English ⚖ 132 KB

The Complexity of Membership Problems fo

The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers

✍ Pierre McKenzie; Klaus W. Wagner 📂 Article 📅 2007 🏛 Springer 🌐 English ⚖ 404 KB

The query complexity of estimating weigh

The query complexity of estimating weighted averages

✍ Amit Chakrabarti; Venkatesan Guruswami; Andrew Wirth; Anthony Wirth 📂 Article 📅 2011 🏛 Springer-Verlag 🌐 English ⚖ 160 KB

PAC Learning Intersections of Halfspaces

PAC Learning Intersections of Halfspaces with Membership Queries

✍ S. Kwek; L. Pitt 📂 Article 📅 1998 🏛 Springer 🌐 English ⚖ 323 KB

The Black-Box Query Complexity of Polyno

The Black-Box Query Complexity of Polynomial Summation

✍ Ali Juma; Valentine Kabanets; Charles Rackoff; Amir Shpilka 📂 Article 📅 2009 🏛 Springer 🌐 English ⚖ 560 KB