8 Search Results for "Mukhopadhyay, Sagnik"


Document
Track A: Algorithms, Complexity and Games
Sublinear-Round Parallel Matroid Intersection

Authors: Joakim Blikstad

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


Abstract
Despite a lot of recent progress in obtaining faster sequential matroid intersection algorithms, the fastest parallel poly(n)-query algorithm was still the straightforward O(n)-round parallel implementation of Edmonds' augmenting paths algorithm from the 1960s. Very recently, Chakrabarty-Chen-Khanna [FOCS'21] showed the lower bound that any, possibly randomized, parallel matroid intersection algorithm making poly(n) rank-queries requires Ω̃(n^{1/3}) rounds of adaptivity. They ask, as an open question, if the lower bound can be improved to Ω̃(n), or if there can be sublinear-round, poly(n)-query algorithms for matroid intersection. We resolve this open problem by presenting the first sublinear-round parallel matroid intersection algorithms. Perhaps surprisingly, we do not only break the Õ(n)-barrier in the rank-oracle model, but also in the weaker independence-oracle model. Our rank-query algorithm guarantees O(n^{3/4}) rounds of adaptivity, while the independence-query algorithm uses O(n^{7/8}) rounds of adaptivity, both making a total of poly(n) queries.

Cite as

Joakim Blikstad. Sublinear-Round Parallel Matroid Intersection. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{blikstad:LIPIcs.ICALP.2022.25,
  author =	{Blikstad, Joakim},
  title =	{{Sublinear-Round Parallel Matroid Intersection}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{25:1--25:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.25},
  URN =		{urn:nbn:de:0030-drops-163662},
  doi =		{10.4230/LIPIcs.ICALP.2022.25},
  annote =	{Keywords: Matroid Intersection, Combinatorial Optimization, Parallel Algorithms}
}
Document
Data Structures Lower Bounds and Popular Conjectures

Authors: Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
In this paper, we investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NCC) of Li and Li [Li and Li, 2004] and several data structure problems such as non-adaptive function inversion of Hellman [M. Hellman, 1980] and the well-studied problem of polynomial evaluation and interpolation. In turn these data structure problems imply super-linear circuit lower bounds for explicit functions such as integer sorting and multi-point polynomial evaluation.

Cite as

Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová. Data Structures Lower Bounds and Popular Conjectures. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ESA.2021.39,
  author =	{Dvo\v{r}\'{a}k, Pavel and Kouck\'{y}, Michal and Kr\'{a}l, Karel and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{Data Structures Lower Bounds and Popular Conjectures}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.39},
  URN =		{urn:nbn:de:0030-drops-146207},
  doi =		{10.4230/LIPIcs.ESA.2021.39},
  annote =	{Keywords: Data structures, Circuits, Lower bounds, Network Coding Conjecture}
}
Document
Track A: Algorithms, Complexity and Games
Breaking O(nr) for Matroid Intersection

Authors: Joakim Blikstad

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
We present algorithms that break the Õ(nr)-independence-query bound for the Matroid Intersection problem for the full range of r; where n is the size of the ground set and r ≤ n is the size of the largest common independent set. The Õ(nr) bound was due to the efficient implementations [CLSSW FOCS'19; Nguyên 2019] of the classic algorithm of Cunningham [SICOMP'86]. It was recently broken for large r (r = ω(√n)), first by the Õ(n^{1.5}/ε^{1.5})-query (1-ε)-approximation algorithm of CLSSW [FOCS'19], and subsequently by the Õ(n^{6/5}r^{3/5})-query exact algorithm of BvdBMN [STOC'21]. No algorithm - even an approximation one - was known to break the Õ(nr) bound for the full range of r. We present an Õ(n√r/ε)-query (1-ε)-approximation algorithm and an Õ(nr^{3/4})-query exact algorithm. Our algorithms improve the Õ(nr) bound and also the bounds by CLSSW and BvdBMN for the full range of r.

Cite as

Joakim Blikstad. Breaking O(nr) for Matroid Intersection. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{blikstad:LIPIcs.ICALP.2021.31,
  author =	{Blikstad, Joakim},
  title =	{{Breaking O(nr) for Matroid Intersection}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.31},
  URN =		{urn:nbn:de:0030-drops-141004},
  doi =		{10.4230/LIPIcs.ICALP.2021.31},
  annote =	{Keywords: Matroid Intersection, Combinatorial Optimization, Approximation Algorithms}
}
Document
Equality Alone Does not Simulate Randomness

Authors: Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)


Abstract
The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is "Equality". In this work we show that even allowing access to an "Equality" oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on n bits with randomized one-sided communication complexity O(log n), but such that every deterministic protocol with access to "Equality" oracle needs Omega(n) cost to compute it. Additionally we exhibit a natural and strict infinite hierarchy within BPP, starting with the class P^{EQ} at its bottom.

Cite as

Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality Alone Does not Simulate Randomness. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 14:1-14:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2019.14,
  author =	{Chattopadhyay, Arkadev and Lovett, Shachar and Vinyals, Marc},
  title =	{{Equality Alone Does not Simulate Randomness}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{14:1--14:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.14},
  URN =		{urn:nbn:de:0030-drops-108368},
  doi =		{10.4230/LIPIcs.CCC.2019.14},
  annote =	{Keywords: Communication lower bound, derandomization}
}
Document
Lifting Theorems for Equality

Authors: Bruno Loff and Sagnik Mukhopadhyay

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
We show a deterministic simulation (or lifting) theorem for composed problems f o Eq_n where the inner function (the gadget) is Equality on n bits. When f is a total function on p bits, it is easy to show via a rank argument that the communication complexity of f o Eq_n is Omega(deg(f) * n). However, there is a surprising counter-example of a partial function f on p bits, such that any completion f' of f has deg(f') = Omega(p), and yet f o Eq_n has communication complexity O(n). Nonetheless, we are able to show that the communication complexity of f o Eq_n is at least D(f) * n for a complexity measure D(f) which is closely related to the AND-query complexity of f and is lower-bounded by the logarithm of the leaf complexity of f. As a corollary, we also obtain lifting theorems for the set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the NOR gadget. As an application, we prove a tight lower-bound for the deterministic communication complexity of the communication problem, where Alice and Bob are each given p-many n-bit strings, with the promise that either all of the strings are distinct, or all-but-one of the strings are distinct, and they wish to know which is the case. We show that the complexity of this problem is Theta(p * n).

Cite as

Bruno Loff and Sagnik Mukhopadhyay. Lifting Theorems for Equality. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{loff_et_al:LIPIcs.STACS.2019.50,
  author =	{Loff, Bruno and Mukhopadhyay, Sagnik},
  title =	{{Lifting Theorems for Equality}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{50:1--50:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.50},
  URN =		{urn:nbn:de:0030-drops-102892},
  doi =		{10.4230/LIPIcs.STACS.2019.50},
  annote =	{Keywords: Communication complexity, Query complexity, Simulation theorem, Equality function}
}
Document
Lower Bounds for Elimination via Weak Regularity

Authors: Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let f: {0,1}^2n -> {0,1} be any boolean function. Alice and Bob get k inputs x_1, ..., x_k and y_1, ..., y_k respectively, with x_i,y_i in {0,1}^n. They want to output a k-bit vector v, such that there exists one index i for which v_i is not equal f(x_i,y_i). We prove a general result lower bounding the randomized communication complexity of the elimination problem for f using its discrepancy. Consequently, we obtain strong lower bounds for the functions Inner-Product and Greater-Than, that work for exponentially larger values of k than the best previous bounds. To prove our result, we use a pseudo-random notion called regularity that was first used by Raz and Wigderson. We show that functions with small discrepancy are regular. We also observe that a weaker notion, that we call weak-regularity, already implies hardness of elimination. Finally, we give a different proof, borrowing ideas from Viola, to show that Greater-Than is weakly regular.

Cite as

Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Lower Bounds for Elimination via Weak Regularity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.STACS.2017.21,
  author =	{Chattopadhyay, Arkadev and Dvor\'{a}k, Pavel and Kouck\'{y}, Michal and Loff, Bruno and Mukhopadhyay, Sagnik},
  title =	{{Lower Bounds for Elimination via Weak Regularity}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.21},
  URN =		{urn:nbn:de:0030-drops-70128},
  doi =		{10.4230/LIPIcs.STACS.2017.21},
  annote =	{Keywords: communication complexity, elimination, discrepancy, regularity, greater-than}
}
Document
Towards Better Separation between Deterministic and Randomized Query Complexity

Authors: Sagnik Mukhopadhyay and Swagato Sanyal

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R_0(F)) and randomized one-sided error query complexity (R_1(F)): R_1(F) = ~O(sqrt{D(F)) and R_0(F)=~O(D(F))^3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R_0(f)=Omega(D(f))^0.753.. . This also shows widest separation between R_1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R_0(f), and polynomial separation between R_0(f) and R_1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.

Cite as

Sagnik Mukhopadhyay and Swagato Sanyal. Towards Better Separation between Deterministic and Randomized Query Complexity. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 206-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{mukhopadhyay_et_al:LIPIcs.FSTTCS.2015.206,
  author =	{Mukhopadhyay, Sagnik and Sanyal, Swagato},
  title =	{{Towards Better Separation between Deterministic and Randomized Query Complexity}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{206--220},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.206},
  URN =		{urn:nbn:de:0030-drops-56467},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.206},
  annote =	{Keywords: Deterministic Decision Tree, Randomized Decision Tree, Query Complexity, Models of Computation.}
}
Document
Tribes Is Hard in the Message Passing Model

Authors: Arkadev Chattopadhyay and Sagnik Mukhopadhyay

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
We consider the point-to-point message passing model of communication in which there are $k$ processors with individual private inputs, each n-bit long. Each processor is located at the node of an underlying undirected graph and has access to private random coins. An edge of the graph is a private channel of communication between its endpoints. The processors have to compute a given function of all their inputs by communicating along these channels. While this model has been widely used in distributed computing, strong lower bounds on the amount of communication needed to compute simple functions have just begun to appear. In this work, we prove a tight lower bound of \Omega(kn) on the communication needed for computing the Tribes function, when the underlying graph is a star of k+1 nodes that has k leaves with inputs and a center with no input. A lower bound on this topology easily implies comparable bounds for others. Our lower bounds are obtained by building upon the recent information theoretic techniques of Braverman et al. ([4], FOCS'13) and combining it with the earlier work of Jayram, Kumar and Sivakumar ([10], STOC'03). This approach yields information complexity bounds that are of independent interest.

Cite as

Arkadev Chattopadhyay and Sagnik Mukhopadhyay. Tribes Is Hard in the Message Passing Model. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 224-237, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.STACS.2015.224,
  author =	{Chattopadhyay, Arkadev and Mukhopadhyay, Sagnik},
  title =	{{Tribes Is Hard in the Message Passing Model}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{224--237},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.224},
  URN =		{urn:nbn:de:0030-drops-49162},
  doi =		{10.4230/LIPIcs.STACS.2015.224},
  annote =	{Keywords: communication complexity, Tribes, information complexity, direct-sum}
}
  • Refine by Author
  • 4 Mukhopadhyay, Sagnik
  • 3 Chattopadhyay, Arkadev
  • 2 Blikstad, Joakim
  • 2 Koucký, Michal
  • 2 Loff, Bruno
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Matroids and greedoids
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Communication complexity
  • 2 Theory of computation → Discrete optimization
  • 1 Theory of computation → Circuit complexity
  • Show More...

  • Refine by Keyword
  • 2 Combinatorial Optimization
  • 2 Matroid Intersection
  • 2 communication complexity
  • 1 Approximation Algorithms
  • 1 Circuits
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2015
  • 2 2019
  • 2 2021
  • 1 2017
  • 1 2022

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