Analysis of Boolean Functions
From MaRDI portal
Publication:5166888
DOI10.1017/CBO9781139814782zbMath1336.94096arXiv2105.10386OpenAlexW3102754027MaRDI QIDQ5166888
Publication date: 9 July 2014
Full work available at URL: https://arxiv.org/abs/2105.10386
learning theorycryptographysocial choicecircuit complexitypseudorandomnessBoolean function, Fourier transform
Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Social choice (91B14) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory (94-01) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to ordered structures (06-01)
Related Items (only showing first 100 items - show all)
A Peccati-Tudor type theorem for Rademacher chaoses ⋮ On mappings on the hypercube with small average stretch ⋮ On Boolean Functions Defined on Bracket Sequences ⋮ An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Hierarchies of resources for measurement-based quantum computation ⋮ Stability of the Walsh-Hadamard spectrum of cryptographic Boolean functions with biased inputs ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ On (simple) decision tree rank ⋮ One more proof of the first linear programming bound for binary codes and two conjectures ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ Bipartite perfect matching as a real polynomial ⋮ Isoperimetric stability in lattices ⋮ Noise sensitivity of percolation via differential inequalities ⋮ Phase transitions and noise sensitivity on the Poisson space via stopping sets and decision trees ⋮ The spectral gap of random regular graphs ⋮ Influence of a Set of Variables on a Boolean Function ⋮ Noise sensitivity and stability of deep neural networks for binary classification ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Interview with Gil Kalai ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Harmonic polynomials on perfect matchings ⋮ Talagrand's influence inequality revisited ⋮ Secure non-interactive simulation from arbitrary joint distributions ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Forbidden intersections for codes ⋮ Universality of approximate message passing with semirandom matrices ⋮ VARIANTS OF A MULTIPLIER THEOREM OF KISLYAKOV ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ On uniqueness properties of Rademacher chaos series ⋮ Generic framework for key-guessing improvements ⋮ On the \(\Phi \)-stability and related conjectures ⋮ Secure non-interactive reducibility is decidable ⋮ Unnamed Item ⋮ Unnamed Item ⋮ SAT-based invariant inference and its relation to concept learning ⋮ On the smoothed analysis of the smallest singular value with discrete noise ⋮ Adaptivity gaps for the stochastic Boolean function evaluation problem ⋮ Local limit theorems for subgraph counts ⋮ Hypercontractivity on the symmetric group ⋮ Threshold for detecting high dimensional geometry in anisotropic random geometric graphs ⋮ Additive randomized encodings and their applications ⋮ Average-case speedup for product formulas ⋮ KKL's influence on me ⋮ Interactions of computational complexity theory and mathematics ⋮ From multivalued to Boolean functions: preservation of soft nested canalization ⋮ Average sensitivity of nested canalizing multivalued functions ⋮ Communication and information complexity ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ Approximate F_2-Sketching of Valuation Functions ⋮ An optimal distributed discrete log protocol with applications to homomorphic secret sharing ⋮ Generalized satisfiability problems via operator assignments ⋮ Rectangles Are Nonnegative Juntas ⋮ Bipartite communities via spectral partitioning ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ On the Decision Tree Complexity of Threshold Functions ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Amplification of One-Way Information Complexity via Codes and Noise Sensitivity ⋮ Fast Heuristics and Approximation Algorithms ⋮ A note on concentration for polynomials in the Ising model ⋮ Quasi-random multilinear polynomials ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Disordered systems insights on computational hardness ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ An orthogonal basis for functions over a slice of the Boolean hypercube ⋮ Fooling Polytopes ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ Upper Bounds on Fourier Entropy ⋮ Probabilistic view of voting, paradoxes, and manipulation ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Central limit theorem for majority dynamics: bribing three voters suffices ⋮ The inverse Shapley value problem ⋮ Private Sampling: A Noiseless Approach for Generating Differentially Private Synthetic Data ⋮ Quantum learning Boolean linear functions w.r.t. product distributions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions ⋮ On the Fourier spectrum of functions on Boolean cubes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum algorithms for the Goldreich-Levin learning problem ⋮ Several Classes of Boolean Functions with Four-Valued Walsh Spectra ⋮ Degree 2 Boolean functions on Grassmann graphs ⋮ Mean field dynamics of stochastic cellular automata for random and small-world graphs ⋮ On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones ⋮ Boolean functions on $S_n$ which are nearly linear ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Polynomial inequalities on the Hamming cube ⋮ Query-to-Communication Lifting for BPP ⋮ Unnamed Item ⋮ Hypercontractivity via tensor calculus ⋮ Fuzzy Measures and Integrals: Recent Developments
This page was built for publication: Analysis of Boolean Functions
