Search Results

Documents authored by Kayal, Chandrima

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.71
Approximate Degree Composition for Recursive Functions

Authors: Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, and Nitin Saurabh

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

Abstract
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e. functions obtained by composing a base function with itself a number of times. Let h^d denote the standard d-fold composition of the base function h. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: - The outer function f:{0,1}ⁿ → {0,1} is a recursive function of the form h^d, with h being any base function and d = Ω(log log n). - The inner function is a recursive function of the form h^d, with h being any constant arity base function (other than AND and OR) and d = Ω(log log n), where n is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be efficiently eliminated if the inner or outer function is a recursive function.
Cite as

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, and Nitin Saurabh. Approximate Degree Composition for Recursive Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 71:1-71:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2024.71,
  author =	{Chakraborty, Sourav and Kayal, Chandrima and Mittal, Rajat and Paraashar, Manaswi and Saurabh, Nitin},
  title =	{{Approximate Degree Composition for Recursive Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{71:1--71:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.71},
  URN =		{urn:nbn:de:0030-drops-210642},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.71},
  annote =	{Keywords: Approximate degree, Boolean function, Composition theorem}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.63
On the Composition of Randomized Query Complexity and Approximate Degree

Authors: Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh

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

Abstract
For any Boolean functions f and g, the question whether R(f∘g) = Θ̃(R(f) ⋅ R(g)), is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg̃(f∘g) = Θ̃(deg̃(f)⋅deg̃(g)). These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R and deg̃ compose. A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g) = Ω(noisyR(f)⋅ R(g)). This implies that composition holds whenever noisyR(f) = Θ̃(R(f)). We show two results: 1. When R(f) = Θ(n), then noisyR(f) = Θ(R(f)). In other words, composition holds whenever the randomized query complexity of the outer function is full. 2. If R composes with respect to an outer function, then noisyR also composes with respect to the same outer function. On the other hand, no result of the type deg̃(f∘g) = Ω(M(f) ⋅ deg̃(g)) (for some non-trivial complexity measure M(⋅)) was known to the best of our knowledge. We prove that deg̃(f∘g) = Ω̃(√{bs(f)} ⋅ deg̃(g)), where bs(f) is the block sensitivity of f. This implies that deg̃ composes when deg̃(f) is asymptotically equal to √{bs(f)}. It is already known that both R and deg̃ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.
Cite as

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the Composition of Randomized Query Complexity and Approximate Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 63:1-63:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2023.63,
  author =	{Chakraborty, Sourav and Kayal, Chandrima and Mittal, Rajat and Paraashar, Manaswi and Sanyal, Swagato and Saurabh, Nitin},
  title =	{{On the Composition of Randomized Query Complexity and Approximate Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{63:1--63:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.63},
  URN =		{urn:nbn:de:0030-drops-188883},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.63},
  annote =	{Keywords: Approximate degree, Boolean functions, Composition Theorem, Partial functions, Randomized Query Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.36
Separations Between Combinatorial Measures for Transitive Functions

Authors: Sourav Chakraborty, Chandrima Kayal, and Manaswi Paraashar

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The role of symmetry in Boolean functions f:{0, 1}ⁿ → {0, 1} has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are invariant under the action of 𝖲_n, is an important class of functions in the study of Boolean functions. A function f:{0, 1}ⁿ → {0, 1} is called transitive (or weakly-symmetric) if there exists a transitive group 𝖦 of 𝖲_n such that f is invariant under the action of 𝖦. In other words, the value of the function remains unchanged even after the input bits of f are moved around according to some permutation σ ∈ 𝖦. Understanding various complexity measures of transitive functions has been a rich area of research for the past few decades. This work studies transitive functions in light of several combinatorial measures. The question that we try to address in this paper is what are the maximum separations between various pairs of combinatorial measures for transitive functions. Such study for general Boolean functions has been going on for many years. Aaronson et al. (STOC, 2021) have nicely compiled the current best-known results for general Boolean functions. But before this paper, no such systematic study had been done on the case of transitive functions. Separations between a pair of combinatorial measures are shown by constructing interesting functions that demonstrate the separation. Over the past three decades, various interesting classes of functions have been designed for this purpose. In this context, one of the celebrated classes of functions is the "pointer functions". Ambainis et al. (JACM, 2017) constructed several functions, which are modifications of the pointer function in Göös et al. (SICOMP, 2018 / FOCS, 2015), to demonstrate the separation between various pairs of measures. In the last few years, pointer functions have been used to show separation between various other pairs of measures (Eg: Mukhopadhyay et al. (FSTTCS, 2015), Ben-David et al. (ITCS, 2017), Göös et al. (ToCT, 2018 / ICALP, 2017)). However, the pointer functions themselves are not transitive. Based on the various kinds of pointer functions, we construct new transitive functions, which we use to demonstrate similar separations between various pairs of combinatorial measures as demonstrated by the original pointer functions. Our construction of transitive functions depends crucially on the construction of particular classes of transitive groups whose actions, though involved, help to preserve certain structural features of the input strings. The transitive groups we construct may be of independent interest in other areas of mathematics and theoretical computer science. We summarize the current knowledge of relations between various combinatorial measures of transitive functions in a table similar to the table compiled by Aaronson et al. (STOC, 2021) for general functions.
Cite as

Sourav Chakraborty, Chandrima Kayal, and Manaswi Paraashar. Separations Between Combinatorial Measures for Transitive Functions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ICALP.2022.36,
  author =	{Chakraborty, Sourav and Kayal, Chandrima and Paraashar, Manaswi},
  title =	{{Separations Between Combinatorial Measures for Transitive Functions}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.36},
  URN =		{urn:nbn:de:0030-drops-163779},
  doi =		{10.4230/LIPIcs.ICALP.2022.36},
  annote =	{Keywords: Transitive functions, Combinatorial complexity of Boolean functions}
}
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 Imprint Privacy Contact