Search Results

Documents authored by Venkitesh, S.

Document
DOI: 10.4230/LIPIcs.ITCS.2025.93
Polynomials, Divided Differences, and Codes

Authors: S. Venkitesh

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Multiplicity codes (Kopparty et al., J. ACM 2014) are multivariate polynomial codes where the codewords are described by evaluations of polynomials (with a degree bound) and their derivatives up to some order (the multiplicity parameter), on a suitably chosen affine set of points. While efficient decoding algorithms were known in some special cases of point sets, by a reduction to univariate multiplicity codes, a general algorithm for list decoding up to the distance of the code when the point set is an arbitrary finite grid, was obtained only recently (Bhandari et al., IEEE TIT 2023). This required the characteristic of the field to be zero or larger than the degree bound, which is somewhat necessary since list decoding up to distance with small output list size is not possible when the characteristic is significantly smaller than the degree. In this work, we present an alternative construction based on divided differences of polynomials, that conceptually resembles the classical multiplicity codes but has good list decodability "insensitive to the field characteristic". We obtain a simple algorithm that list decodes this code up to distance for arbitrary finite grids over all finite fields. Our construction can also be interpreted as a folded Reed-Muller code, which may be of independent interest.
Cite as

S. Venkitesh. Polynomials, Divided Differences, and Codes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 93:1-93:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{venkitesh:LIPIcs.ITCS.2025.93,
  author =	{Venkitesh, S.},
  title =	{{Polynomials, Divided Differences, and Codes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{93:1--93:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.93},
  URN =		{urn:nbn:de:0030-drops-227216},
  doi =		{10.4230/LIPIcs.ITCS.2025.93},
  annote =	{Keywords: Error-correcting code, polynomial code, Reed-Solomon code, Reed-Muller code, folded Reed-Solomon code, folded Reed-Muller code, multiplicity code, divided difference, q-derivative, polynomial method, list decoding, list decoding capacity, linear algebraic list decoding}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.42
On the Probabilistic Degree of an n-Variate Boolean Function

Authors: Srikanth Srinivasan and S. Venkitesh

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}ⁿ → {0,1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x₁,…,x_n), 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.
Cite as

Srikanth Srinivasan and S. Venkitesh. On the Probabilistic Degree of an n-Variate Boolean Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{srinivasan_et_al:LIPIcs.APPROX/RANDOM.2021.42,
  author =	{Srinivasan, Srikanth and Venkitesh, S.},
  title =	{{On the Probabilistic Degree of an n-Variate Boolean Function}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.42},
  URN =		{urn:nbn:de:0030-drops-147356},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.42},
  annote =	{Keywords: truly n-variate, Boolean function, probabilistic polynomial, probabilistic degree}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.28
On the Probabilistic Degrees of Symmetric Boolean Functions

Authors: Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

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).
Cite as

Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. On the Probabilistic Degrees of Symmetric Boolean Functions. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{srinivasan_et_al:LIPIcs.FSTTCS.2019.28,
  author =	{Srinivasan, Srikanth and Tripathi, Utkarsh and Venkitesh, S.},
  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 =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.28},
  URN =		{urn:nbn:de:0030-drops-115908},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.28},
  annote =	{Keywords: Symmetric Boolean function, probabilistic degree}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact