Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

DOI10.1016/j.dam.2012.04.020zbMath1252.94126OpenAlexW1970944793MaRDI QIDQ713329

Anders Yeo, Gregory Gutin

Publication date: 26 October 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.04.020

zbMATH Keywords

harmonic analysishypercontractive inequalitypseudo-Boolean functionFourier analysis of pseudo-Boolean functionsMaxLin

Mathematics Subject Classification ID

Boolean functions (06E30) Fourier coefficients, Fourier series of functions with special properties, special Fourier series (42A16)

Related Items (2)

Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• A probabilistic approach to problems parameterized above or below tight bounds
• Solving MAX-\(r\)-SAT above a tight lower bound
• Pseudo-Boolean optimization
• Noise stability of functions with low influences: invariance and optimality
• Parameterizing above or below guaranteed values
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Parametrized complexity theory.
• Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• Algorithms with large domination ratio
• Some optimal inapproximability results
• On the advantage over a random assignment
• Proof of a hypercontractive estimate via entropy

This page was built for publication: Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width