Pages that link to "Item:Q1853508"
From MaRDI portal
The following pages link to Complexity measures and decision tree complexity: a survey. (Q1853508):
Displaying 50 items.
- Totally optimal decision trees for Boolean functions (Q323025) (← links)
- Quantum query complexity of almost all functions with fixed on-set size (Q347109) (← links)
- A strong direct product theorem for quantum query complexity (Q354645) (← links)
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length (Q368235) (← links)
- Optimal direct sum results for deterministic and randomized decision tree complexity (Q407594) (← links)
- On the average sensitivity of the weighted sum function (Q413263) (← links)
- Exponential lower bound for bounded depth circuits with few threshold gates (Q413295) (← links)
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma (Q451107) (← links)
- How low can approximate degree and quantum query complexity be for total Boolean functions? (Q488052) (← links)
- On the power of non-adaptive learning graphs (Q488054) (← links)
- An improved lower bound on the sensitivity complexity of graph properties (Q551172) (← links)
- On the power of Ambainis lower bounds (Q557899) (← links)
- Unbounded-error quantum query complexity (Q638526) (← links)
- Secure and highly-available aggregation queries in large-scale sensor networks via set sampling (Q658674) (← links)
- A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function (Q669952) (← links)
- Fourier 1-norm and quantum speed-up (Q670032) (← links)
- Improved direct product theorems for randomized query complexity (Q693002) (← links)
- Memory-restricted black-box complexity of OneMax (Q763484) (← links)
- The complexity of the certification of properties of stable marriage (Q834962) (← links)
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs (Q835643) (← links)
- A note on the size of minimal covers (Q845985) (← links)
- On the parity complexity measures of Boolean functions (Q974756) (← links)
- Quantum zero-error algorithms cannot be composed (Q1014398) (← links)
- A characterization of nested canalyzing functions with maximum average sensitivity (Q1627840) (← links)
- An adaptivity hierarchy theorem for property testing (Q1630385) (← links)
- Quantum query as a state decomposition (Q1643135) (← links)
- Optimal separation in exact query complexities for Simon's problem (Q1672002) (← links)
- Nonadaptive quantum query complexity (Q1675876) (← links)
- Submodular goal value of Boolean functions (Q1701106) (← links)
- Composition limits and separating examples for some Boolean function complexity measures (Q1701350) (← links)
- Sharp phase transition for the random-cluster and Potts models via decision trees (Q1711490) (← links)
- Non-interactive proofs of proximity (Q1745962) (← links)
- A lower bound on the quantum query complexity of read-once functions (Q1880783) (← links)
- Minterm-transitive functions with asymptotically smallest block sensitivity (Q1944206) (← links)
- Sensitivity versus block sensitivity of Boolean functions (Q1944916) (← links)
- On block sensitivity and fractional block sensitivity (Q1992105) (← links)
- Quantum algorithms on Walsh transform and Hamming distance for Boolean functions (Q1993748) (← links)
- An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function (Q2003766) (← links)
- On the structure of Boolean functions with small spectral norm (Q2012184) (← links)
- Decision trees based on 1-consequences (Q2043377) (← links)
- Critical properties and complexity measures of read-once Boolean functions (Q2043436) (← links)
- Query complexity of generalized Simon's problem (Q2051810) (← links)
- On the decision tree complexity of threshold functions (Q2095465) (← links)
- Evaluation of exact quantum query complexities by semidefinite programming (Q2100824) (← links)
- On separation between the degree of a Boolean function and the block sensitivity (Q2117108) (← links)
- Revisiting Deutsch-Jozsa algorithm (Q2216118) (← links)
- Conflict complexity is lower bounded by block sensitivity (Q2219069) (← links)
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture (Q2334869) (← links)
- On the isomorphism problem for decision trees and decision lists (Q2348033) (← links)
- Any monotone property of 3-uniform hypergraphs is weakly evasive (Q2348256) (← links)
