Pages that link to "Item:Q1346612"
From MaRDI portal
The following pages link to On the degree of Boolean functions as real polynomials (Q1346612):
Displaying 50 items.
- Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables (Q294804) (← links)
- Improved approximation of linear threshold functions (Q371200) (← links)
- On the minimal Fourier degree of symmetric Boolean functions (Q397079) (← links)
- How low can approximate degree and quantum query complexity be for total Boolean functions? (Q488052) (← links)
- A quasi-stability result for dictatorships in \(S_n\) (Q519995) (← links)
- An improved lower bound on the sensitivity complexity of graph properties (Q551172) (← links)
- Unbounded-error quantum query complexity (Q638526) (← links)
- Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions (Q657913) (← links)
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs (Q835643) (← links)
- Pseudo-Boolean functions and the multiplicity of the zeros of polynomials (Q891348) (← links)
- The equivalence of two problems on the cube (Q1194759) (← links)
- On the power of circuits with gates of low \(L_{1}\) norms. (Q1389652) (← links)
- An oracle builder's toolkit (Q1398366) (← links)
- Boolean functions: degree and support (Q1616170) (← links)
- A characterization of nested canalyzing functions with maximum average sensitivity (Q1627840) (← links)
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product (Q1671999) (← links)
- Complexity measures and decision tree complexity: a survey. (Q1853508) (← links)
- One complexity theorist's view of quantum computing (Q1870556) (← links)
- A lower bound on the quantum query complexity of read-once functions (Q1880783) (← links)
- Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions (Q1887146) (← links)
- Complexity limitations on quantum computation (Q1961375) (← links)
- An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function (Q2003766) (← links)
- On separation between the degree of a Boolean function and the block sensitivity (Q2117108) (← links)
- Log-Sobolev inequality for the multislice, with applications (Q2119683) (← links)
- Computational barriers to estimation from low-degree polynomials (Q2149001) (← links)
- A structure theorem for almost low-degree functions on the slice (Q2218715) (← links)
- Boolean constant degree functions on the slice are juntas (Q2329200) (← links)
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture (Q2334869) (← links)
- Dual lower bounds for approximate degree and Markov-Bernstein inequalities (Q2347795) (← links)
- On exact quantum query complexity (Q2350895) (← links)
- The quantum query complexity of the abelian hidden subgroup problem (Q2373740) (← links)
- Bounds on the Fourier coefficients of the weighted sum function (Q2379949) (← links)
- Block sensitivity of weakly symmetric functions (Q2382286) (← links)
- Optimal parallel quantum query algorithms (Q2408924) (← links)
- Triangle-intersecting families of graphs (Q2428720) (← links)
- Extremal properties of polynomial threshold functions (Q2475403) (← links)
- Polynomial degree vs. quantum query complexity (Q2490260) (← links)
- LWPP and WPP are not uniformly gap-definable (Q2495405) (← links)
- An orthogonal basis for functions over a slice of the Boolean hypercube (Q2635087) (← links)
- On sensitivity in bipartite Cayley graphs (Q2668018) (← links)
- From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm (Q2684233) (← links)
- Degree 2 Boolean functions on Grassmann graphs (Q2684903) (← links)
- On the central levels problem (Q2692785) (← links)
- Topology of real multi-affine hypersurfaces and a homological stability property (Q2699228) (← links)
- Junta threshold for low degree Boolean functions on the slice (Q2699646) (← links)
- Superlinear Advantage for Exact Quantum Algorithms (Q2805516) (← links)
- The Multiparty Communication Complexity of Set Disjointness (Q2817790) (← links)
- Bounded Indistinguishability and the Complexity of Recovering Secrets (Q2829962) (← links)
- Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma (Q2948459) (← links)
- (Q3191149) (← links)
