Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. The Power of Many Samples in Query Complexity
 
conference paper

The Power of Many Samples in Query Complexity

Bassilakis, Andrew
β€’
Drucker, Andrew
β€’
GΓΆΓΆs, Mika  
Show more
Czumaj, Artur
β€’
Dawar, Anuj
Show more
2020
[Proceedings of ICALP 2020]
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

The randomized query complexity 𝖱(f) of a boolean function f: {0,1}ⁿ β†’ {0,1} is famously characterized (via Yao’s minimax) by the least number of queries needed to distinguish a distribution π’Ÿβ‚€ over 0-inputs from a distribution π’Ÿβ‚ over 1-inputs, maximized over all pairs (π’Ÿβ‚€,π’Ÿβ‚). We ask: Does this task become easier if we allow query access to infinitely many samples from either π’Ÿβ‚€ or π’Ÿβ‚? We show the answer is no: There exists a hard pair (π’Ÿβ‚€,π’Ÿβ‚) such that distinguishing π’Ÿβ‚€^∞ from π’Ÿβ‚^∞ requires Θ(𝖱(f)) many queries. As an application, we show that for any composed function f∘g we have 𝖱(f∘g) β‰₯ Ξ©(fbs(f)𝖱(g)) where fbs denotes fractional block sensitivity.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

LIPIcs-ICALP-2020-9.pdf

Type

Publisher

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

License Condition

CC BY

Size

598.5 KB

Format

Adobe PDF

Checksum (MD5)

8450f90d3a4fe435854b15c5ee53f207

Logo EPFL, Γ‰cole polytechnique fΓ©dΓ©rale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. Β© EPFL, tous droits rΓ©servΓ©s