Publications.ComPlexity

 
Counting Classes and the fine structure between NC1 and L (with Meena Mahajan, B. V. R. Rao, Michael Thomas and Heribert Vollmer), To appear 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), 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://arxiv.org/abs/0912.4602http://www.imsc.res.in/~bireswarhttp://www.imsc.res.in/~prajaktahttp://www.imsc.res.in/~prajaktahttps://image.informatik.htw-aalen.de/Thierauf/Papers/Kfree-iso.pdfhttp://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/publications.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/publications.complexity_files/plan.ggr_1.pdfshapeimage_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_58