scientific article; zbMATH DE number 6789278

DOI10.4230/LIPICS.CCC.2016.13MaRDI QIDQ5368747zbMATH OpenFDO

Authors Parikshit Gopalan, A. Wigderson, Rocco A. Servedio

Publication date 10 October 2017

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2016.13

zbMATH Keywords

Boolean functionsFourier analysisrandom restrictions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4091790
• Tail dependence from a distributional point of view
• Tail-weighted measures of dependence
• Bounds on the Tail Probability and Absolute Difference Between Two Distributions
• Estimating tails of probability distributions
• On the estimation of the variability in the distribution tail
• Tail dependence for two skew t distributions
• Comparison between two indicators for the variation regularity of tails of distributions
• On estimation of the scale and location parameters of distribution tails

Cited in

(18)

• The equivalence of two problems on the cube
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
• Size of sets with small sensitivity: a generalization of Simon's lemma
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• Low-sensitivity functions from unambiguous certificates
• Pseudorandom generators for low sensitivity functions
• New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
• Fourier bounds and pseudorandom generators for product tests
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• On the resolution of the sensitivity conjecture
• A note on the polynomial representation of Boolean functions over \(\mathrm{GF}(2)\)
• A communication game related to the sensitivity conjecture
• An Optimal Separation of Randomized and Quantum Query Complexity
• A tighter relation between sensitivity complexity and certificate complexity
• Complexity of quantum circuits via sensitivity, magic, and coherence
• A very short proof of Sidorenko's inequality for counts of homomorphisms between graphs

This page was built for publication:

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