Sensitivity and query complexity under uncertainty

DOI10.4230/LIPICS.MFCS.2025.17MaRDI QIDQ7310178zbMATH OpenFDO

Authors Deepu Benson, Balagopal Komarath, Nikhil S. Mande, Sai Soumya Nalli, Jayalal Sarma M. N., Karteek Sreenivasaiah

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.17

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Complexity measures and decision tree complexity: a survey.
• CREW PRAM<scp>s</scp> and Decision Trees
• Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1182735 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Karchmer-Wigderson games for hazard-free computation
• Learning decision trees from random examples
• Notes on hazard-free circuits
• On the complexity of hazard-free circuits
• On the degree of Boolean functions as real polynomials
• Parallelism in random access machines
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Sensitivity vs. block sensitivity of Boolean functions
• Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• Understanding machine learning. From theory to algorithms
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

This page was built for publication: Sensitivity and query complexity under uncertainty

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310178)