Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
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)
@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} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
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)
@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} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
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)
@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} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
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)
@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} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
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)
@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} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
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)
@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} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
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)
@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.} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
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)
@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} }
Feedback for Dagstuhl Publishing