Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Edward Pyne. Derandomizing Logspace with a Small Shared Hard Drive. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{pyne:LIPIcs.CCC.2024.4, author = {Pyne, Edward}, title = {{Derandomizing Logspace with a Small Shared Hard Drive}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {4:1--4:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.4}, URN = {urn:nbn:de:0030-drops-204006}, doi = {10.4230/LIPIcs.CCC.2024.4}, annote = {Keywords: Catalytic computation, space-bounded computation, derandomization} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ilan Doron-Arad, Ariel Kulik, and Hadas Shachnai. Lower Bounds for Matroid Optimization Problems with a Linear Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.56, author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas}, title = {{Lower Bounds for Matroid Optimization Problems with a Linear Constraint}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {56:1--56:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.56}, URN = {urn:nbn:de:0030-drops-201990}, doi = {10.4230/LIPIcs.ICALP.2024.56}, annote = {Keywords: matroid optimization, budgeted problems, knapsack, approximation schemes} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Sonika Arora, Venkatesan T. Chakaravarthy, Kanika Gupta, Neelima Gupta, and Yogish Sabharwal. Replica Placement on Directed Acyclic Graphs. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 213-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{arora_et_al:LIPIcs.FSTTCS.2014.213, author = {Arora, Sonika and Chakaravarthy, Venkatesan T. and Gupta, Kanika and Gupta, Neelima and Sabharwal, Yogish}, title = {{Replica Placement on Directed Acyclic Graphs}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {213--225}, 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.213}, URN = {urn:nbn:de:0030-drops-48449}, doi = {10.4230/LIPIcs.FSTTCS.2014.213}, annote = {Keywords: Approximation Algorithms, LP Rounding} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Archita Agarwal, Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sambuddha Roy, and Yogish Sabharwal. Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 249-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2013.249, author = {Agarwal, Archita and Chakaravarthy, Venkatesan T. and Choudhury, Anamitra Roy and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {249--261}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.249}, URN = {urn:nbn:de:0030-drops-43775}, doi = {10.4230/LIPIcs.FSTTCS.2013.249}, annote = {Keywords: approximation algorithms, set cover problem, tree cover} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Sonika Arora, Venkatesan T. Chakaravarthy, Neelima Gupta, Koyel Mukherjee, and Yogish Sabharwal. Replica Placement via Capacitated Vertex Cover. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 263-274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{arora_et_al:LIPIcs.FSTTCS.2013.263, author = {Arora, Sonika and Chakaravarthy, Venkatesan T. and Gupta, Neelima and Mukherjee, Koyel and Sabharwal, Yogish}, title = {{Replica Placement via Capacitated Vertex Cover}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {263--274}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.263}, URN = {urn:nbn:de:0030-drops-43784}, doi = {10.4230/LIPIcs.FSTTCS.2013.263}, annote = {Keywords: Approximation Algorithms, LP Rounding} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Venkatesan T. Chakaravarthy, Anamitra Roy Choudhury, Sivaramakrishnan R. Natarajan, and Sambuddha Roy. Knapsack Cover Subject to a Matroid Constraint. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2013.275, author = {Chakaravarthy, Venkatesan T. and Choudhury, Anamitra Roy and Natarajan, Sivaramakrishnan R. and Roy, Sambuddha}, title = {{Knapsack Cover Subject to a Matroid Constraint}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {275--286}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.275}, URN = {urn:nbn:de:0030-drops-43795}, doi = {10.4230/LIPIcs.FSTTCS.2013.275}, annote = {Keywords: Approximation Algorithms, LP rounding, Matroid Constraints, Knapsack problems} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Venkatesan T. Chakaravarthy, Arindam Pal, Sambuddha Roy, and Yogish Sabharwal. Scheduling Resources for Executing a Partial Set of Jobs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 199-210, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2012.199, author = {Chakaravarthy, Venkatesan T. and Pal, Arindam and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Scheduling Resources for Executing a Partial Set of Jobs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {199--210}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.199}, URN = {urn:nbn:de:0030-drops-38598}, doi = {10.4230/LIPIcs.FSTTCS.2012.199}, annote = {Keywords: Approximation Algorithms, Partial Covering, Interval Graphs} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Venkatesan T. Chakaravarthy, Natwar Modani, Sivaramakrishnan R. Natarajan, Sambuddha Roy, and Yogish Sabharwal. Density Functions subject to a Co-Matroid Constraint. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 236-248, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2012.236, author = {Chakaravarthy, Venkatesan T. and Modani, Natwar and Natarajan, Sivaramakrishnan R. and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Density Functions subject to a Co-Matroid Constraint}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {236--248}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.236}, URN = {urn:nbn:de:0030-drops-38627}, doi = {10.4230/LIPIcs.FSTTCS.2012.236}, annote = {Keywords: Approximation Algorithms, Submodular Functions, Graph Density} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, and Yogish Sabharwal. A Near-linear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 181-191, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2010.181, author = {Chakaravarthy, Venkatesan T. and Choudhury, Anamitra R. and Sabharwal, Yogish}, title = {{A Near-linear Time Constant Factor Algorithm for Unsplittable Flow Problem on Line with Bag Constraints}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {181--191}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.181}, URN = {urn:nbn:de:0030-drops-28623}, doi = {10.4230/LIPIcs.FSTTCS.2010.181}, annote = {Keywords: Approximation Algorithms; Scheduling; Resource Allocation} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, and Yogish Sabharwal. Finding Independent Sets in Unions of Perfect Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 251-259, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{chakaravarthy_et_al:LIPIcs.FSTTCS.2010.251, author = {Chakaravarthy, Venkatesan T. and Pandit, Vinayaka and Roy, Sambuddha and Sabharwal, Yogish}, title = {{Finding Independent Sets in Unions of Perfect Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {251--259}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.251}, URN = {urn:nbn:de:0030-drops-28683}, doi = {10.4230/LIPIcs.FSTTCS.2010.251}, annote = {Keywords: Approximation Algorithms; Comparability Graphs; Hardness of approximation} }
Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)
Venkatesan T. Chakaravarthy and Sambuddha Roy. Finding Irrefutable Certificates for S_2^p via Arthur and Merlin. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 157-168, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{chakaravarthy_et_al:LIPIcs.STACS.2008.1342, author = {Chakaravarthy, Venkatesan T. and Roy, Sambuddha}, title = {{Finding Irrefutable Certificates for S\underline2^p via Arthur and Merlin}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {157--168}, 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.1342}, URN = {urn:nbn:de:0030-drops-13421}, doi = {10.4230/LIPIcs.STACS.2008.1342}, annote = {Keywords: Symmetric alternation, promise-AM, Karp--Lipton theorem, learning circuits} }