English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

This paper makes two contributions towards determining some well-studiedoptimal constants in Fourier analysis \newa{of Boolean functions} andhigh-dimensional geometry.  \begin{enumerate}  \item It has been known since 1994 \cite{GL:94} that every linear thresholdfunction has squared Fourier mass at least 1/2 on its degree-0 and degree-1coefficients. Denote the minimum such Fourier mass by $\w^{\leq 1}[\ltf]$,where the minimum is taken over all $n$-variable linear threshold functions andall $n \ge 0$. Benjamini, Kalai and Schramm \cite{BKS:99} have conjectured thatthe true value of $\w^{\leq 1}[\ltf]$ is $2/\pi$. We make progress on thisconjecture by proving that $\w^{\leq 1}[\ltf] \geq 1/2 + c$ for some absoluteconstant $c>0$. The key ingredient in our proof is a "robust" version of thewell-known Khintchine inequality in functional analysis, which we believe maybe of independent interest.  \item We give an algorithm with the following property: given any $\eta > 0$,the algorithm runs in time $2^{\poly(1/\eta)}$ and determines the value of$\w^{\leq 1}[\ltf]$ up to an additive error of $\pm\eta$. We give a similar$2^{{\poly(1/\eta)}}$-time algorithm to determine \emph{Tomaszewski's constant}to within an additive error of $\pm \eta$; this is the minimum (over allorigin-centered hyperplanes $H$) fraction of points in $\{-1,1\}^n$ that liewithin Euclidean distance 1 of $H$. Tomaszewski's constant is conjectured to be1/2; lower bounds on it have been given by Holzman and Kleitman \cite{HK92} andindependently by Ben-Tal, Nemirovski and Roos \cite{BNR02}.  Our algorithms combine tools from anti-concentration of sums of independentrandom variables, Fourier analysis, and Hermite analysis of linear thresholdfunctions.  \end{enumerate}

A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry