Search results for "logspace"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
133	Till Tantau	Logspace Optimization Problems and Their Approximability Properties.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
119	Till Tantau	Logspace Optimization Problems and Their Approximability Properties.	FCT	2005	DBLP DOI BibTeX RDF
95	Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty 0001, Samir Datta, Sambuddha Roy	Planar and Grid Graph Reachability Problems.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Logspace, Algorithms, Planar graphs, Reachability, Complexity theory, Circuit complexity, Grid graphs
91	Satyanarayana V. Lokam, Meena Mahajan, V. Vinay	Logspace Verifiers, NC, and NP.	ISAAC	1995	DBLP DOI BibTeX RDF
88	Johannes Köbler, Sebastian Kuhnert	The Isomorphism Problem for k-Trees Is Complete for Logspace.	MFCS	2009	DBLP DOI BibTeX RDF	graph canonization, logspace completeness, graph isomorphism, space complexity, k-trees
84	Hans-Jörg Burtschick	Comparing Counting Classes for Logspace, One-way Logspace, and First-order.	MFCS	1995	DBLP DOI BibTeX RDF
77	Douglas Cenzer, Zia Uddin	Logspace Complexity of Functions and Structures.	CiE	2006	DBLP DOI BibTeX RDF	Complexity, Computability, Computable Model Theory
77	Vikraman Arvind, T. C. Vijayaraghavan	Abelian Permutation Group Problems and Logspace Counting Classes.	CCC	2004	DBLP DOI BibTeX RDF
77	Erich Grädel, Marc Spielmann	Logspace Reducibility via Abstract State Machines.	World Congress on Formal Methods	1999	DBLP DOI BibTeX RDF
63	Vikraman Arvind, Bireswar Das, Johannes Köbler	A Logspace Algorithm for Partial 2-Tree Canonization.	CSR	2008	DBLP DOI BibTeX RDF
60	Andreas Jakoby, Till Tantau	Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.	FSTTCS	2007	DBLP DOI BibTeX RDF	logspace algorithms, distance problem, longest path problem, bounded tree-width, K 4-minor-free graphs, Series-parallel graphs
56	Vikraman Arvind, Bireswar Das, Johannes Köbler	The Space Complexity of k -Tree Isomorphism.	ISAAC	2007	DBLP DOI BibTeX RDF
56	Kai-Min Chung, Omer Reingold, Salil P. Vadhan	S-T Connectivity on Digraphs with a Known Stationary Distribution.	CCC	2007	DBLP DOI BibTeX RDF
53	Georg Gottlob	Collapsing Oracle-Tape Hierarchies.	CCC	1996	DBLP DOI BibTeX RDF	tape, logspace, logarithmic space, machine model, complexity, query, oracle, circuit, Turing machine, generalized quantifier, relativization, bounded queries
49	Guillaume Bonfante	Some Programming Languages for Logspace and Ptime.	AMAST	2006	DBLP DOI BibTeX RDF
49	Alexander Leontjev, Vladimir Yu. Sazonov	Capturing LOGSPACE over Hereditarily-Finite Sets.	FoIKS	2000	DBLP DOI BibTeX RDF
49	Birgit Jenner	Closure under Complementation of Logspace Complexity Classes - A Survey.	Foundations of Computer Science: Potential - Theory - Cognition	1997	DBLP DOI BibTeX RDF
49	Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel	Structure and Importance of Logspace-MOD-Classes.	STACS	1991	DBLP DOI BibTeX RDF
42	Martin Hofmann 0001, Ulrich Schöpp	Pointer Programs and Undirected Reachability.	LICS	2009	DBLP DOI BibTeX RDF
42	Alina Beygelzimer, Mitsunori Ogihara	The (Non)Enumerability of the Determinant and the Rank.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
42	Thanh Minh Hoang, Thomas Thierauf	The Complexity of Verifying the Characteristic Polynomial and Testing Similarity.	CCC	2000	DBLP DOI BibTeX RDF
42	Matthias Ruhl	Counting and Addition Cannot Express Deterministic Transitive Closure.	LICS	1999	DBLP DOI BibTeX RDF	Counting quantifiers, circuit complexity, finite model theory, descriptive complexity theory
42	John Watrous	Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity.	CCC	1999	DBLP DOI BibTeX RDF	quantum computation, graph connectivity, space-bounded computation
42	Jin-yi Cai, Ashish V. Naik, D. Sivakumar	On the Existence of Hard Sparse Sets under Weak Reductions.	STACS	1996	DBLP DOI BibTeX RDF
42	Sairam Sairam, Jeffrey Scott Vitter, Roberto Tamassia	A Complexity Theoretic Approach to Incremental Computation.	STACS	1993	DBLP DOI BibTeX RDF
42	Richard J. Lipton	Efficient Checking of Computations.	STACS	1990	DBLP DOI BibTeX RDF
39	Jin-yi Cai, Hong Zhu 0004	Progress in Computational Complexity Theory.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	computational complexity theory, PCP theorem, logspace complexity, Reingold's theorem, GAP problem, complexity of lattice problems, worst-case to average-case reductions, extractors, pseudorandomness, inapproximability, primality testing, theoretical computer science, holographic algorithms
35	Till Tantau	A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.	STACS	2004	DBLP DOI BibTeX RDF
35	Grégory Lafitte, Jacques Mazoyer	The Infinite Versions of LOGSPACE != P Are Consistent with the Axioms of Set Theory.	MFCS	2000	DBLP DOI BibTeX RDF
35	Uriel Feige	A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.	ICALP	1994	DBLP DOI BibTeX RDF
35	Iain A. Stewart	Copmlete Problems for Logspace Involving Lexicographic First Paths in Graphs.	WG	1991	DBLP DOI BibTeX RDF
35	Klaus-Jörn Lange	Nondeterministic Logspace Reductions.	MFCS	1984	DBLP DOI BibTeX RDF
28	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification via Space-Efficient Direct Products.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17
28	Martin Hofmann 0001, Ulrich Schöpp	Pure Pointer Programs with Iteration.	CSL	2008	DBLP DOI BibTeX RDF
28	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification Via Space-Efficient Direct Products.	LATIN	2006	DBLP DOI BibTeX RDF	error-correcting codes, expanders, Direct products, hardness amplification
28	Georg Gottlob, Christoph Koch 0001, Reinhard Pichler, Luc Segoufin	The complexity of XPath query evaluation and XML typing.	J. ACM	2005	DBLP DOI BibTeX RDF	LOGCFL, XML, Complexity, XPath, DTD
28	Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan	Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.	CCC	2005	DBLP DOI BibTeX RDF
28	Thanh Minh Hoang, Thomas Thierauf	On the Minimal Polynomial of a Matrix.	COCOON	2002	DBLP DOI BibTeX RDF
28	Manindra Agrawal	Towards Uniform AC0 - Isomorphisms.	CCC	2001	DBLP DOI BibTeX RDF
28	Kai Salomaa, Derick Wood, Sheng Yu 0001	Complexity of E0L Structural Equivalence.	MFCS	1994	DBLP DOI BibTeX RDF
28	Iain A. Stewart	Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machines.	CSL	1992	DBLP DOI BibTeX RDF
28	Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes	Using Inductive Counting to Simulate Nondeterministic Computation.	MFCS	1990	DBLP DOI BibTeX RDF
28	Helmut Seidl	Deciding Equivalence of Finite Tree Automata.	STACS	1989	DBLP DOI BibTeX RDF
25	Derrick Stolee, Chris Bourke, N. V. Vinodchandran	A Log-Space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources.	CCC	2010	DBLP DOI BibTeX RDF	acyclic digraph, logspace algorithm, planar graph, reachability
25	Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney	L-Printable Sets.	CCC	1996	DBLP DOI BibTeX RDF	printability, logspace, rankability, computational complexity
25	Jin-yi Cai, D. Sivakumar	The Resolution of a Hartmanis Conjecture.	FOCS	1995	DBLP DOI BibTeX RDF	Hartmanis conjecture, sparse sets, logspace many-one reductions, sparse hard set, computational complexity
25	Mitsunori Ogihara	Sparse P-Hard Sets Yield Space-Efficient Algorithms.	FOCS	1995	DBLP DOI BibTeX RDF	sparse P-hard sets, space-efficient algorithms, logspace many-one reductions, poly-logarithmic space-computable many-one reductions, computational complexity
25	Ker-I Ko	Computational Complexity of Roots of Real Functions (Extended Abstract)	FOCS	1989	DBLP DOI BibTeX RDF	roots of real functions, one-to-one, k-to-one functions, discrete complexity classes, LOGSPACE, P, UP, classification, computational complexity, NP
21	Uma Girish, Ran Raz, Wei Zhan	Quantum Logspace Computations are Verifiable.	SOSA	2024	DBLP DOI BibTeX RDF
21	Anselm Haak, Arne Meier, Om Prakash 0002, B. V. Raghavendra Rao	Parameterised Counting in Logspace.	Algorithmica	2023	DBLP DOI BibTeX RDF
21	Uma Girish, Ran Raz, Wei Zhan	Quantum Logspace Computations are Verifiable.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
21	Yakov Shalunov	Leakage-Resilient Hardness Equivalence to Logspace Derandomization.	CoRR	2023	DBLP DOI BibTeX RDF
21	Steffen van Bergerem, Martin Grohe, Sandra Kiefer, Luca Oeljeklaus	Simulating Logspace-Recursion with Logarithmic Quantifier Depth.	CoRR	2023	DBLP DOI BibTeX RDF
21	Uma Girish, Ran Raz, Wei Zhan	Quantum Logspace Computations are Verifiable.	CoRR	2023	DBLP DOI BibTeX RDF
21	Steffen van Bergerem, Martin Grohe, Sandra Kiefer, Luca Oeljeklaus	Simulating Logspace-Recursion with Logarithmic Quantifier Depth.	LICS	2023	DBLP DOI BibTeX RDF
21	Reiner Czerwinski	Incomplete sets in P for logspace-reduction.	CoRR	2022	DBLP BibTeX RDF
21	Pratish Datta, Tapas Pal, Katsuyuki Takashima	Compact FE for Unbounded Attribute-Weighted Sums for Logspace from SXDH.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
21	William M. Hoza, Chris Umans	Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
21	Pratish Datta, Tapas Pal, Katsuyuki Takashima	Compact FE for Unbounded Attribute-Weighted Sums for Logspace from SXDH.	ASIACRYPT (1)	2022	DBLP DOI BibTeX RDF
21	Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros	#NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes.	J. ACM	2021	DBLP DOI BibTeX RDF
21	Cody Karcher	Logspace Sequential Quadratic Programming for Design Optimization.	CoRR	2021	DBLP BibTeX RDF
21	Jay Mardia	Logspace Reducibility From Secret Leakage Planted Clique.	CoRR	2021	DBLP BibTeX RDF
21	Uma Girish, Ran Raz, Wei Zhan	Quantum Logspace Algorithm for Powering Matrices with Bounded Norm.	ICALP	2021	DBLP DOI BibTeX RDF
21	Anselm Haak, Arne Meier, Om Prakash 0002, B. V. Raghavendra Rao	Parameterised Counting in Logspace.	STACS	2021	DBLP DOI BibTeX RDF
21	Reinhard Pichler	Technical Perspective: Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation.	SIGMOD Rec.	2020	DBLP DOI BibTeX RDF
21	Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation.	SIGMOD Rec.	2020	DBLP DOI BibTeX RDF
21	Uma Girish, Ran Raz, Wei Zhan	Quantum Logspace Algorithm for Powering Matrices with Bounded Norm.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
21	Neil D. Jones, Siddharth Bhaskar, Cynthia Kop, Jakob Grue Simonsen	Cons-free Programs and Complexity Classes between LOGSPACE and PTIME.	VPT/HCVS@ETAPS	2020	DBLP DOI BibTeX RDF
21	Uma Girish, Ran Raz, Wei Zhan	Quantum Logspace Algorithm for Powering Matrices with Bounded Norm.	CoRR	2020	DBLP BibTeX RDF
21	Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation.	CoRR	2019	DBLP BibTeX RDF
21	Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros	Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation.	PODS	2019	DBLP DOI BibTeX RDF
21	Chetan Gupta 0002, Vimal Raj Sharma, Raghunath Tewari	Reachability in O(log n) Genus Graphs is in Unambiguous Logspace.	STACS	2019	DBLP DOI BibTeX RDF
21	Paraschos Koutris, Jef Wijsen	Consistent Query Answering for Primary Keys in Logspace.	ICDT	2019	DBLP DOI BibTeX RDF
21	Paraschos Koutris, Jef Wijsen	Consistent Query Answering for Primary Keys in Logspace.	CoRR	2018	DBLP BibTeX RDF
21	Lukasz Czajka 0001	Term Rewriting Characterisation of LOGSPACE for Finite and Infinite Data.	FSCD	2018	DBLP DOI BibTeX RDF
21	Dean Doron, Amir Sarid, Amnon Ta-Shma	On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace.	Comput. Complex.	2017	DBLP DOI BibTeX RDF
21	Marc Bagnol	Multiplicative-Additive Proof Equivalence is Logspace-complete, via Binary Decision Trees.	CoRR	2017	DBLP BibTeX RDF
21	Marc Bagnol	Multiplicative-Additive Proof Equivalence is Logspace-complete, via Binary Decision Trees.	Log. Methods Comput. Sci.	2017	DBLP DOI BibTeX RDF
21	Michael Elberfeld, Pascal Schweitzer	Canonizing Graphs of Bounded Tree Width in Logspace.	ACM Trans. Comput. Theory	2017	DBLP DOI BibTeX RDF
21	Christian Glaßer, Maximilian Witek	Autoreducibility and mitoticity of logspace-complete sets for NP and other classes.	Inf. Comput.	2017	DBLP DOI BibTeX RDF
21	William M. Hoza, Chris Umans	Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace.	STOC	2017	DBLP DOI BibTeX RDF
21	Dean Doron, Amir Sarid, Amnon Ta-Shma	On approximating the eigenvalues of stochastic matrices in probabilistic logspace.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
21	Boris Brimkov, Illya V. Hicks	On the logspace shortest path problem.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
21	Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky 0001	Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace.	J. Discrete Algorithms	2016	DBLP DOI BibTeX RDF
21	Armin Weiß	A Logspace Solution to the Word and Conjugacy problem of Generalized Baumslag-Solitar Groups.	CoRR	2016	DBLP BibTeX RDF
21	William M. Hoza, Chris Umans	Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace.	CoRR	2016	DBLP BibTeX RDF
21	Benjamin A. Burton, Murray Elder, Arkadius G. Kalka, Stephan Tillmann	2-manifold recognition is in logspace.	J. Comput. Geom.	2016	DBLP DOI BibTeX RDF
21	Volker Diekert, Jonathan Kausch	Logspace computations in graph products.	J. Symb. Comput.	2016	DBLP DOI BibTeX RDF
21	Peter Dixon 0002, Debasis Mandal, Aduri Pavan, N. V. Vinodchandran	A Note on the Advice Complexity of Multipass Randomized Logspace.	MFCS	2016	DBLP DOI BibTeX RDF
21	Armin Weiß	A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups.	AMS-EMS-SPM Joint Meeting	2016	DBLP BibTeX RDF
21	Michael Elberfeld, Pascal Schweitzer	Canonizing Graphs of Bounded Tree Width in Logspace.	STACS	2016	DBLP DOI BibTeX RDF
21	Maurice Chandoo	Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace.	STACS	2016	DBLP DOI BibTeX RDF
21	Boris Brimkov	A reduction of the logspace shortest path problem to biconnected graphs.	CoRR	2015	DBLP BibTeX RDF
21	Michael Elberfeld, Pascal Schweitzer	Canonizing Graphs of Bounded Tree Width in Logspace.	CoRR	2015	DBLP BibTeX RDF
21	Maurice Chandoo	Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace.	CoRR	2015	DBLP BibTeX RDF
21	Jeremy MacDonald, Alexei G. Myasnikov, Andrey Nikolaev, Svetla Vassileva	Logspace and compressed-word computations in nilpotent groups.	CoRR	2015	DBLP BibTeX RDF
21	Marc Bagnol	MALL proof equivalence is Logspace-complete, via binary decision diagrams.	CoRR	2015	DBLP BibTeX RDF
21	Bireswar Das, Murali Krishna Enduri, I. Vinod Reddy	Logspace and FPT Algorithms for Graph Isomorphism for Subclasses of Bounded Tree-Width Graphs.	WALCOM	2015	DBLP DOI BibTeX RDF
21	Marc Bagnol	MALL Proof Equivalence is Logspace-Complete, via Binary Decision Diagrams.	TLCA	2015	DBLP DOI BibTeX RDF
21	Víctor Dalmau, László Egri, Pavol Hell, Benoît Larose, Arash Rafiey	Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy.	LICS	2015	DBLP DOI BibTeX RDF