Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Nutan Limaye
@article{DBLP:journals/cacm/LimayeST24,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits},
journal = {Commun. {ACM}},
volume = {67},
number = {2},
pages = {101--108},
year = {2024},
url = {https://doi.org/10.1145/3611094},
doi = {10.1145/3611094},
timestamp = {Fri, 23 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cacm/LimayeST24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChauguleL24,
author = {Prasad Chaugule and
Nutan Limaye},
title = {On the closures of monotone algebraic classes and variants of the
determinant},
journal = {Electron. Colloquium Comput. Complex.},
pages = {TR24--021},
year = {2024},
url = {https://eccc.weizmann.ac.il/report/2024/021},
timestamp = {Tue, 05 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/ChauguleL24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/ChauguleKLMSS23,
author = {Prasad Chaugule and
Mrinal Kumar and
Nutan Limaye and
Chandra Kanta Mohapatra and
Adrian She and
Srikanth Srinivasan},
title = {Schur Polynomials Do Not Have Small Formulas If the Determinant does
not},
journal = {Comput. Complex.},
volume = {32},
number = {1},
pages = {3},
year = {2023},
url = {https://doi.org/10.1007/s00037-023-00236-x},
doi = {10.1007/S00037-023-00236-X},
timestamp = {Mon, 05 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/ChauguleKLMSS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/FournierLM0T23,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
editor = {Amnon Ta{-}Shma},
title = {Towards Optimal Depth-Reductions for Algebraic Formulas},
booktitle = {38th Computational Complexity Conference, {CCC} 2023, July 17-20,
2023, Warwick, {UK}},
series = {LIPIcs},
volume = {264},
pages = {28:1--28:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.CCC.2023.28},
doi = {10.4230/LIPICS.CCC.2023.28},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/FournierLM0T23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2302-06984,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {Towards Optimal Depth-Reductions for Algebraic Formulas},
journal = {CoRR},
volume = {abs/2302.06984},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2302.06984},
doi = {10.48550/ARXIV.2302.06984},
eprinttype = {arXiv},
eprint = {2302.06984},
timestamp = {Mon, 20 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2302-06984.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FournierL0T23,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {On the Power of Homogeneous Algebraic Formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-191}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/191},
eprinttype = {ECCC},
eprint = {TR23-191},
timestamp = {Wed, 10 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/FournierL0T23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FournierLM0T23,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {Towards Optimal Depth-Reductions for Algebraic Formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR23-009}},
year = {2023},
url = {https://eccc.weizmann.ac.il/report/2023/009},
eprinttype = {ECCC},
eprint = {TR23-009},
timestamp = {Mon, 06 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/eccc/FournierLM0T23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/BajpaiKKLS22,
author = {Swapnam Bajpai and
Vaibhav Krishan and
Deepanshu Kush and
Nutan Limaye and
Srikanth Srinivasan},
title = {A {\#}SAT Algorithm for Small Constant-Depth Circuits with {PTF} gates},
journal = {Algorithmica},
volume = {84},
number = {4},
pages = {1132--1162},
year = {2022},
url = {https://doi.org/10.1007/s00453-021-00915-7},
doi = {10.1007/S00453-021-00915-7},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/BajpaiKKLS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/sigact/LimayeST22,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits},
journal = {{SIGACT} News},
volume = {53},
number = {2},
pages = {40--62},
year = {2022},
url = {https://doi.org/10.1145/3544979.3544989},
doi = {10.1145/3544979.3544989},
timestamp = {Tue, 15 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/sigact/LimayeST22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/DattaLNTW22,
author = {Samir Datta and
Nutan Limaye and
Prajakta Nimbhorkar and
Thomas Thierauf and
Fabian Wagner},
title = {Planar Graph Isomorphism Is in Log-Space},
journal = {{ACM} Trans. Comput. Theory},
volume = {14},
number = {2},
pages = {8:1--8:33},
year = {2022},
url = {https://doi.org/10.1145/3543686},
doi = {10.1145/3543686},
timestamp = {Mon, 05 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/toct/DattaLNTW22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Limaye0T22,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
editor = {Shachar Lovett},
title = {On the Partial Derivative Method Applied to Lopsided Set-Multilinear
Polynomials},
booktitle = {37th Computational Complexity Conference, {CCC} 2022, July 20-23,
2022, Philadelphia, PA, {USA}},
series = {LIPIcs},
volume = {234},
pages = {32:1--32:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.CCC.2022.32},
doi = {10.4230/LIPICS.CCC.2022.32},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Limaye0T22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/CurticapeanL022,
author = {Radu Curticapean and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Anuj Dawar and
Venkatesan Guruswami},
title = {On the VNP-Hardness of Some Monomial Symmetric Polynomials},
booktitle = {42nd {IARCS} Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, {FSTTCS} 2022, December 18-20, 2022,
{IIT} Madras, Chennai, India},
series = {LIPIcs},
volume = {250},
pages = {16:1--16:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2022.16},
doi = {10.4230/LIPICS.FSTTCS.2022.16},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/CurticapeanL022.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/latin/ChauguleL22,
author = {Prasad Chaugule and
Nutan Limaye},
editor = {Armando Casta{\~{n}}eda and
Francisco Rodr{\'{\i}}guez{-}Henr{\'{\i}}quez},
title = {On the Closures of Monotone Algebraic Classes and Variants of the
Determinant},
booktitle = {{LATIN} 2022: Theoretical Informatics - 15th Latin American Symposium,
Guanajuato, Mexico, November 7-11, 2022, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13568},
pages = {610--625},
publisher = {Springer},
year = {2022},
url = {https://doi.org/10.1007/978-3-031-20624-5\_37},
doi = {10.1007/978-3-031-20624-5\_37},
timestamp = {Thu, 03 Nov 2022 11:43:27 +0100},
biburl = {https://dblp.org/rec/conf/latin/ChauguleL22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/TavenasL022,
author = {S{\'{e}}bastien Tavenas and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Stefano Leonardi and
Anupam Gupta},
title = {Set-multilinear and non-commutative formula lower bounds for iterated
matrix multiplication},
booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing,
Rome, Italy, June 20 - 24, 2022},
pages = {416--425},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3519935.3520044},
doi = {10.1145/3519935.3520044},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/TavenasL022.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/CurticapeanL022,
author = {Radu Curticapean and
Nutan Limaye and
Srikanth Srinivasan},
title = {On the VNP-hardness of Some Monomial Symmetric Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-139}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/139},
eprinttype = {ECCC},
eprint = {TR22-139},
timestamp = {Tue, 25 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/CurticapeanL022.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Limaye0T22,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {On the Partial Derivative Method Applied to Lopsided Set-Multilinear
Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR22-090}},
year = {2022},
url = {https://eccc.weizmann.ac.il/report/2022/090},
eprinttype = {ECCC},
eprint = {TR22-090},
timestamp = {Mon, 11 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Limaye0T22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/LimayeSSTV21,
author = {Nutan Limaye and
Karteek Sreenivasaiah and
Srikanth Srinivasan and
Utkarsh Tripathi and
S. Venkitesh},
title = {A Fixed-Depth Size-Hierarchy Theorem for {\textdollar}{\textbackslash}mathrm\{AC\}{\^{}}0[{\textbackslash}oplus]{\textdollar}
via the Coin Problem},
journal = {{SIAM} J. Comput.},
volume = {50},
number = {4},
pages = {1461--1499},
year = {2021},
url = {https://doi.org/10.1137/19M1276467},
doi = {10.1137/19M1276467},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/LimayeSSTV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/ChauguleLV21,
author = {Prasad Chaugule and
Nutan Limaye and
Aditya Varre},
title = {Variants of Homomorphism Polynomials Complete for Algebraic Complexity
Classes},
journal = {{ACM} Trans. Comput. Theory},
volume = {13},
number = {4},
pages = {21:1--21:26},
year = {2021},
url = {https://doi.org/10.1145/3470858},
doi = {10.1145/3470858},
timestamp = {Wed, 15 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/ChauguleLV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/ChauguleLP21,
author = {Prasad Chaugule and
Nutan Limaye and
Shourya Pandey},
editor = {Rahul Santhanam and
Daniil Musatov},
title = {Variants of the Determinant Polynomial and the VP-Completeness},
booktitle = {Computer Science - Theory and Applications - 16th International Computer
Science Symposium in Russia, {CSR} 2021, Sochi, Russia, June 28 -
July 2, 2021, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {12730},
pages = {31--55},
publisher = {Springer},
year = {2021},
url = {https://doi.org/10.1007/978-3-030-79416-3\_3},
doi = {10.1007/978-3-030-79416-3\_3},
timestamp = {Wed, 14 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/csr/ChauguleLP21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Limaye0T21,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {804--814},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00083},
doi = {10.1109/FOCS52979.2021.00083},
timestamp = {Tue, 21 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Limaye0T21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LimayeST21,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR21-081}},
year = {2021},
url = {https://eccc.weizmann.ac.il/report/2021/081},
eprinttype = {ECCC},
eprint = {TR21-081},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LimayeST21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LimayeST21a,
author = {Nutan Limaye and
Srikanth Srinivasan and
S{\'{e}}bastien Tavenas},
title = {New Non-FPT Lower Bounds for Some Arithmetic Formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR21-094}},
year = {2021},
url = {https://eccc.weizmann.ac.il/report/2021/094},
eprinttype = {ECCC},
eprint = {TR21-094},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LimayeST21a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/BalajiKL20,
author = {Nikhil Balaji and
Andreas Krebs and
Nutan Limaye},
title = {Skew circuits of small width},
journal = {Theor. Comput. Sci.},
volume = {821},
pages = {111--123},
year = {2020},
url = {https://doi.org/10.1016/j.tcs.2017.03.013},
doi = {10.1016/J.TCS.2017.03.013},
timestamp = {Mon, 15 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tcs/BalajiKL20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ChauguleKLMS020,
author = {Prasad Chaugule and
Mrinal Kumar and
Nutan Limaye and
Chandra Kanta Mohapatra and
Adrian She and
Srikanth Srinivasan},
editor = {Shubhangi Saraf},
title = {Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't},
booktitle = {35th Computational Complexity Conference, {CCC} 2020, July 28-31,
2020, Saarbr{\"{u}}cken, Germany (Virtual Conference)},
series = {LIPIcs},
volume = {169},
pages = {14:1--14:27},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.CCC.2020.14},
doi = {10.4230/LIPICS.CCC.2020.14},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/ChauguleKLMS020.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChauguleLP20,
author = {Prasad Chaugule and
Nutan Limaye and
Shourya Pandey},
title = {Variants of the Determinant polynomial and VP-completeness},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR20-152}},
year = {2020},
url = {https://eccc.weizmann.ac.il/report/2020/152},
eprinttype = {ECCC},
eprint = {TR20-152},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChauguleLP20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/LagardeLS19,
author = {Guillaume Lagarde and
Nutan Limaye and
Srikanth Srinivasan},
title = {Lower Bounds and {PIT} for Non-commutative Arithmetic Circuits with
Restricted Parse Trees},
journal = {Comput. Complex.},
volume = {28},
number = {3},
pages = {471--542},
year = {2019},
url = {https://doi.org/10.1007/s00037-018-0171-9},
doi = {10.1007/S00037-018-0171-9},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/LagardeLS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChillaraL019,
author = {Suryajith Chillara and
Nutan Limaye and
Srikanth Srinivasan},
title = {Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication
with Applications},
journal = {{SIAM} J. Comput.},
volume = {48},
number = {1},
pages = {70--92},
year = {2019},
url = {https://doi.org/10.1137/18M1191567},
doi = {10.1137/18M1191567},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChillaraL019.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/ChauguleLV19,
author = {Prasad Chaugule and
Nutan Limaye and
Aditya Varre},
editor = {Ding{-}Zhu Du and
Zhenhua Duan and
Cong Tian},
title = {Variants of Homomorphism Polynomials Complete for Algebraic Complexity
Classes},
booktitle = {Computing and Combinatorics - 25th International Conference, {COCOON}
2019, Xi'an, China, July 29-31, 2019, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {11653},
pages = {90--102},
publisher = {Springer},
year = {2019},
url = {https://doi.org/10.1007/978-3-030-26176-4\_8},
doi = {10.1007/978-3-030-26176-4\_8},
timestamp = {Wed, 24 Jul 2019 17:02:06 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/ChauguleLV19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/Limaye0T19,
author = {Nutan Limaye and
Srikanth Srinivasan and
Utkarsh Tripathi},
editor = {Arkadev Chattopadhyay and
Paul Gastin},
title = {More on AC{\^{}}0[oplus] and Variants of the Majority Function},
booktitle = {39th {IARCS} Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, {FSTTCS} 2019, December 11-13, 2019,
Bombay, India},
series = {LIPIcs},
volume = {150},
pages = {22:1--22:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2019.22},
doi = {10.4230/LIPICS.FSTTCS.2019.22},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/Limaye0T19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/BajpaiKKL019,
author = {Swapnam Bajpai and
Vaibhav Krishan and
Deepanshu Kush and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Avrim Blum},
title = {A {\#}SAT Algorithm for Small Constant-Depth Circuits with {PTF} Gates},
booktitle = {10th Innovations in Theoretical Computer Science Conference, {ITCS}
2019, January 10-12, 2019, San Diego, California, {USA}},
series = {LIPIcs},
volume = {124},
pages = {8:1--8:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2019.8},
doi = {10.4230/LIPICS.ITCS.2019.8},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/BajpaiKKL019.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/LimayeS0TV19,
author = {Nutan Limaye and
Karteek Sreenivasaiah and
Srikanth Srinivasan and
Utkarsh Tripathi and
S. Venkitesh},
editor = {Moses Charikar and
Edith Cohen},
title = {A fixed-depth size-hierarchy theorem for AC\({}^{\mbox{0}}\)[{\(\oplus\)}]
via the coin problem},
booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019},
pages = {442--453},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3313276.3316339},
doi = {10.1145/3313276.3316339},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/LimayeS0TV19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-12520,
author = {Prasad Chaugule and
Mrinal Kumar and
Nutan Limaye and
Chandra Kanta Mohapatra and
Adrian She and
Srikanth Srinivasan},
title = {Schur Polynomials do not have small formulas if the Determinant doesn't!},
journal = {CoRR},
volume = {abs/1911.12520},
year = {2019},
url = {http://arxiv.org/abs/1911.12520},
eprinttype = {arXiv},
eprint = {1911.12520},
timestamp = {Fri, 17 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-12520.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChauguleKLMSS19,
author = {Prasad Chaugule and
Mrinal Kumar and
Nutan Limaye and
Chandra Kanta Mohapatra and
Adrian She and
Srikanth Srinivasan},
title = {Schur Polynomials do not have small formulas if the Determinant doesn't!},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-172}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/172},
eprinttype = {ECCC},
eprint = {TR19-172},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChauguleKLMSS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LimayeST19,
author = {Nutan Limaye and
Srikanth Srinivasan and
Utkarsh Tripathi},
title = {More on {\textdollar}AC{\^{}}0[{\textbackslash}oplus]{\textdollar}
and Variants of the Majority Function},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-133}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/133},
eprinttype = {ECCC},
eprint = {TR19-133},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LimayeST19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChillaraEL018,
author = {Suryajith Chillara and
Christian Engels and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Mikkel Thorup},
title = {A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear
Circuits},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {934--945},
publisher = {{IEEE} Computer Society},
year = {2018},
url = {https://doi.org/10.1109/FOCS.2018.00092},
doi = {10.1109/FOCS.2018.00092},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChillaraEL018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ChillaraL018,
author = {Suryajith Chillara and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Ioannis Chatzigiannakis and
Christos Kaklamanis and
D{\'{a}}niel Marx and
Donald Sannella},
title = {A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas},
booktitle = {45th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2018, July 9-13, 2018, Prague, Czech Republic},
series = {LIPIcs},
volume = {107},
pages = {36:1--36:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2018.36},
doi = {10.4230/LIPICS.ICALP.2018.36},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ChillaraL018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/ChillaraL018,
author = {Suryajith Chillara and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Rolf Niedermeier and
Brigitte Vall{\'{e}}e},
title = {Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication,
with Applications},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science, {STACS}
2018, February 28 to March 3, 2018, Caen, France},
series = {LIPIcs},
volume = {96},
pages = {21:1--21:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2018},
url = {https://doi.org/10.4230/LIPIcs.STACS.2018.21},
doi = {10.4230/LIPICS.STACS.2018.21},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/ChillaraL018.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1804-02520,
author = {Suryajith Chillara and
Christian Engels and
Nutan Limaye and
Srikanth Srinivasan},
title = {A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear
Circuits},
journal = {CoRR},
volume = {abs/1804.02520},
year = {2018},
url = {http://arxiv.org/abs/1804.02520},
eprinttype = {arXiv},
eprint = {1804.02520},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1804-02520.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1809-04092,
author = {Nutan Limaye and
Karteek Sreenivasaiah and
Srikanth Srinivasan and
Utkarsh Tripathi and
S. Venkitesh},
title = {The Coin Problem in Constant Depth: Sample Complexity and Parity Gates},
journal = {CoRR},
volume = {abs/1809.04092},
year = {2018},
url = {http://arxiv.org/abs/1809.04092},
eprinttype = {arXiv},
eprint = {1809.04092},
timestamp = {Fri, 05 Oct 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1809-04092.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1809-05932,
author = {Swapnam Bajpai and
Vaibhav Krishan and
Deepanshu Kush and
Nutan Limaye and
Srikanth Srinivasan},
title = {A {\#}SAT Algorithm for Small Constant-Depth Circuits with {PTF} gates},
journal = {CoRR},
volume = {abs/1809.05932},
year = {2018},
url = {http://arxiv.org/abs/1809.05932},
eprinttype = {arXiv},
eprint = {1809.05932},
timestamp = {Fri, 05 Oct 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1809-05932.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BajpaiKKLS18,
author = {Swapnam Bajpai and
Vaibhav Krishan and
Deepanshu Kush and
Nutan Limaye and
Srikanth Srinivasan},
title = {A {\#}SAT Algorithm for Small Constant-Depth Circuits with {PTF} gates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-162}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/162},
eprinttype = {ECCC},
eprint = {TR18-162},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BajpaiKKLS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChauguleLV18,
author = {Prasad Chaugule and
Nutan Limaye and
Aditya Varre},
title = {Variants of Homomorphism Polynomials Complete for Algebraic Complexity
Classes},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-135}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/135},
eprinttype = {ECCC},
eprint = {TR18-135},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChauguleLV18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChillaraELS18,
author = {Suryajith Chillara and
Christian Engels and
Nutan Limaye and
Srikanth Srinivasan},
title = {A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear
Circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-062}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/062},
eprinttype = {ECCC},
eprint = {TR18-062},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChillaraELS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LimayeSSTV18,
author = {Nutan Limaye and
Karteek Sreenivasaiah and
Srikanth Srinivasan and
Utkarsh Tripathi and
S. Venkitesh},
title = {The Coin Problem in Constant Depth: Sample Complexity and Parity gates},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR18-157}},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/157},
eprinttype = {ECCC},
eprint = {TR18-157},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LimayeSSTV18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/KayalLSS17,
author = {Neeraj Kayal and
Nutan Limaye and
Chandan Saha and
Srikanth Srinivasan},
title = {An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {1},
pages = {307--335},
year = {2017},
url = {https://doi.org/10.1137/151002423},
doi = {10.1137/151002423},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/KayalLSS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/FournierLM017,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Meena Mahajan and
Srikanth Srinivasan},
title = {The Shifted Partial Derivative Complexity of Elementary Symmetric
Polynomials},
journal = {Theory Comput.},
volume = {13},
number = {1},
pages = {1--34},
year = {2017},
url = {https://doi.org/10.4086/toc.2017.v013a009},
doi = {10.4086/TOC.2017.V013A009},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/FournierLM017.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ton/VyavahareLDM17,
author = {Pooja Vyavahare and
Nutan Limaye and
Ajit A. Diwan and
D. Manjunath},
title = {On the Maximum Rate of Networked Computation in a Capacitated Network},
journal = {{IEEE/ACM} Trans. Netw.},
volume = {25},
number = {4},
pages = {2444--2458},
year = {2017},
url = {https://doi.org/10.1109/TNET.2017.2695578},
doi = {10.1109/TNET.2017.2695578},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ton/VyavahareLDM17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/KrebsLL17,
author = {Andreas Krebs and
Nutan Limaye and
Michael Ludwig},
editor = {Satya V. Lokam and
R. Ramanujam},
title = {A Unified Method for Placing Problems in Polylogarithmic Depth},
booktitle = {37th {IARCS} Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, {FSTTCS} 2017, December 11-15, 2017,
Kanpur, India},
series = {LIPIcs},
volume = {93},
pages = {36:36--36:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2017.36},
doi = {10.4230/LIPICS.FSTTCS.2017.36},
timestamp = {Fri, 03 Sep 2021 15:00:19 +0200},
biburl = {https://dblp.org/rec/conf/fsttcs/KrebsLL17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/LagardeL017,
author = {Guillaume Lagarde and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Kim G. Larsen and
Hans L. Bodlaender and
Jean{-}Fran{\c{c}}ois Raskin},
title = {Lower Bounds and {PIT} for Non-Commutative Arithmetic Circuits with
Restricted Parse Trees},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer
Science, {MFCS} 2017, August 21-25, 2017 - Aalborg, Denmark},
series = {LIPIcs},
volume = {83},
pages = {41:1--41:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.MFCS.2017.41},
doi = {10.4230/LIPICS.MFCS.2017.41},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/LagardeL017.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1710-05481,
author = {Suryajith Chillara and
Nutan Limaye and
Srikanth Srinivasan},
title = {Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication,
with Applications},
journal = {CoRR},
volume = {abs/1710.05481},
year = {2017},
url = {http://arxiv.org/abs/1710.05481},
eprinttype = {arXiv},
eprint = {1710.05481},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1710-05481.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChillaraLS17,
author = {Suryajith Chillara and
Nutan Limaye and
Srikanth Srinivasan},
title = {Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication,
with Applications},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-156}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/156},
eprinttype = {ECCC},
eprint = {TR17-156},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChillaraLS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KrebsLL17,
author = {Andreas Krebs and
Nutan Limaye and
Michael Ludwig},
title = {A Unified Method for Placing Problems in Polylogarithmic Depth},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-019}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/019},
eprinttype = {ECCC},
eprint = {TR17-019},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KrebsLL17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LagardeLS17,
author = {Guillaume Lagarde and
Nutan Limaye and
Srikanth Srinivasan},
title = {Lower Bounds and {PIT} for Non-Commutative Arithmetic circuits with
Restricted Parse Trees},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR17-077}},
year = {2017},
url = {https://eccc.weizmann.ac.il/report/2017/077},
eprinttype = {ECCC},
eprint = {TR17-077},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LagardeLS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/LimayeMS16,
author = {Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan},
title = {Lower Bounds for Non-Commutative Skew Circuits},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--38},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a012},
doi = {10.4086/TOC.2016.V012A012},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/LimayeMS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/GalJLMS16,
author = {Anna G{\'{a}}l and
Jing{-}Tang Jang and
Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah},
title = {Space-Efficient Approximations for Subset Sum},
journal = {{ACM} Trans. Comput. Theory},
volume = {8},
number = {4},
pages = {16:1--16:28},
year = {2016},
url = {https://doi.org/10.1145/2894843},
doi = {10.1145/2894843},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/GalJLMS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/KrebsLMS16,
author = {Andreas Krebs and
Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah},
title = {Small Depth Proof Systems},
journal = {{ACM} Trans. Comput. Theory},
volume = {9},
number = {1},
pages = {2:1--2:26},
year = {2016},
url = {https://doi.org/10.1145/2956229},
doi = {10.1145/2956229},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/KrebsLMS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ton/VyavahareLM16,
author = {Pooja Vyavahare and
Nutan Limaye and
D. Manjunath},
title = {Optimal Embedding of Functions for In-Network Computation: Complexity
Analysis and Algorithms},
journal = {{IEEE/ACM} Trans. Netw.},
volume = {24},
number = {4},
pages = {2019--2032},
year = {2016},
url = {https://doi.org/10.1109/TNET.2015.2445835},
doi = {10.1109/TNET.2015.2445835},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ton/VyavahareLM16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/KrebsLL16,
author = {Andreas Krebs and
Nutan Limaye and
Michael Ludwig},
editor = {Thang N. Dinh and
My T. Thai},
title = {Cost Register Automata for Nested Words},
booktitle = {Computing and Combinatorics - 22nd International Conference, {COCOON}
2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9797},
pages = {587--598},
publisher = {Springer},
year = {2016},
url = {https://doi.org/10.1007/978-3-319-42634-1\_47},
doi = {10.1007/978-3-319-42634-1\_47},
timestamp = {Tue, 14 May 2019 10:00:35 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/KrebsLL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BalajiLS16,
author = {Nikhil Balaji and
Nutan Limaye and
Srikanth Srinivasan},
title = {An Almost Cubic Lower Bound for {\(\Sigma\)}{\(\Pi\)}{\(\Sigma\)}
Circuits Computing a Polynomial in {VP}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-143}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/143},
eprinttype = {ECCC},
eprint = {TR16-143},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BalajiLS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KrishanL16,
author = {Vaibhav Krishan and
Nutan Limaye},
title = {Isolation Lemma for Directed Reachability and {NL} vs. {L}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-155}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/155},
eprinttype = {ECCC},
eprint = {TR16-155},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KrishanL16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/FournierLMS15,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan},
title = {Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication},
journal = {{SIAM} J. Comput.},
volume = {44},
number = {5},
pages = {1173--1201},
year = {2015},
url = {https://doi.org/10.1137/140990280},
doi = {10.1137/140990280},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/FournierLMS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/BalajiKL15,
author = {Nikhil Balaji and
Andreas Krebs and
Nutan Limaye},
editor = {Dachuan Xu and
Donglei Du and
Ding{-}Zhu Du},
title = {Skew Circuits of Small Width},
booktitle = {Computing and Combinatorics - 21st International Conference, {COCOON}
2015, Beijing, China, August 4-6, 2015, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {9198},
pages = {199--210},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-319-21398-9\_16},
doi = {10.1007/978-3-319-21398-9\_16},
timestamp = {Sun, 25 Oct 2020 22:58:52 +0100},
biburl = {https://dblp.org/rec/conf/cocoon/BalajiKL15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/FournierLMS15,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Meena Mahajan and
Srikanth Srinivasan},
editor = {Giuseppe F. Italiano and
Giovanni Pighizzini and
Donald Sannella},
title = {The Shifted Partial Derivative Complexity of Elementary Symmetric
Polynomials},
booktitle = {Mathematical Foundations of Computer Science 2015 - 40th International
Symposium, {MFCS} 2015, Milan, Italy, August 24-28, 2015, Proceedings,
Part {II}},
series = {Lecture Notes in Computer Science},
volume = {9235},
pages = {324--335},
publisher = {Springer},
year = {2015},
url = {https://doi.org/10.1007/978-3-662-48054-0\_27},
doi = {10.1007/978-3-662-48054-0\_27},
timestamp = {Thu, 23 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/FournierLMS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/VyavahareLM15,
author = {Pooja Vyavahare and
Nutan Limaye and
D. Manjunath},
title = {On the Maximum Rate of Networked Computation in a Capacitated Network},
journal = {CoRR},
volume = {abs/1507.04234},
year = {2015},
url = {http://arxiv.org/abs/1507.04234},
eprinttype = {arXiv},
eprint = {1507.04234},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/VyavahareLM15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/CadilhacKL15,
author = {Micha{\"{e}}l Cadilhac and
Andreas Krebs and
Nutan Limaye},
title = {Value Automata with Filters},
journal = {CoRR},
volume = {abs/1510.02393},
year = {2015},
url = {http://arxiv.org/abs/1510.02393},
eprinttype = {arXiv},
eprint = {1510.02393},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/CadilhacKL15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FournierLMS15,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Meena Mahajan and
Srikanth Srinivasan},
title = {The shifted partial derivative complexity of Elementary Symmetric
Polynomials},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-118}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/118},
eprinttype = {ECCC},
eprint = {TR15-118},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FournierLMS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LimayeMS15,
author = {Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan},
title = {Lower bounds for non-commutative skew circuits},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-022}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/022},
eprinttype = {ECCC},
eprint = {TR15-022},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LimayeMS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/allerton/VyavahareMGLM14,
author = {Pooja Vyavahare and
Majid Mahzoon and
Pulkit Grover and
Nutan Limaye and
D. Manjunath},
title = {Information friction limits on computation},
booktitle = {52nd Annual Allerton Conference on Communication, Control, and Computing,
Allerton 2014, Allerton Park {\&} Retreat Center, Monticello,
IL, USA, September 30 - October 3, 2014},
pages = {93--100},
publisher = {{IEEE}},
year = {2014},
url = {https://doi.org/10.1109/ALLERTON.2014.7028441},
doi = {10.1109/ALLERTON.2014.7028441},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/allerton/VyavahareMGLM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KayalLSS14,
author = {Neeraj Kayal and
Nutan Limaye and
Chandan Saha and
Srikanth Srinivasan},
title = {An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {61--70},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.15},
doi = {10.1109/FOCS.2014.15},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/KayalLSS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/KayalLSS14,
author = {Neeraj Kayal and
Nutan Limaye and
Chandan Saha and
Srikanth Srinivasan},
editor = {David B. Shmoys},
title = {Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas},
booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
May 31 - June 03, 2014},
pages = {119--127},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2591796.2591823},
doi = {10.1145/2591796.2591823},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/KayalLSS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/FournierLMS14,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan},
editor = {David B. Shmoys},
title = {Lower bounds for depth 4 formulas computing iterated matrix multiplication},
booktitle = {Symposium on Theory of Computing, {STOC} 2014, New York, NY, USA,
May 31 - June 03, 2014},
pages = {128--135},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2591796.2591824},
doi = {10.1145/2591796.2591824},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/FournierLMS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/VyavahareLM14,
author = {Pooja Vyavahare and
Nutan Limaye and
D. Manjunath},
title = {Efficient Embedding of Functions in Weighted Communication Networks},
journal = {CoRR},
volume = {abs/1401.2518},
year = {2014},
url = {http://arxiv.org/abs/1401.2518},
eprinttype = {arXiv},
eprint = {1401.2518},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/VyavahareLM14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BalajiKL14,
author = {Nikhil Balaji and
Andreas Krebs and
Nutan Limaye},
title = {Skew Circuits of Small Width},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-183}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/183},
eprinttype = {ECCC},
eprint = {TR14-183},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BalajiKL14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/GalJLMS14,
author = {Anna G{\'{a}}l and
Jing{-}Tang Jang and
Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah},
title = {Space-Efficient Approximations for Subset Sum},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-180}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/180},
eprinttype = {ECCC},
eprint = {TR14-180},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/GalJLMS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KayalLSS14,
author = {Neeraj Kayal and
Nutan Limaye and
Chandan Saha and
Srikanth Srinivasan},
title = {An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-005}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/005},
eprinttype = {ECCC},
eprint = {TR14-005},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KayalLSS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tcs/BabuLRV13,
author = {Ajesh Babu and
Nutan Limaye and
Jaikumar Radhakrishnan and
Girish Varma},
title = {Streaming algorithms for language recognition problems},
journal = {Theor. Comput. Sci.},
volume = {494},
pages = {13--23},
year = {2013},
url = {https://doi.org/10.1016/j.tcs.2012.12.028},
doi = {10.1016/J.TCS.2012.12.028},
timestamp = {Wed, 17 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/tcs/BabuLRV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/KrebsL13,
author = {Andreas Krebs and
Nutan Limaye},
editor = {Anil Seth and
Nisheeth K. Vishnoi},
title = {{DLOGTIME} Proof Systems},
booktitle = {{IARCS} Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, {FSTTCS} 2013, December 12-14, 2013,
Guwahati, India},
series = {LIPIcs},
volume = {24},
pages = {189--200},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2013},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2013.189},
doi = {10.4230/LIPICS.FSTTCS.2013.189},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/KrebsL13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/KrebsLMS13,
author = {Andreas Krebs and
Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah},
editor = {Krishnendu Chatterjee and
Jir{\'{\i}} Sgall},
title = {Small Depth Proof Systems},
booktitle = {Mathematical Foundations of Computer Science 2013 - 38th International
Symposium, {MFCS} 2013, Klosterneuburg, Austria, August 26-30, 2013.
Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8087},
pages = {583--594},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-40313-2\_52},
doi = {10.1007/978-3-642-40313-2\_52},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/KrebsLMS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/KrebsLMS13,
author = {Andreas Krebs and
Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah},
title = {Small Depth Proof Systems},
journal = {CoRR},
volume = {abs/1307.4897},
year = {2013},
url = {http://arxiv.org/abs/1307.4897},
eprinttype = {arXiv},
eprint = {1307.4897},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/KrebsLMS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/FournierLMS13,
author = {Herv{\'{e}} Fournier and
Nutan Limaye and
Guillaume Malod and
Srikanth Srinivasan},
title = {Lower bounds for depth 4 formulas computing iterated matrix multiplication},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-100}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/100},
eprinttype = {ECCC},
eprint = {TR13-100},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/FournierLMS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KrebsLMS13,
author = {Andreas Krebs and
Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah},
title = {Small Depth Proof Systems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-102}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/102},
eprinttype = {ECCC},
eprint = {TR13-102},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KrebsLMS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/KrebsLM12,
author = {Andreas Krebs and
Nutan Limaye and
Meena Mahajan},
title = {Counting Paths in {VPA} Is Complete for {\#}NC 1},
journal = {Algorithmica},
volume = {64},
number = {2},
pages = {279--294},
year = {2012},
url = {https://doi.org/10.1007/s00453-011-9501-x},
doi = {10.1007/S00453-011-9501-X},
timestamp = {Thu, 23 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/KrebsLM12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/LimayeMS12,
author = {Nutan Limaye and
Meena Mahajan and
Karteek Sreenivasaiah},
editor = {Joachim Gudmundsson and
Juli{\'{a}}n Mestre and
Taso Viglas},
title = {The Complexity of Unary Subset Sum},
booktitle = {Computing and Combinatorics - 18th Annual International Conference,
{COCOON} 2012, Sydney, Australia, August 20-22, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7434},
pages = {458--469},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32241-9\_39},
doi = {10.1007/978-3-642-32241-9\_39},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/LimayeMS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1206-0206,
author = {Andreas Krebs and
Nutan Limaye and
Srikanth Srinivasan},
title = {Streaming algorithms for recognizing nearly well-parenthesized expressions},
journal = {CoRR},
volume = {abs/1206.0206},
year = {2012},
url = {http://arxiv.org/abs/1206.0206},
eprinttype = {arXiv},
eprint = {1206.0206},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1206-0206.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1210-6134,
author = {Pooja Vyavahare and
Nutan Limaye and
D. Manjunath},
title = {In-Network Estimation of Frequency Moments},
journal = {CoRR},
volume = {abs/1210.6134},
year = {2012},
url = {http://arxiv.org/abs/1210.6134},
eprinttype = {arXiv},
eprint = {1210.6134},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1210-6134.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KrebsL12,
author = {Andreas Krebs and
Nutan Limaye},
title = {DLOGTIME-Proof Systems},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-186}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/186},
eprinttype = {ECCC},
eprint = {TR12-186},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KrebsL12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/KrebsLS11,
author = {Andreas Krebs and
Nutan Limaye and
Srikanth Srinivasan},
editor = {Filip Murlak and
Piotr Sankowski},
title = {Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions},
booktitle = {Mathematical Foundations of Computer Science 2011 - 36th International
Symposium, {MFCS} 2011, Warsaw, Poland, August 22-26, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6907},
pages = {412--423},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22993-0\_38},
doi = {10.1007/978-3-642-22993-0\_38},
timestamp = {Tue, 14 May 2019 10:00:37 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/KrebsLS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1104-0848,
author = {Ajesh Babu and
Nutan Limaye and
Jaikumar Radhakrishnan and
Girish Varma},
title = {Streaming algorithms for language recognition problems},
journal = {CoRR},
volume = {abs/1104.0848},
year = {2011},
url = {http://arxiv.org/abs/1104.0848},
eprinttype = {arXiv},
eprint = {1104.0848},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1104-0848.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cjtcs/LimayeMN10,
author = {Nutan Limaye and
Meena Mahajan and
Prajakta Nimbhorkar},
title = {Longest Paths in Planar DAGs in Unambiguous Log-Space},
journal = {Chic. J. Theor. Comput. Sci.},
volume = {2010},
year = {2010},
url = {http://cjtcs.cs.uchicago.edu/articles/CATS2009/5/contents.html},
timestamp = {Thu, 11 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cjtcs/LimayeMN10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mst/LimayeMR10,
author = {Nutan Limaye and
Meena Mahajan and
B. V. Raghavendra Rao},
title = {Arithmetizing Classes Around NC{\textbackslash}textsf\{NC\}\({}^{\mbox{1}}\)
and L{\textbackslash}textsf\{L\}},
journal = {Theory Comput. Syst.},
volume = {46},
number = {3},
pages = {499--522},
year = {2010},
url = {https://doi.org/10.1007/s00224-009-9233-3},
doi = {10.1007/S00224-009-9233-3},
timestamp = {Thu, 23 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mst/LimayeMR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/DattaKLM10,
author = {Samir Datta and
Raghav Kulkarni and
Nutan Limaye and
Meena Mahajan},
title = {Planarity, Determinants, Permanents, and (Unique) Matchings},
journal = {{ACM} Trans. Comput. Theory},
volume = {1},
number = {3},
pages = {10:1--10:20},
year = {2010},
url = {https://doi.org/10.1145/1714450.1714453},
doi = {10.1145/1714450.1714453},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/DattaKLM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cocoon/KrebsLM10,
author = {Andreas Krebs and
Nutan Limaye and
Meena Mahajan},
editor = {My T. Thai and
Sartaj Sahni},
title = {Counting Paths in {VPA} Is Complete for {\#}NC\({}^{\mbox{1}}\)},
booktitle = {Computing and Combinatorics, 16th Annual International Conference,
{COCOON} 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6196},
pages = {44--53},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-14031-0\_7},
doi = {10.1007/978-3-642-14031-0\_7},
timestamp = {Thu, 23 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/cocoon/KrebsLM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tamc/BabuLV10,
author = {Ajesh Babu and
Nutan Limaye and
Girish Varma},
editor = {Jan Kratochv{\'{\i}}l and
Angsheng Li and
Jir{\'{\i}} Fiala and
Petr Kolman},
title = {Streaming Algorithms for Some Problems in Log-Space},
booktitle = {Theory and Applications of Models of Computation, 7th Annual Conference,
{TAMC} 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6108},
pages = {94--104},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-13562-0\_10},
doi = {10.1007/978-3-642-13562-0\_10},
timestamp = {Tue, 14 May 2019 10:00:46 +0200},
biburl = {https://dblp.org/rec/conf/tamc/BabuLV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BabuLV10,
author = {Ajesh Babu and
Nutan Limaye and
Girish Varma},
title = {Streaming algorithms for some problems in log-space},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-094}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/094},
eprinttype = {ECCC},
eprint = {TR10-094},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BabuLV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/KrebsLM10,
author = {Andreas Krebs and
Nutan Limaye and
Meena Mahajan},
title = {Counting paths in {VPA} is complete for {\#}NC\({}^{\mbox{1}}\)},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-103}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/103},
eprinttype = {ECCC},
eprint = {TR10-103},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/KrebsLM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/LimayeMS09,
author = {Nutan Limaye and
Meena Mahajan and
Jayalal Sarma},
title = {Upper Bounds for Monotone Planar Circuit Value and Variants},
journal = {Comput. Complex.},
volume = {18},
number = {3},
pages = {377--412},
year = {2009},
url = {https://doi.org/10.1007/s00037-009-0265-5},
doi = {10.1007/S00037-009-0265-5},
timestamp = {Sun, 15 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/cc/LimayeMS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jalc/LimayeMM09,
author = {Nutan Limaye and
Meena Mahajan and
Antoine Meyer},
title = {On the Complexity of Membership and Counting in Height-Deterministic
Pushdown Automata},
journal = {J. Autom. Lang. Comb.},
volume = {14},
number = {3/4},
pages = {211--235},
year = {2009},
url = {https://doi.org/10.25596/jalc-2009-211},
doi = {10.25596/JALC-2009-211},
timestamp = {Mon, 11 May 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jalc/LimayeMM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cats/LimayeMN09,
author = {Nutan Limaye and
Meena Mahajan and
Prajakta Nimbhorkar},
editor = {Rod Downey and
Prabhu Manyem},
title = {Longest Paths in Planar DAGs in Unambiguous Logspace},
booktitle = {Theory of Computing 2009, Fifteenth Computing: The Australasian Theory
Symposium, {CATS} 2009, Wellington, New Zealand, January 2009},
series = {{CRPIT}},
volume = {94},
pages = {99--105},
publisher = {Australian Computer Society},
year = {2009},
url = {http://crpit.scem.westernsydney.edu.au/abstracts/CRPITV94Limaye.html},
timestamp = {Mon, 08 Feb 2021 13:26:47 +0100},
biburl = {https://dblp.org/rec/conf/cats/LimayeMN09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/DattaLNTW09,
author = {Samir Datta and
Nutan Limaye and
Prajakta Nimbhorkar and
Thomas Thierauf and
Fabian Wagner},
title = {Planar Graph Isomorphism is in Log-Space},
booktitle = {Proceedings of the 24th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2009, Paris, France, 15-18 July 2009},
pages = {203--214},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/CCC.2009.16},
doi = {10.1109/CCC.2009.16},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/DattaLNTW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/lata/LimayeM09,
author = {Nutan Limaye and
Meena Mahajan},
editor = {Adrian{-}Horia Dediu and
Armand{-}Mihai Ionescu and
Carlos Mart{\'{\i}}n{-}Vide},
title = {Membership Testing: Removing Extra Stacks from Multi-stack Pushdown
Automata},
booktitle = {Language and Automata Theory and Applications, Third International
Conference, {LATA} 2009, Tarragona, Spain, April 2-8, 2009. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5457},
pages = {493--504},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-00982-2\_42},
doi = {10.1007/978-3-642-00982-2\_42},
timestamp = {Tue, 14 May 2019 10:00:41 +0200},
biburl = {https://dblp.org/rec/conf/lata/LimayeM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/DattaLNTW09,
author = {Samir Datta and
Nutan Limaye and
Prajakta Nimbhorkar and
Thomas Thierauf and
Fabian Wagner},
editor = {Manindra Agrawal and
Lance Fortnow and
Thomas Thierauf and
Christopher Umans},
title = {Planar Graph Isomorphism is in Log-Space},
booktitle = {Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009},
series = {Dagstuhl Seminar Proceedings},
volume = {09421},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2009},
url = {http://drops.dagstuhl.de/opus/volltexte/2010/2416/},
timestamp = {Thu, 10 Jun 2021 13:02:05 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/DattaLNTW09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/WagnerDLNT09,
author = {Fabian Wagner and
Samir Datta and
Nutan Limaye and
Prajakta Nimbhorkar and
Thomas Thierauf},
title = {Planar Graph Isomorphism is in Log-space},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-052}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/052},
eprinttype = {ECCC},
eprint = {TR09-052},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/WagnerDLNT09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/LimayeMM08,
author = {Nutan Limaye and
Meena Mahajan and
Antoine Meyer},
editor = {Edward A. Hirsch and
Alexander A. Razborov and
Alexei L. Semenov and
Anatol Slissenko},
title = {On the Complexity of Membership and Counting in Height-Deterministic
Pushdown Automata},
booktitle = {Computer Science - Theory and Applications, Third International Computer
Science Symposium in Russia, {CSR} 2008, Moscow, Russia, June 7-12,
2008, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {5010},
pages = {240--251},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-79709-8\_25},
doi = {10.1007/978-3-540-79709-8\_25},
timestamp = {Tue, 21 Mar 2023 21:00:47 +0100},
biburl = {https://dblp.org/rec/conf/csr/LimayeMM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/DattaLN08,
author = {Samir Datta and
Nutan Limaye and
Prajakta Nimbhorkar},
editor = {Ramesh Hariharan and
Madhavan Mukund and
V. Vinay},
title = {3-connected Planar Graph Isomorphism is in Log-space},
booktitle = {{IARCS} Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, {FSTTCS} 2008, December 9-11, 2008,
Bangalore, India},
series = {LIPIcs},
volume = {2},
pages = {155--162},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2008},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1749},
doi = {10.4230/LIPICS.FSTTCS.2008.1749},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/DattaLN08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0802-1699,
author = {Nutan Limaye and
Meena Mahajan and
Prajakta Nimbhorkar},
title = {Longest paths in Planar DAGs in Unambiguous Logspace},
journal = {CoRR},
volume = {abs/0802.1699},
year = {2008},
url = {http://arxiv.org/abs/0802.1699},
eprinttype = {arXiv},
eprint = {0802.1699},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0802-1699.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0806-1041,
author = {Samir Datta and
Nutan Limaye and
Prajakta Nimbhorkar},
title = {3-connected Planar Graph Isomorphism is in Log-space},
journal = {CoRR},
volume = {abs/0806.1041},
year = {2008},
url = {http://arxiv.org/abs/0806.1041},
eprinttype = {arXiv},
eprint = {0806.1041},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0806-1041.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0809-2319,
author = {Samir Datta and
Nutan Limaye and
Prajakta Nimbhorkar and
Thomas Thierauf and
Fabian Wagner},
title = {A Log-space Algorithm for Canonization of Planar Graphs},
journal = {CoRR},
volume = {abs/0809.2319},
year = {2008},
url = {http://arxiv.org/abs/0809.2319},
eprinttype = {arXiv},
eprint = {0809.2319},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0809-2319.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/csr/DattaKLM07,
author = {Samir Datta and
Raghav Kulkarni and
Nutan Limaye and
Meena Mahajan},
editor = {Volker Diekert and
Mikhail V. Volkov and
Andrei Voronkov},
title = {Planarity, Determinants, Permanents, and (Unique) Matchings},
booktitle = {Computer Science - Theory and Applications, Second International Symposium
on Computer Science in Russia, {CSR} 2007, Ekaterinburg, Russia, September
3-7, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4649},
pages = {115--126},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74510-5\_14},
doi = {10.1007/978-3-540-74510-5\_14},
timestamp = {Thu, 09 Nov 2023 20:20:35 +0100},
biburl = {https://dblp.org/rec/conf/csr/DattaKLM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/LimayeMR07,
author = {Nutan Limaye and
Meena Mahajan and
B. V. Raghavendra Rao},
editor = {Wolfgang Thomas and
Pascal Weil},
title = {Arithmetizing Classes Around {NC} \({}^{\mbox{1}}\) and {L}},
booktitle = {{STACS} 2007, 24th Annual Symposium on Theoretical Aspects of Computer
Science, Aachen, Germany, February 22-24, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4393},
pages = {477--488},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-70918-3\_41},
doi = {10.1007/978-3-540-70918-3\_41},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/LimayeMR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/LimayeMR07,
author = {Nutan Limaye and
Meena Mahajan and
B. V. Raghavendra Rao},
title = {Arithmetizing classes around NC{\^{}}1 and {L}},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-087}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-087/index.html},
eprinttype = {ECCC},
eprint = {TR07-087},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/LimayeMR07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/LimayeMS06,
author = {Nutan Limaye and
Meena Mahajan and
Jayalal Sarma},
editor = {Bruno Durand and
Wolfgang Thomas},
title = {Evaluating Monotone Circuits on Cylinders, Planes and Tori},
booktitle = {{STACS} 2006, 23rd Annual Symposium on Theoretical Aspects of Computer
Science, Marseille, France, February 23-25, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3884},
pages = {660--671},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11672142\_54},
doi = {10.1007/11672142\_54},
timestamp = {Wed, 19 May 2021 12:05:43 +0200},
biburl = {https://dblp.org/rec/conf/stacs/LimayeMS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR06-009,
author = {Nutan Limaye and
Meena Mahajan and
Jayalal Sarma},
title = {Evaluating Monotone Circuits on Cylinders, Planes and Tori},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR06-009}},
year = {2006},
url = {https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-009/index.html},
eprinttype = {ECCC},
eprint = {TR06-009},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR06-009.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-25 01:21 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
