LIPIcs, Volume 18
FSTTCS 2012, December 15-17, 2012, Hyderabad, India
Editors: Deepak D'Souza, Jaikumar Radhakrishnan, and Kavitha Telikepalli
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Arghya Chakraborty and Rahul Vaze. Online Facility Location with Weights and Congestion. 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. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2023.6, author = {Chakraborty, Arghya and Vaze, Rahul}, title = {{Online Facility Location with Weights and Congestion}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {6:1--6:22}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.6}, URN = {urn:nbn:de:0030-drops-193797}, doi = {10.4230/LIPIcs.FSTTCS.2023.6}, annote = {Keywords: online algorithms, online facility location, probabilistic method, weighted-requests, congestion} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar. Criticality of AC⁰-Formulae. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{harsha_et_al:LIPIcs.CCC.2023.19, author = {Harsha, Prahladh and Molli, Tulasimohan and Shankar, Ashutosh}, title = {{Criticality of AC⁰-Formulae}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {19:1--19:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.19}, URN = {urn:nbn:de:0030-drops-182898}, doi = {10.4230/LIPIcs.CCC.2023.19}, annote = {Keywords: AC⁰ circuits, AC⁰ formulae, criticality, switching lemma, correlation bounds} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Florian Barth, Stefan Funke, and Claudius Proissl. An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{barth_et_al:LIPIcs.ESA.2022.14, author = {Barth, Florian and Funke, Stefan and Proissl, Claudius}, title = {{An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {14:1--14:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.14}, URN = {urn:nbn:de:0030-drops-169525}, doi = {10.4230/LIPIcs.ESA.2022.14}, annote = {Keywords: Parametric Shortest Paths, Extreme Shortest Paths} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Shyam S. Dhamapurkar, Shubham Vivek Pawar, and Jaikumar Radhakrishnan. Set Membership with Two Classical and Quantum Bit Probes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dhamapurkar_et_al:LIPIcs.ICALP.2022.52, author = {Dhamapurkar, Shyam S. and Pawar, Shubham Vivek and Radhakrishnan, Jaikumar}, title = {{Set Membership with Two Classical and Quantum Bit Probes}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {52:1--52:19}, 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.52}, URN = {urn:nbn:de:0030-drops-163932}, doi = {10.4230/LIPIcs.ICALP.2022.52}, annote = {Keywords: set membership problem, bit probe complexity, graphs with high girth, quantum data structure} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Telikepalli Kavitha. Fairly Popular Matchings and Optimality. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kavitha:LIPIcs.STACS.2022.41, author = {Kavitha, Telikepalli}, title = {{Fairly Popular Matchings and Optimality}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {41:1--41:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.41}, URN = {urn:nbn:de:0030-drops-158516}, doi = {10.4230/LIPIcs.STACS.2022.41}, annote = {Keywords: Bipartite graphs, Stable matchings, Mixed matchings, Polytopes} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mande_et_al:LIPIcs.STACS.2022.49, author = {Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail}, title = {{One-Way Communication Complexity and Non-Adaptive Decision Trees}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {49:1--49:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.49}, URN = {urn:nbn:de:0030-drops-158598}, doi = {10.4230/LIPIcs.STACS.2022.49}, annote = {Keywords: Decision trees, communication complexity, composed Boolean functions} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Jaikumar Radhakrishnan and Aravind Srinivasan. Property B: Two-Coloring Non-Uniform Hypergraphs. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 31:1-31:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{radhakrishnan_et_al:LIPIcs.FSTTCS.2021.31, author = {Radhakrishnan, Jaikumar and Srinivasan, Aravind}, title = {{Property B: Two-Coloring Non-Uniform Hypergraphs}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {31:1--31:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.31}, URN = {urn:nbn:de:0030-drops-155428}, doi = {10.4230/LIPIcs.FSTTCS.2021.31}, annote = {Keywords: Hypergraph coloring, Propery B} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy. Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{dey_et_al:LIPIcs.MFCS.2020.28, author = {Dey, Palash and Radhakrishnan, Jaikumar and Velusamy, Santhoshini}, title = {{Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {28:1--28:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.28}, URN = {urn:nbn:de:0030-drops-126965}, doi = {10.4230/LIPIcs.MFCS.2020.28}, annote = {Keywords: Set membership, Bit-probe model, Fully-explicit data structures, Adaptive data structures, Error-correcting codes} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2020.34, author = {Guruswami, Venkatesan and Opr\v{s}al, Jakub and Sandeep, Sai}, title = {{Revisiting Alphabet Reduction in Dinur’s PCP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {34:1--34:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.34}, URN = {urn:nbn:de:0030-drops-126372}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.34}, annote = {Keywords: PCP theorem, CSP, discrete Fourier analysis, label cover, long code} }
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 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Kshitij Gajjar and Jaikumar Radhakrishnan. Distance-Preserving Subgraphs of Interval Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{gajjar_et_al:LIPIcs.ESA.2017.39, author = {Gajjar, Kshitij and Radhakrishnan, Jaikumar}, title = {{Distance-Preserving Subgraphs of Interval Graphs}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {39:1--39:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.39}, URN = {urn:nbn:de:0030-drops-78798}, doi = {10.4230/LIPIcs.ESA.2017.39}, annote = {Keywords: interval graphs, shortest path, distance-preserving subgraphs, bit-reversal permutation matrix} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Mohit Garg and Jaikumar Radhakrishnan. Set Membership with Non-Adaptive Bit Probes. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{garg_et_al:LIPIcs.STACS.2017.38, author = {Garg, Mohit and Radhakrishnan, Jaikumar}, title = {{Set Membership with Non-Adaptive Bit Probes}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {38:1--38:13}, 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.38}, URN = {urn:nbn:de:0030-drops-69952}, doi = {10.4230/LIPIcs.STACS.2017.38}, annote = {Keywords: Data Structures, Bit-probe model, Compression, Bloom filters, Expansion} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Jaikumar Radhakrishnan and Swagato Sanyal. The Zero-Error Randomized Query Complexity of the Pointer Function. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{radhakrishnan_et_al:LIPIcs.FSTTCS.2016.16, author = {Radhakrishnan, Jaikumar and Sanyal, Swagato}, title = {{The Zero-Error Randomized Query Complexity of the Pointer Function}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {16:1--16:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.16}, URN = {urn:nbn:de:0030-drops-68514}, doi = {10.4230/LIPIcs.FSTTCS.2016.16}, annote = {Keywords: Deterministic Decision Tree, Randomized Decision Tree, Query Complexity, Models of Computation.} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan. Partition Bound Is Quadratically Tight for Product Distributions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 135:1-135:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{harsha_et_al:LIPIcs.ICALP.2016.135, author = {Harsha, Prahladh and Jain, Rahul and Radhakrishnan, Jaikumar}, title = {{Partition Bound Is Quadratically Tight for Product Distributions}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {135:1--135:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.135}, URN = {urn:nbn:de:0030-drops-62708}, doi = {10.4230/LIPIcs.ICALP.2016.135}, annote = {Keywords: partition bound, product distribution, communication complexity, query complexity} }
Feedback for Dagstuhl Publishing