Analysis of Boolean Functions
2012/05/02 by Li-Yang Tan, Tan, Li-Yang · 84 citations
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1205.0314
43 pages
arxiv created 2012/05/02 · arxiv updated 2012/05/03
Abstract
Scribe notes from the 2012 Barbados Workshop on Computational Complexity. A series of lectures on Analysis of Boolean Functions by Ryan O'Donnell, with a guest lecture by Per Austrin.
Cited by
- Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks
- Dimension-Free Approximate Tensorization of Quantum Hypercontractivity for Qudit Depolarizing Semigroups
- On the encoding complexity of quantum numerical integration: an angle-structure characterization
- Improved Hardness Results for Nash Social Welfare, Budgeted Allocation and GAP via the Unique Games Conjecture
- Forbidding just one intersection for short integer sequences
- Limitations of Membership Queries in Testable Learning
- PTF Testing Lower Bounds for Non-Gaussian Component Analysis
- Talagrand's convolution conjecture up to loglog via perturbed reverse heat
- Optical kernel machine with programmable nonlinearity
- Smoothed Agnostic Learning of Halfspaces over the Hypercube
- Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
- A fast and frugal Gaussian Boson Sampling emulator
- Learning and Testing Convex Functions
- Further improvements to stabilizer simulation theory: classical rewriting of CSS-preserving stabilizer circuits, quadratic form expansions of stabilizer operations, and framed hidden variable models
- Random Spiking Neural Networks are Stable and Spectrally Simple
- How Data Mixing Shapes In-Context Learning: Asymptotic Equivalence for Transformers with MLPs
- Hardware-Aware QUBO Reformulation of Constrained Binary Optimization via the Walsh-Fourier Transform
- Talagrand-Type Correlation Inequalities for Supermodular and Submodular Functions on the Hypercube
- From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD
- Counterexample to majority optimality in NICD with erasures
- Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
- VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
- On the permutation equivariance principle for causal estimands
- Fourier Analysis on the Boolean Hypercube via Hoeffding Functional Decomposition
- Non-iid hypothesis testing: from classical to quantum
- Expand Neurons, Not Parameters
- FourierCSP: Differentiable Constraint Satisfaction Problem Solving by Walsh-Fourier Expansion
- Large Deviations Principle for Isoperimetry and Its Equivalence to Nonlinear Log-Sobolev Inequalities
- On irreducible central limit theorems
- Linear-Size QAC0 Channels: Learning, Testing and Hardness
- Exact Bias of Linear TRNG Correctors -- Spectral Approach
- An SoS Entropy Dichotomy via Windowed Hypercontractivity
- Light Differentiable Logic Gate Networks
- Structural Origin and the Minimal Syntax of NP-Hardness: Analysis of SAT from Syntactic Generativity and Compositional Collapse
- Lower Bounds for Learning Hamiltonians from Time Evolution
- No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
- On The Most Discriminative Boolean Functions for Correlated Sources
- Rational degree is polynomially related to degree
- A Theoretical Framework for Stochastic Activity Prediction in Tensor Accelerator Wallace-Tree Multipliers
- A Compositional Kernel Model for Feature Learning
- Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing
- The Structure of Extremal Bad Science Matrices
- Correlation thresholds in the steady states of particle systems and spin glasses
- Voter Model stability with respect to conservative noises
- Finite entropy sums in quantum field theory
- On the Maximal Gaussian Perimeter of Convex Sets, Revisited
- Towards Interpretability of Neural Quantum States
- Efficiently Verifiable Proofs of Data Attribution
- Incoherent Light-Driven Nonlinear Optical Extreme Learner via Data Reverberation
- Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
- Robustly Learning Monotone Single-Index Models
- Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups
- Faster exact learning of k-term DNFs with membership and equivalence queries
- Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube
- Graphs With the Same Edge Count in Each Neighborhood
- Enhanced noise sensitivity, 2D directed polymers and Stochastic Heat Flow
- Testing Isomorphism of Boolean Functions over Finite Abelian Groups
- A Distributional-Lifting Theorem for PAC Learning
- Identity Testing for Circuits with Exponentiation Gates
- Black-Box Crypto is Useless for Pseudorandom Codes
- Learning DNF through Generalized Fourier Representations
- Thinking Out of the Box: Hybrid SAT Solving by Unconstrained Continuous Optimization
- On the Spectral Expansion of Monotone Subsets of the Hypercube
- Characterising the Inductive Biases of Neural Networks on Boolean Data
- Strong Low Degree Hardness for the Number Partitioning Problem
- ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs
- BiKAN: Restoring Collapsed Basis of Binary Kolmogorov--Arnold Networks
- A near-optimal Quadratic Goldreich-Levin algorithm
- A Framework for Ruling Out Quantum Speedups
- On the symmetry of evidential support
- Polynomial Algorithms for Minimum Degree Partitions in Semicomplete Digraphs
- Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs
- Identifying structural design principles shaping the computational abilities of recurrent neural networks
- Accelerated Fourier SAT (AFSAT): Fully Realising a GPU-based Symmetric Pseudo-Boolean SAT Solver
- On the Computational Complexity of Geometrically Local QAC0 circuits
- How Global Calibration Strengthens Multiaccuracy
- Capacity on BMS Channels via Code Symmetry and Nesting
- Probabilistic Stability Guarantees for Feature Attributions
- Partial results for union-closed conjectures on the weighted cube
- A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
- Fine-Grained Complexity via Quantum Natural Proofs
- Relative-error testing of conjunctions and decision lists
- Almost sure bounds for higher-order derivatives of first-passage percolation with respect to the environment
- Higher-order derivatives of first-passage percolation with respect to the environment
Related