Publications.ComPlexity

 
Verifying Proofs in Constant Depth (with Olaf Beyersdorff, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, and Heribert Vollmer), To appear in MFCS 2011. Perfect Matching in Bipartite Planar Graphs is in UL (with Raghav Kulkarni and Raghunath Tewari) Manuscript, ECCC version. Planarity Testing Revisited (with Gautam Prakriya), In TAMC 2011. Some Tractable Win-Lose Games (with Nagarajan Krishnamurthy), In TAMC 2011. Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs (with Raghav Kulkarni, Raghunath Tewari and N. Variyam Vinodchandran), In STACS 2011. Counting Classes and the fine structure between NC1 and L (with Meena Mahajan, B. V. R. Rao, Michael Thomas and Heribert Vollmer), In MFCS 2010. Log-space Algorithms for Paths and Matchings in k-trees (with Bireswar Das and Prajakta Nimbhorkar). In STACS 2010. Graph Isomorphism for K3,3-free and K5-free Graphs is in Log-Space (with Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner) In Proc. 29th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2009. Planar Graph Isomorphism is in Logspace (with Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner) preprint on arxiv.org In Proc. 24th Annual IEEE Conference on Computational Complexity, 2009. 3-connected Planar Graph Isomorphism is in Logspace, (with Nutan Limaye and Prajakta Nimbhorkar) preprint on arxiv.org. In Proc. 28th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2008. Planar and Grid Graph Reachability Problems, (with Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, and Sambuddha Roy), to appear in Theory of Computing Systems. Subsumes this and this. Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs (with Raghav Kulkarni, and Sambuddha Roy), Theory Comput. Syst. 47(3): 737-757 (2010), A preliminary version appeared in Proc. 25th International Symposium on Theoretical Aspects of Computer Science, Feb 21-23, 2008, Bordeaux, France. Planarity, Determinants, Permanents, and (Unique) Perfect Matchings.. (with Raghav Kulkarni, Nutan Limaye, and Meena Mahajan), Proc. 2nd International Computer Science Symposium in Russia CSR, 2007, Ekaterinburg, Lecture Notes in Computer Science, 4649, pp. 115-126. One-input-face MPCVP is Hard for L, but in LogDCFL (with Tanmoy Chakraborty), Proc. 26th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2006, Lecture Notes in Computer Science, 4337, pp. 57-68. Grid Graph Reachability Problems, (with Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, and Sambuddha Roy), Proc. 21st Annual IEEE Conference on Computational Complexity, 2006, pp. 299--313. The Directed Planar Reachability Problem, (with Eric Allender and Sambuddha Roy), Proc. 25th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), 2005, Lecture Notes in Computer Science 3821, pp. 238-249. Topology inside NC1, (with Eric Allender and Sambuddha Roy), in Proc. 20th Annual IEEE Conference on Computational Complexity, 2005. On TC0, AC0, and Arithmetic Circuits, (with Manindra Agrawal and Eric Allender Journal of Computer and System Sciences 60 (2000) 395-421. An earlier version appeared in the twelfth Annual IEEE Conference on Computational Complexity, 1997. Characterizing Small Depth and Small Space Classes by Operators of Higher Types, (with Manindra Agrawal, Eric Allender, Heribert Vollmer, and Klaus W. Wagner), Chicago Journal of Theoretical Computer Science, 2000, article 2. Bounded Depth Arithmetic Circuits: Counting and Closure, (with Eric Allender, Andris Ambainis, David A. Mix Barrington, and Huong LeThanh), Proc. 26th International Colloquium on Automata, Languages, and Programming (ICALP), 1999, Lecture Notes in Computer Science 1644, pp. 149-158.http://www.imsc.res.in/%7Emeena/papers/proofs.pdfhttp://www.thi.uni-hannover.de/institut/mitarbeiter/olaf-beyersdorff/http://www.imsc.res.in/~meenahttp://www.math-inf.uni-greifswald.de/mathe/index.php/arbeitsgruppen/logik-und-grundlagen-der-mathematik/147-dr-gido-scharfenberger-fabianhttp://www.math-inf.uni-greifswald.de/mathe/index.php/arbeitsgruppen/logik-und-grundlagen-der-mathematik/147-dr-gido-scharfenberger-fabianhttp://www.imsc.res.in/%7Ekarteekhttp://www.thi.uni-hannover.de/en/homepage/people/michael-thomas/http://www.thi.uni-hannover.de/en/homepage/people/heribert-vollmer/http://eccc.hpi-web.de/report/2010/201http://eccc.hpi-web.de/report/2010/201http://eccc.hpi-web.de/report/2010/201http://eccc.hpi-web.de/report/2011/009http://arxiv.org/abs/1010.5951http://arxiv.org/abs/1004.5080http://eccc.hpi-web.de/report/2010/101http://arxiv.org/abs/0912.4602http://www.imsc.res.in/~bireswarhttp://www.imsc.res.in/~prajaktahttp://www.imsc.res.in/~prajaktahttp://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2314http://www.imsc.res.in/~prajaktahttp://www.imsc.res.in/~prajaktahttp://theorie.informatik.uni-ulm.de/thierauf/http://arxiv.org/abs/0809.2319http://www.imsc.res.in/~nutanhttp://www.imsc.res.in/~prajaktahttp://theorie.informatik.uni-ulm.de/thierauf/http://arxiv.org/abs/0809.2319http://arxiv.orghttp://arxiv.org/abs/0806.1041v1http://www.imsc.res.in/~nutanhttp://www.imsc.res.in/~prajaktahttp://www.imsc.res.in/~prajaktahttp://arxiv.org/abs/0806.1041http://arxiv.orgpublications.complexity_files/plan.ggr.pdfhttp://www.cs.rutgers.edu/~allenderhttp://www.cs.umass.edu/~barring/http://www.seas.upenn.edu/~tanmoy/http://www.cmi.ac.in/~sdatta/Samir%20Datta/publications.complexity_files/planar.reach.pdfhttp://www.cmi.ac.in/~sdatta/Samir%20Datta/publications.complexity_files/ggr.pdfhttp://drops.dagstuhl.de/opus/volltexte/2008/1346/http://dblp.uni-trier.de/db/journals/mst/mst47.html#DattaKR10http://drops.dagstuhl.de/opus/volltexte/2008/1346publications.complexity_files/planarRestr.pdfhttp://www.informatik.uni-trier.de/~ley/db/indices/a-tree/k/Kulkarni:Raghav.htmlhttp://www.imsc.res.in/~nutanhttp://www.imsc.res.in/~meenapublications.complexity_files/mpcvp.pdfhttp://www.seas.upenn.edu/~tanmoy/publications.complexity_files/ggr.pdfhttp://www.cs.rutgers.edu/~allenderhttp://www.cs.umass.edu/~barring/http://www.seas.upenn.edu/~tanmoy/http://www.seas.upenn.edu/~tanmoy/http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/r/Roy:Sambuddha.htmlpublications.complexity_files/planar.reach.pdfhttp://www.cs.rutgers.edu/~allenderhttp://www.informatik.uni-trier.de/~ley/db/indices/a-tree/r/Roy:Sambuddha.htmlpublications.complexity_files/topology.pdfhttp://www.cs.rutgers.edu/~allenderhttp://www.informatik.uni-trier.de/~ley/db/indices/a-tree/r/Roy:Sambuddha.htmlpublications.complexity_files/arithmetic.pdfhttp://www.cse.iitk.ac.in/users/manindra/http://www.cs.rutgers.edu/~allenderhttp://livepage.apple.com/publications.complexity_files/AADVW.pdfhttp://www.cse.iitk.ac.in/users/manindra/http://www.cs.rutgers.edu/~allenderhttp://www.thi.uni-hannover.de/mitarbeiter/vollmer/http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Wagner:Klaus_W=.htmlpublications.complexity_files/icalp99.pdfhttp://www.cs.rutgers.edu/~allenderhttp://www.math.uwaterloo.ca/~ambainis/http://www.math.uwaterloo.ca/~ambainis/http://www.cs.umass.edu/~barring/file://localhost/unnamedshapeimage_1_link_0shapeimage_1_link_1shapeimage_1_link_2shapeimage_1_link_3shapeimage_1_link_4shapeimage_1_link_5shapeimage_1_link_6shapeimage_1_link_7shapeimage_1_link_8shapeimage_1_link_9shapeimage_1_link_10shapeimage_1_link_11shapeimage_1_link_12shapeimage_1_link_13shapeimage_1_link_14shapeimage_1_link_15shapeimage_1_link_16shapeimage_1_link_17shapeimage_1_link_18shapeimage_1_link_19shapeimage_1_link_20shapeimage_1_link_21shapeimage_1_link_22shapeimage_1_link_23shapeimage_1_link_24shapeimage_1_link_25shapeimage_1_link_26shapeimage_1_link_27shapeimage_1_link_28shapeimage_1_link_29shapeimage_1_link_30shapeimage_1_link_31shapeimage_1_link_32shapeimage_1_link_33shapeimage_1_link_34shapeimage_1_link_35shapeimage_1_link_36shapeimage_1_link_37shapeimage_1_link_38shapeimage_1_link_39shapeimage_1_link_40shapeimage_1_link_41shapeimage_1_link_42shapeimage_1_link_43shapeimage_1_link_44shapeimage_1_link_45shapeimage_1_link_46shapeimage_1_link_47shapeimage_1_link_48shapeimage_1_link_49shapeimage_1_link_50shapeimage_1_link_51shapeimage_1_link_52shapeimage_1_link_53shapeimage_1_link_54shapeimage_1_link_55shapeimage_1_link_56shapeimage_1_link_57shapeimage_1_link_58shapeimage_1_link_59shapeimage_1_link_60shapeimage_1_link_61shapeimage_1_link_62shapeimage_1_link_63shapeimage_1_link_64shapeimage_1_link_65shapeimage_1_link_66shapeimage_1_link_67shapeimage_1_link_68shapeimage_1_link_69shapeimage_1_link_70shapeimage_1_link_71shapeimage_1_link_72shapeimage_1_link_73shapeimage_1_link_74shapeimage_1_link_75