Search Results

Documents authored by Podder, Supartha

Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.27
Decision Tree Complexity Versus Block Sensitivity and Degree

Authors: Rahul Chugh, Supartha Podder, and Swagato Sanyal

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It is known that decision tree complexity is bounded above by the cube of block sensitivity, and the cube of polynomial degree. However, the widest separation between decision tree complexity and each of block sensitivity and degree that is witnessed by known Boolean functions is quadratic. Proving quadratic relations between these measures would resolve several open questions in decision tree complexity. For example, it will imply a tight relation between decision tree complexity and square of randomized decision tree complexity and a tight relation between zero-error randomized decision tree complexity and square of fractional block sensitivity, resolving an open question raised by Aaronson [Aaronson, 2008]. In this work, we investigate the tightness of the existing cubic upper bounds. We improve the cubic upper bounds for many interesting classes of Boolean functions. We show that for graph properties and for functions with a constant number of alternations, the cubic upper bounds can be improved to quadratic. We define a class of Boolean functions, which we call the zebra functions, that comprises Boolean functions where each monotone path from 0ⁿ to 1ⁿ has an equal number of alternations. This class contains the symmetric and monotone functions as its subclasses. We show that for any zebra function, decision tree complexity is at most the square of block sensitivity, and certificate complexity is at most the square of degree. Finally, we show using a lifting theorem of communication complexity by Göös, Pitassi and Watson [Göös et al., 2017] that the task of proving an improved upper bound on the decision tree complexity for all functions is in a sense equivalent to the potentially easier task of proving a similar upper bound on communication complexity for each bi-partition of the input variables, for all functions. In particular, this implies that to bound the decision tree complexity it suffices to bound smaller measures like parity decision tree complexity, subcube decision tree complexity and decision tree rank, that are defined in terms of models that can be efficiently simulated by communication protocols.
Cite as

Rahul Chugh, Supartha Podder, and Swagato Sanyal. Decision Tree Complexity Versus Block Sensitivity and Degree. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chugh_et_al:LIPIcs.FSTTCS.2023.27,
  author =	{Chugh, Rahul and Podder, Supartha and Sanyal, Swagato},
  title =	{{Decision Tree Complexity Versus Block Sensitivity and Degree}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{27:1--27:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.27},
  URN =		{urn:nbn:de:0030-drops-194001},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.27},
  annote =	{Keywords: Query complexity, Graph Property, Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.55
On the Fine-Grained Query Complexity of Symmetric Functions

Authors: Supartha Podder, Penghui Yao, and Zekun Ye

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Watrous conjectured that the randomized and quantum query complexities of symmetric functions are polynomially equivalent, which was resolved by Ambainis and Aaronson [Scott Aaronson and Andris Ambainis, 2014], and was later improved in [André Chailloux, 2019; Shalev Ben-David et al., 2020]. This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to 1/2. Our contributions include the following: 1) An analysis of the optimal success probability of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. We prove that for any quantum algorithm computing these two functions using T queries, there exist randomized algorithms using poly(T) queries that achieve the same success probability as the quantum algorithm, even if the success probability is arbitrarily close to 1/2. These two classes of functions are instrumental in analyzing general symmetric functions. 2) We establish that for any total symmetric Boolean function f, if a quantum algorithm uses T queries to compute f with success probability 1/2+β, then there exists a randomized algorithm using O(T²) queries to compute f with success probability 1/2 + Ω(δβ²) on a 1-δ fraction of inputs, where β,δ can be arbitrarily small positive values. As a corollary, we prove a randomized version of Aaronson-Ambainis Conjecture [Scott Aaronson and Andris Ambainis, 2014] for total symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. 3) We present polynomial equivalences for several fundamental complexity measures of partial symmetric Boolean functions. Specifically, we first prove that for certain partial symmetric Boolean functions, quantum query complexity is at most quadratic in approximate degree for any error arbitrarily close to 1/2. Next, we show exact quantum query complexity is at most quadratic in degree. Additionally, we give the tight bounds of several complexity measures, indicating their polynomial equivalence. Conversely, we exhibit an exponential separation between randomized and exact quantum query complexity for certain partial symmetric Boolean functions.
Cite as

Supartha Podder, Penghui Yao, and Zekun Ye. On the Fine-Grained Query Complexity of Symmetric Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{podder_et_al:LIPIcs.ISAAC.2023.55,
  author =	{Podder, Supartha and Yao, Penghui and Ye, Zekun},
  title =	{{On the Fine-Grained Query Complexity of Symmetric Functions}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.55},
  URN =		{urn:nbn:de:0030-drops-193570},
  doi =		{10.4230/LIPIcs.ISAAC.2023.55},
  annote =	{Keywords: Query complexity, Symmetric functions, Quantum advantages}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.61
Communication Memento: Memoryless Communication Complexity

Authors: Srinivasan Arunachalam and Supartha Podder

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the communication complexity of computing functions F: {0,1}ⁿ × {0,1}ⁿ → {0,1} in the memoryless communication model. Here, Alice is given x ∈ {0,1}ⁿ, Bob is given y ∈ {0,1}ⁿ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x (in particular, her reply is independent of the information from the previous rounds); the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that some of these different variants of our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS'13), space-bounded communication complexity by Brody et al. (ITCS'13) and the overlay communication complexity by Papakonstantinou et al. (CCC'14). Thus the memoryless communication complexity model provides a unified framework to study all these space-bounded communication complexity models. We establish the following main results: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose model of computation; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c > 1 for which the memoryless communication complexity is at least c log n? Note that c ≥ 2+ε would imply a Ω(n^{2+ε}) lower bound for general formula size, improving upon the best lower bound by [Nečiporuk, 1966].
Cite as

Srinivasan Arunachalam and Supartha Podder. Communication Memento: Memoryless Communication Complexity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.ITCS.2021.61,
  author =	{Arunachalam, Srinivasan and Podder, Supartha},
  title =	{{Communication Memento: Memoryless Communication Complexity}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{61:1--61:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.61},
  URN =		{urn:nbn:de:0030-drops-136007},
  doi =		{10.4230/LIPIcs.ITCS.2021.61},
  annote =	{Keywords: Communication complexity, space complexity, branching programs, garden-hose model, quantum computing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.17
Graph Properties in Node-Query Setting: Effect of Breaking Symmetry

Authors: Nikhil Balaji, Samir Datta, Raghav Kulkarni, and Supartha Podder

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The query complexity of graph properties is well-studied when queries are on the edges. We investigate the same when queries are on the nodes. In this setting a graph G = (V,E) on n vertices and a property P are given. A black-box access to an unknown subset S of V is provided via queries of the form "Does i belong to S?". We are interested in the minimum number of queries needed in the worst case in order to determine whether G[S] - the subgraph of G induced on S - satisfies P. Our primary motivation to study this model comes from the fact that it allows us to initiate a systematic study of breaking symmetry in the context of query complexity of graph properties. In particular, we focus on the hereditary graph properties - properties that are closed under deletion of vertices as well as edges. The famous Evasiveness Conjecture asserts that even with a minimal symmetry assumption on G, namely that of vertex-transitivity, the query complexity for any hereditary graph property in our setting is the worst possible, i.e., n. We show that in the absence of any symmetry on G it can fall as low as O(n^{1/(d + 1)}) where d denotes the minimum possible degree of a minimal forbidden sub-graph for P. In particular, every hereditary property benefits at least quadratically. The main question left open is: Can it go exponentially low for some hereditary property? We show that the answer is no for any hereditary property with finitely many forbidden subgraphs by exhibiting a bound of Omega(n^{1/k}) for a constant k depending only on the property. For general ones we rule out the possibility of the query complexity falling down to constant by showing Omega(log(n)*log(log(n))) bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erdos and Rado.
Cite as

Nikhil Balaji, Samir Datta, Raghav Kulkarni, and Supartha Podder. Graph Properties in Node-Query Setting: Effect of Breaking Symmetry. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{balaji_et_al:LIPIcs.MFCS.2016.17,
  author =	{Balaji, Nikhil and Datta, Samir and Kulkarni, Raghav and Podder, Supartha},
  title =	{{Graph Properties in Node-Query Setting: Effect of Breaking Symmetry}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.17},
  URN =		{urn:nbn:de:0030-drops-64329},
  doi =		{10.4230/LIPIcs.MFCS.2016.17},
  annote =	{Keywords: query complexity, graph properties, symmetry and computation, forbidden subgraph}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.48
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism

Authors: Raghav Kulkarni and Supartha Podder

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Let H be a (non-empty) graph on n vertices, possibly containing isolated vertices. Let f_H(G) = 1 iff the input graph G on n vertices contains H as a (not necessarily induced) subgraph. Let alpha_H denote the cardinality of a maximum independent set of H. In this paper we show: Q(f_H) = Omega( sqrt{alpha_H * n}), where Q(f_H) denotes the quantum query complexity of f_H. As a consequence we obtain lower bounds for Q(f_H) in terms of several other parameters of H such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that Q(f_H) = Omega(n^{3/4}) for any H, improving on the previously best known bound of Omega(n^{2/3}) [M. Santha/A. Chi-Chih Yao, unpublished manuscript]. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our Omega(n^{3/4}) bound for Q(f_H) matches the square root of the current best known bound for the randomized query complexity of f_H, which is Omega(n^{3/2}) due to Groger. Interestingly, the randomized bound of Omega(alpha_H * n) for f_H still remains open. We also study the Subgraph Homomorphism Problem, denoted by f_{[H]}, and show that Q(f_{[H]}) = Omega(n). Finally we extend our results to the 3-uniform hypergraphs. In particular, we show an Omega(n^{4/5}) bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known Omega(n^{3/4}) bound. For the Subgraph Homomorphism, we obtain an Omega(n^{3/2}) bound for the same.
Cite as

Raghav Kulkarni and Supartha Podder. Quantum Query Complexity of Subgraph Isomorphism and Homomorphism. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kulkarni_et_al:LIPIcs.STACS.2016.48,
  author =	{Kulkarni, Raghav and Podder, Supartha},
  title =	{{Quantum Query Complexity of Subgraph Isomorphism and Homomorphism}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.48},
  URN =		{urn:nbn:de:0030-drops-57495},
  doi =		{10.4230/LIPIcs.STACS.2016.48},
  annote =	{Keywords: quantum query complexity, subgraph isomorphism, monotone graph properties}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.481
New Bounds for the Garden-Hose Model

Authors: Hartmut Klauck and Supartha Podder

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown Theta(n) bounds for Inner Product mod 2 and Disjointness), as well as an O(n * log^3(n) upper bound for the Distributed Majority function (previously conjectured to have quadratic complexity). We show an efficient simulation of formulae made of AND, OR, XOR gates in the garden-hose model, which implies that lower bounds on the garden-hose complexity GH(f) of the order Omega(n^{2+epsilon}) will be hard to obtain for explicit functions. Furthermore we study a time-bounded variant of the model, in which even modest savings in time can lead to exponential lower bounds on the size of garden-hose protocols.
Cite as

Hartmut Klauck and Supartha Podder. New Bounds for the Garden-Hose Model. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 481-492, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{klauck_et_al:LIPIcs.FSTTCS.2014.481,
  author =	{Klauck, Hartmut and Podder, Supartha},
  title =	{{New Bounds for the Garden-Hose Model}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{481--492},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.481},
  URN =		{urn:nbn:de:0030-drops-48657},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.481},
  annote =	{Keywords: Space Complexity, Communication Complexity, Garden-Hose Model}
}
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