Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width

DOI10.1016/J.DAM.2012.04.020zbMATH Open1252.94126OpenAlexW1970944793MaRDI QIDQ713329FDOQ713329

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

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

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)

Cites Work

• Parameterizing above or below guaranteed values
• Parametrized complexity theory.
• Some optimal inapproximability results
• Solving MAX-\(r\)-SAT above a tight lower bound
• Pseudo-Boolean optimization
• Title not available (Why is that?)
• Noise stability of functions with low influences: invariance and optimality
• Improved bounds on Bell numbers and on moments of sums of random variables
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• 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
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Algorithms with large domination ratio
• On the advantage over a random assignment
• Proof of a hypercontractive estimate via entropy

Cited In (3)

• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Title not available (Why is that?)
• 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)