Aarhus University Seal / Aarhus Universitets segl

On the probabilistic degree of an n-variate boolean function

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

Nisan and Szegedy (CC 1994) showed that any Boolean function f : {0, 1}n → {0, 1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x1,..., xn), has degree at least log n − O(log log n). This was improved to a tight (log n − O(1)) bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)). In this paper, we address this question for Probabilistic degree. The function f has probabilistic degree at most d if there is a random real-valued polynomial of degree at most d that agrees with f at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the best-known bounds put it between (log n)1/2−o(1) and O(log n) (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)). Here we can give a near-optimal understanding of the probabilistic degree of n-variate functions f, modulo our lack of understanding of the probabilistic degree of OR. We show that if the probabilistic degree of OR is (log n)c, then the minimum possible probabilistic degree of such an f is at least (log n)c/(c+1)−o(1), and we show this is tight up to (log n)o(1) factors.

OriginalsprogEngelsk
TitelApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021
RedaktørerMary Wootters, Laura Sanita
Antal sider20
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Udgivelsesårsep. 2021
Artikelnummer42
ISBN (Elektronisk)9783959772075
DOI
StatusUdgivet - sep. 2021
Begivenhed24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 - Virtual, Seattle, USA
Varighed: 16 aug. 202118 aug. 2021

Konference

Konference24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021
LandUSA
ByVirtual, Seattle
Periode16/08/202118/08/2021
SerietitelLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind207
ISSN1868-8969

Se relationer på Aarhus Universitet Citationsformater

ID: 224088820