License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.28
URN: urn:nbn:de:0030-drops-115908
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11590/
Go to the corresponding LIPIcs Volume Portal

Srinivasan, Srikanth ; Tripathi, Utkarsh ; Venkitesh, S.

On the Probabilistic Degrees of Symmetric Boolean Functions

pdf-format:
LIPIcs-FSTTCS-2019-28.pdf (0.5 MB)

Abstract

The probabilistic degree of a Boolean function f:{0,1}^n -> {0,1} is defined to be the smallest d such that there is a random polynomial P of degree at most d that agrees with f at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees of Boolean functions - specifically symmetric Boolean functions - have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems.
In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).

BibTeX - Entry

@InProceedings{srinivasan_et_al:LIPIcs:2019:11590,
  author =	{Srikanth Srinivasan and Utkarsh Tripathi and S. Venkitesh},
  title =	{{On the Probabilistic Degrees of Symmetric Boolean Functions}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11590},
  URN =		{urn:nbn:de:0030-drops-115908},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.28},
  annote =	{Keywords: Symmetric Boolean function, probabilistic degree}
}

Keywords: Symmetric Boolean function, probabilistic degree
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI