Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
133 | Till Tantau |
Logspace Optimization Problems and Their Approximability Properties. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 41(2), pp. 327-350, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
119 | Till Tantau |
Logspace Optimization Problems and Their Approximability Properties. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FCT ![In: Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005, Proceedings, pp. 103-114, 2005, Springer, 3-540-28193-2. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 45(4), pp. 675-723, 2009. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ISAAC ![In: Algorithms and Computation, 6th International Symposium, ISAAC '95, Cairns, Australia, December 4-6, 1995, Proceedings, pp. 52-61, 1995, Springer, 3-540-60573-8. The full citation details ...](Pics/full.jpeg) |
1995 |
DBLP DOI BibTeX RDF |
|
88 | Johannes Köbler, Sebastian Kuhnert |
The Isomorphism Problem for k-Trees Is Complete for Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings, pp. 537-548, 2009, Springer, 978-3-642-03815-0. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1995, 20th International Symposium, MFCS'95, Prague, Czech Republic, August 28 - September 1, 1995, Proceedings, pp. 139-148, 1995, Springer, 3-540-60246-1. The full citation details ...](Pics/full.jpeg) |
1995 |
DBLP DOI BibTeX RDF |
|
77 | Douglas Cenzer, Zia Uddin |
Logspace Complexity of Functions and Structures. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CiE ![In: Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30-July 5, 2006, Proceedings, pp. 75-84, 2006, Springer, 3-540-35466-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
Complexity, Computability, Computable Model Theory |
77 | Vikraman Arvind, T. C. Vijayaraghavan |
Abelian Permutation Group Problems and Logspace Counting Classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA, pp. 204-214, 2004, IEEE Computer Society, 0-7695-2120-7. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
77 | Erich Grädel, Marc Spielmann |
Logspace Reducibility via Abstract State Machines. ![Search on Bibsonomy](Pics/bibsonomy.png) |
World Congress on Formal Methods ![In: FM'99 - Formal Methods, World Congress on Formal Methods in the Development of Computing Systems, Toulouse, France, September 20-24, 1999, Proceedings, Volume II, pp. 1738-1757, 1999, Springer, 3-540-66588-9. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
63 | Vikraman Arvind, Bireswar Das, Johannes Köbler |
A Logspace Algorithm for Partial 2-Tree Canonization. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSR ![In: Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings, pp. 40-51, 2008, Springer, 978-3-540-79708-1. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
60 | Andreas Jakoby, Till Tantau |
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FSTTCS ![In: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference, New Delhi, India, December 12-14, 2007, Proceedings, pp. 216-227, 2007, Springer, 978-3-540-77049-7. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ISAAC ![In: Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, pp. 822-833, 2007, Springer, 978-3-540-77118-0. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
56 | Kai-Min Chung, Omer Reingold, Salil P. Vadhan |
S-T Connectivity on Digraphs with a Known Stationary Distribution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA, pp. 236-249, 2007, IEEE Computer Society, 0-7695-2780-9. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
53 | Georg Gottlob |
Collapsing Oracle-Tape Hierarchies. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996, pp. 33-42, 1996, IEEE Computer Society, 0-8186-7386-9. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
AMAST ![In: Algebraic Methodology and Software Technology, 11th International Conference, AMAST 2006, Kuressaare, Estonia, July 5-8, 2006, Proceedings, pp. 66-80, 2006, Springer, 3-540-35633-9. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
49 | Alexander Leontjev, Vladimir Yu. Sazonov |
Capturing LOGSPACE over Hereditarily-Finite Sets. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FoIKS ![In: Foundations of Information and Knowledge Systems, First International Symposium, FoIKS 2000, Burg, Germany, February 14-17, 2000, Proceedings, pp. 156-175, 2000, Springer, 3-540-67100-5. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
49 | Birgit Jenner |
Closure under Complementation of Logspace Complexity Classes - A Survey. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Foundations of Computer Science: Potential - Theory - Cognition ![In: Foundations of Computer Science: Potential - Theory - Cognition, to Wilfried Brauer on the occasion of his sixtieth birthday, pp. 163-175, 1997, Springer, 3-540-63746-X. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
|
49 | Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel |
Structure and Importance of Logspace-MOD-Classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 91, 8th Annual Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany, February 14-16, 1991, Proceedings, pp. 360-371, 1991, Springer, 3-540-53709-0. The full citation details ...](Pics/full.jpeg) |
1991 |
DBLP DOI BibTeX RDF |
|
42 | Martin Hofmann 0001, Ulrich Schöpp |
Pointer Programs and Undirected Reachability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LICS ![In: Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LICS 2009, 11-14 August 2009, Los Angeles, CA, USA, pp. 133-142, 2009, IEEE Computer Society, 978-0-7695-3746-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
42 | Alina Beygelzimer, Mitsunori Ogihara |
The (Non)Enumerability of the Determinant and the Rank. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 36(4), pp. 359-374, 2003. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
42 | Thanh Minh Hoang, Thomas Thierauf |
The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 87-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
42 | Matthias Ruhl |
Counting and Addition Cannot Express Deterministic Transitive Closure. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LICS ![In: 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, pp. 326-334, 1999, IEEE Computer Society, 0-7695-0158-3. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 180-187, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Grenoble, France, February 22-24, 1996, Proceedings, pp. 307-318, 1996, Springer, 3-540-60922-9. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP DOI BibTeX RDF |
|
42 | Sairam Sairam, Jeffrey Scott Vitter, Roberto Tamassia |
A Complexity Theoretic Approach to Incremental Computation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993, Proceedings, pp. 640-649, 1993, Springer, 3-540-56503-5. The full citation details ...](Pics/full.jpeg) |
1993 |
DBLP DOI BibTeX RDF |
|
42 | Richard J. Lipton |
Efficient Checking of Computations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 90, 7th Annual Symposium on Theoretical Aspects of Computer Science, Rouen, France, February 22-24, 1990, Proceedings, pp. 207-215, 1990, Springer, 3-540-52282-4. The full citation details ...](Pics/full.jpeg) |
1990 |
DBLP DOI BibTeX RDF |
|
39 | Jin-yi Cai, Hong Zhu 0004 |
Progress in Computational Complexity Theory. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comput. Sci. Technol. ![In: J. Comput. Sci. Technol. 20(6), pp. 735-750, 2005. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, pp. 326-337, 2004, Springer, 3-540-21236-1. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2000, 25th International Symposium, MFCS 2000, Bratislava, Slovakia, August 28 - September 1, 2000, Proceedings, pp. 508-517, 2000, Springer, 3-540-67901-4. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
35 | Uriel Feige |
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 21st International Colloquium, ICALP94, Jerusalem, Israel, July 11-14, 1994, Proceedings, pp. 499-507, 1994, Springer, 3-540-58201-0. The full citation details ...](Pics/full.jpeg) |
1994 |
DBLP DOI BibTeX RDF |
|
35 | Iain A. Stewart |
Copmlete Problems for Logspace Involving Lexicographic First Paths in Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WG ![In: 17th International Workshop, WG '91, Fischbachau, Germany, June 17-19, 1991, Proceedings, pp. 198-208, 1991, Springer, 3-540-55121-2. The full citation details ...](Pics/full.jpeg) |
1991 |
DBLP DOI BibTeX RDF |
|
35 | Klaus-Jörn Lange |
Nondeterministic Logspace Reductions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1984, Praha, Czechoslovakia, September 3-7, 1984, Proceedings, pp. 378-388, 1984, Springer, 3-540-13372-0. The full citation details ...](Pics/full.jpeg) |
1984 |
DBLP DOI BibTeX RDF |
|
28 | Venkatesan Guruswami, Valentine Kabanets |
Hardness Amplification via Space-Efficient Direct Products. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Comput. Complex. ![In: Comput. Complex. 17(4), pp. 475-500, 2008. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17 |
28 | Martin Hofmann 0001, Ulrich Schöpp |
Pure Pointer Programs with Iteration. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: Computer Science Logic, 22nd International Workshop, CSL 2008, 17th Annual Conference of the EACSL, Bertinoro, Italy, September 16-19, 2008. Proceedings, pp. 79-93, 2008, Springer, 978-3-540-87530-7. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
28 | Venkatesan Guruswami, Valentine Kabanets |
Hardness Amplification Via Space-Efficient Direct Products. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LATIN ![In: LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings, pp. 556-568, 2006, Springer, 3-540-32755-X. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 52(2), pp. 284-335, 2005. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pp. 13-27, 2005, IEEE Computer Society, 0-7695-2364-1. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
28 | Thanh Minh Hoang, Thomas Thierauf |
On the Minimal Polynomial of a Matrix. ![Search on Bibsonomy](Pics/bibsonomy.png) |
COCOON ![In: Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings, pp. 37-46, 2002, Springer, 3-540-43996-X. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
28 | Manindra Agrawal |
Towards Uniform AC0 - Isomorphisms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 13-20, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
28 | Kai Salomaa, Derick Wood, Sheng Yu 0001 |
Complexity of E0L Structural Equivalence. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1994, 19th International Symposium, MFCS'94, Kosice, Slovakia, August 22 - 26, 1994, Proceedings, pp. 587-596, 1994, Springer, 3-540-58338-6. The full citation details ...](Pics/full.jpeg) |
1994 |
DBLP DOI BibTeX RDF |
|
28 | Iain A. Stewart |
Logical Characterization of Bounded Query Classes II: Polynomial-Time Oracle Machines. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: Computer Science Logic, 6th Workshop, CSL '92, San Miniato, Italy, September 28 - October 2, 1992, Selected Papers, pp. 410-424, 1992, Springer, 3-540-56992-8. The full citation details ...](Pics/full.jpeg) |
1992 |
DBLP DOI BibTeX RDF |
|
28 | Gerhard Buntrock, Lane A. Hemachandra, Dirk Siefkes |
Using Inductive Counting to Simulate Nondeterministic Computation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1990, MFCS'90, Banská Bystrica, Czechoslovakia, August 27-31, 1990, Proceedings, pp. 187-194, 1990, Springer, 3-540-52953-5. The full citation details ...](Pics/full.jpeg) |
1990 |
DBLP DOI BibTeX RDF |
|
28 | Helmut Seidl |
Deciding Equivalence of Finite Tree Automata. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 89, 6th Annual Symposium on Theoretical Aspects of Computer Science, Paderborn, FRG, February 16-18, 1989, Proceedings, pp. 480-492, 1989, Springer, 3-540-50840-6. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 131-138, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
acyclic digraph, logspace algorithm, planar graph, reachability |
25 | Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney |
L-Printable Sets. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996, pp. 97-106, 1996, IEEE Computer Society, 0-8186-7386-9. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP DOI BibTeX RDF |
printability, logspace, rankability, computational complexity |
25 | Jin-yi Cai, D. Sivakumar |
The Resolution of a Hartmanis Conjecture. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pp. 362-371, 1995, IEEE Computer Society, 0-8186-7183-1. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pp. 354-361, 1995, IEEE Computer Society, 0-8186-7183-1. The full citation details ...](Pics/full.jpeg) |
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) ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pp. 204-209, 1989, IEEE Computer Society, 0-8186-1982-1. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SOSA ![In: 2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024, pp. 144-150, 2024, SIAM, 978-1-61197-793-6. The full citation details ...](Pics/full.jpeg) |
2024 |
DBLP DOI BibTeX RDF |
|
21 | Anselm Haak, Arne Meier, Om Prakash 0002, B. V. Raghavendra Rao |
Parameterised Counting in Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Algorithmica ![In: Algorithmica 85(10), pp. 2923-2961, October 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
21 | Uma Girish, Ran Raz, Wei Zhan |
Quantum Logspace Computations are Verifiable. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR23, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP BibTeX RDF |
|
21 | Yakov Shalunov |
Leakage-Resilient Hardness Equivalence to Logspace Derandomization. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2312.14023, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
21 | Steffen van Bergerem, Martin Grohe, Sandra Kiefer, Luca Oeljeklaus |
Simulating Logspace-Recursion with Logarithmic Quantifier Depth. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2304.12948, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
21 | Uma Girish, Ran Raz, Wei Zhan |
Quantum Logspace Computations are Verifiable. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2307.11083, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
21 | Steffen van Bergerem, Martin Grohe, Sandra Kiefer, Luca Oeljeklaus |
Simulating Logspace-Recursion with Logarithmic Quantifier Depth. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LICS ![In: LICS, pp. 1-13, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
21 | Reiner Czerwinski |
Incomplete sets in P for logspace-reduction. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2201.08501, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP BibTeX RDF |
|
21 | Pratish Datta, Tapas Pal, Katsuyuki Takashima |
Compact FE for Unbounded Attribute-Weighted Sums for Logspace from SXDH. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2022, pp. 1594, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP BibTeX RDF |
|
21 | William M. Hoza, Chris Umans |
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 51(2), pp. 17-281, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
21 | Pratish Datta, Tapas Pal, Katsuyuki Takashima |
Compact FE for Unbounded Attribute-Weighted Sums for Logspace from SXDH. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ASIACRYPT (1) ![In: Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part I, pp. 126-159, 2022, Springer, 978-3-031-22962-6. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 68(6), pp. 48:1-48:40, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
21 | Cody Karcher |
Logspace Sequential Quadratic Programming for Design Optimization. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2105.14441, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
21 | Jay Mardia |
Logspace Reducibility From Secret Leakage Planted Clique. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2107.11886, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
21 | Uma Girish, Ran Raz, Wei Zhan |
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference)., pp. 73:1-73:20, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-195-5. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
21 | Anselm Haak, Arne Meier, Om Prakash 0002, B. V. Raghavendra Rao |
Parameterised Counting in Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference)., pp. 40:1-40:17, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-180-1. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
21 | Reinhard Pichler |
Technical Perspective: Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIGMOD Rec. ![In: SIGMOD Rec. 49(1), pp. 51, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
21 | Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros |
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIGMOD Rec. ![In: SIGMOD Rec. 49(1), pp. 52-59, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
21 | Uma Girish, Ran Raz, Wei Zhan |
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR20, 2020. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
VPT/HCVS@ETAPS ![In: Proceedings 8th International Workshop on Verification and Program Transformation and 7th Workshop on Horn Clauses for Verification and Synthesis, VPT/HCVS@ETAPS 2020, Dublin, Ireland, 25-26th April 2020., pp. 65-79, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
21 | Uma Girish, Ran Raz, Wei Zhan |
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2006.04880, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
21 | Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros |
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1906.09226, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
21 | Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, Cristian Riveros |
Efficient Logspace Classes for Enumeration, Counting, and Uniform Generation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
PODS ![In: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019., pp. 59-73, 2019, ACM, 978-1-4503-6227-6. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pp. 34:1-34:13, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-100-9. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
21 | Paraschos Koutris, Jef Wijsen |
Consistent Query Answering for Primary Keys in Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICDT ![In: 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pp. 23:1-23:19, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-101-6. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
21 | Paraschos Koutris, Jef Wijsen |
Consistent Query Answering for Primary Keys in Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1810.03386, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
21 | Lukasz Czajka 0001 |
Term Rewriting Characterisation of LOGSPACE for Finite and Infinite Data. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FSCD ![In: 3rd International Conference on Formal Structures for Computation and Deduction, FSCD 2018, July 9-12, 2018, Oxford, UK, pp. 13:1-13:19, 2018, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-077-4. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
21 | Dean Doron, Amir Sarid, Amnon Ta-Shma |
On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Comput. Complex. ![In: Comput. Complex. 26(2), pp. 393-420, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
21 | Marc Bagnol |
Multiplicative-Additive Proof Equivalence is Logspace-complete, via Binary Decision Trees. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1707.00991, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
21 | Marc Bagnol |
Multiplicative-Additive Proof Equivalence is Logspace-complete, via Binary Decision Trees. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Log. Methods Comput. Sci. ![In: Log. Methods Comput. Sci. 13(4), 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
21 | Michael Elberfeld, Pascal Schweitzer |
Canonizing Graphs of Bounded Tree Width in Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Theory ![In: ACM Trans. Comput. Theory 9(3), pp. 12:1-12:29, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
21 | Christian Glaßer, Maximilian Witek |
Autoreducibility and mitoticity of logspace-complete sets for NP and other classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Comput. ![In: Inf. Comput. 256, pp. 93-107, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
21 | William M. Hoza, Chris Umans |
Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pp. 629-640, 2017, ACM, 978-1-4503-4528-6. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
21 | Dean Doron, Amir Sarid, Amnon Ta-Shma |
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR16, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
21 | Boris Brimkov, Illya V. Hicks |
On the logspace shortest path problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR16, 2016. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Discrete Algorithms ![In: J. Discrete Algorithms 38-41, pp. 38-49, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
21 | Armin Weiß |
A Logspace Solution to the Word and Conjugacy problem of Generalized Baumslag-Solitar Groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1602.02445, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
21 | William M. Hoza, Chris Umans |
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1610.01199, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
21 | Benjamin A. Burton, Murray Elder, Arkadius G. Kalka, Stephan Tillmann |
2-manifold recognition is in logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comput. Geom. ![In: J. Comput. Geom. 7(1), pp. 70-85, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
21 | Volker Diekert, Jonathan Kausch |
Logspace computations in graph products. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Symb. Comput. ![In: J. Symb. Comput. 75, pp. 94-109, 2016. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pp. 31:1-31:7, 2016, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-016-3. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
21 | Armin Weiß |
A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
AMS-EMS-SPM Joint Meeting ![In: Algebra and Computer Science, 2016, American Mathematical Society, 978-1-4704-2303-2. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
21 | Michael Elberfeld, Pascal Schweitzer |
Canonizing Graphs of Bounded Tree Width in Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pp. 32:1-32:14, 2016, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-001-9. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
21 | Maurice Chandoo |
Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pp. 26:1-26:13, 2016, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-001-9. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
21 | Boris Brimkov |
A reduction of the logspace shortest path problem to biconnected graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1511.07100, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
21 | Michael Elberfeld, Pascal Schweitzer |
Canonizing Graphs of Bounded Tree Width in Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1506.07810, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
21 | Maurice Chandoo |
Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1507.03348, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
21 | Jeremy MacDonald, Alexei G. Myasnikov, Andrey Nikolaev, Svetla Vassileva |
Logspace and compressed-word computations in nilpotent groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1503.03888, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
21 | Marc Bagnol |
MALL proof equivalence is Logspace-complete, via binary decision diagrams. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1502.01993, 2015. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
WALCOM ![In: WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings, pp. 329-334, 2015, Springer, 978-3-319-15611-8. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
21 | Marc Bagnol |
MALL Proof Equivalence is Logspace-Complete, via Binary Decision Diagrams. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TLCA ![In: 13th International Conference on Typed Lambda Calculi and Applications, TLCA 2015, July 1-3, 2015, Warsaw, Poland, pp. 60-75, 2015, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-939897-87-3. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LICS ![In: 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pp. 487-498, 2015, IEEE Computer Society, 978-1-4799-8875-4. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|