Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

DOI10.1016/J.DAM.2012.04.020MaRDI QIDQ713329zbMATH OpenOpenAlexFDO

Authors G. Gutin, A. Yeo

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 analysispseudo-Boolean functionhypercontractive inequalityFourier 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)

Recommendations

• Proof of a hypercontractive estimate via entropy
• Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions
• On the Fourier spectrum of functions on Boolean cubes
• scientific article; zbMATH DE number 6351506
• scientific article; zbMATH DE number 5062518

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A probabilistic approach to problems parameterized above or below tight bounds
• Algorithms with large domination ratio
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• Improved bounds on Bell numbers and on moments of sums of random variables
• Noise stability of functions with low influences: invariance and optimality
• On the advantage over a random assignment
• Parameterizing above or below guaranteed values
• Parametrized complexity theory.
• Proof of a hypercontractive estimate via entropy
• Pseudo-Boolean optimization
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Solving MAX-\(r\)-SAT above a tight lower bound
• Some optimal inapproximability results
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average

Cited in

(3)

• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• scientific article; zbMATH DE number 5062518 (Why is no real title available?)
• Parameterized constraint satisfaction problems: a survey

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

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