Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Nils Vortmeier and Thomas Zeume. Dynamic Complexity of Parity Exists Queries. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 37:1-37:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{vortmeier_et_al:LIPIcs.CSL.2020.37, author = {Vortmeier, Nils and Zeume, Thomas}, title = {{Dynamic Complexity of Parity Exists Queries}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {37:1--37:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-132-0}, ISSN = {1868-8969}, year = {2020}, volume = {152}, editor = {Fern\'{a}ndez, Maribel and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.37}, URN = {urn:nbn:de:0030-drops-116805}, doi = {10.4230/LIPIcs.CSL.2020.37}, annote = {Keywords: Dynamic complexity, parity quantifier, arity hierarchy} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 21:1-21:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{datta_et_al:LIPIcs.ISAAC.2018.21, author = {Datta, Samir and Kulkarni, Raghav and Kumar, Ashish and Mukherjee, Anish}, title = {{Planar Maximum Matching: Towards a Parallel Algorithm}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.21}, URN = {urn:nbn:de:0030-drops-99695}, doi = {10.4230/LIPIcs.ISAAC.2018.21}, annote = {Keywords: maximum matching, planar graphs, parallel complexity, reductions} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee. Shortest k-Disjoint Paths via Determinants. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 19:1-19:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{datta_et_al:LIPIcs.FSTTCS.2018.19, author = {Datta, Samir and Iyer, Siddharth and Kulkarni, Raghav and Mukherjee, Anish}, title = {{Shortest k-Disjoint Paths via Determinants}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {19:1--19:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-093-4}, ISSN = {1868-8969}, year = {2018}, volume = {122}, editor = {Ganguly, Sumit and Pandya, Paritosh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.19}, URN = {urn:nbn:de:0030-drops-99183}, doi = {10.4230/LIPIcs.FSTTCS.2018.19}, annote = {Keywords: disjoint paths, planar graph, parallel algorithm, cycle cover, determinant, inclusion-exclusion} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
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)
@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} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Samir Datta, Raghav Kulkarni, and Anish Mukherjee. Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 28:1-28:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{datta_et_al:LIPIcs.MFCS.2016.28, author = {Datta, Samir and Kulkarni, Raghav and Mukherjee, Anish}, title = {{Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {28:1--28:12}, 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.28}, URN = {urn:nbn:de:0030-drops-64436}, doi = {10.4230/LIPIcs.MFCS.2016.28}, annote = {Keywords: maximum matching, approximation scheme, logspace, planar graphs} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
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)
@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} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Samir Datta, Arjun Gopalan, Raghav Kulkarni, and Raghunath Tewari. Improved Bounds for Bipartite Matching on Surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 254-265, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{datta_et_al:LIPIcs.STACS.2012.254, author = {Datta, Samir and Gopalan, Arjun and Kulkarni, Raghav and Tewari, Raghunath}, title = {{Improved Bounds for Bipartite Matching on Surfaces}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {254--265}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.254}, URN = {urn:nbn:de:0030-drops-34141}, doi = {10.4230/LIPIcs.STACS.2012.254}, annote = {Keywords: Perfect Matching, Graphs on Surfaces, Space Complexity, NC, UL} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N. Variyam Vinodchandran. Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 579-590, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
@InProceedings{datta_et_al:LIPIcs.STACS.2011.579, author = {Datta, Samir and Kulkarni, Raghav and Tewari, Raghunath and Vinodchandran, N. Variyam}, title = {{Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {579--590}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.579}, URN = {urn:nbn:de:0030-drops-30450}, doi = {10.4230/LIPIcs.STACS.2011.579}, annote = {Keywords: perfect matching, bounded genus graphs, isolation problem} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik. Evasiveness and the Distribution of Prime Numbers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 71-82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{babai_et_al:LIPIcs.STACS.2010.2445, author = {Babai, L\'{a}szl\'{o} and Banerjee, Anandam and Kulkarni, Raghav and Naik, Vipul}, title = {{Evasiveness and the Distribution of Prime Numbers}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {71--82}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2445}, URN = {urn:nbn:de:0030-drops-24451}, doi = {10.4230/LIPIcs.STACS.2010.2445}, annote = {Keywords: Decision tree complexity, evasiveness, graph property, group action, Dirichlet primes, Extended Riemann Hypothesis} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 229-240, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)
@InProceedings{datta_et_al:LIPIcs.STACS.2008.1346, author = {Datta, Samir and Kulkarni, Raghav and Roy, Sambuddha}, title = {{Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {229--240}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1346}, URN = {urn:nbn:de:0030-drops-13465}, doi = {10.4230/LIPIcs.STACS.2008.1346}, annote = {Keywords: } }
Feedback for Dagstuhl Publishing