Search results for "Log-space"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
54	Omer Reingold	Undirected connectivity in log-space.	J. ACM	2008	DBLP DOI BibTeX RDF	bounded space algorithms, Derandomization, pseudorandom generator
54	Omer Reingold	Undirected ST-connectivity in log-space.	STOC	2005	DBLP DOI BibTeX RDF
49	Richard D. Regan, Alex Delis	An Analysis of Main-Memory and Log Space Usage in Extended Ephemeral Logging.	BNCOD	2001	DBLP DOI BibTeX RDF
48	Joe Kilian	Zero-knowledge with Log-Space Verifiers	FOCS	1988	DBLP DOI BibTeX RDF	language-recognition, log-space verifiers, probabilistic log-space automata, exponential-time languages, protocols, zero knowledge, interactive proof systems
44	Fuxiang Yu	On the Representations of NC and Log-Space Real Numbers.	COCOON	2007	DBLP DOI BibTeX RDF	representations of real numbers, Cauchy function, left cut, P, Log-space, Complexity, expressive power, NC
38	Ioan I. Macarie	On the Structure of Log-Space Probabilistic Complexity Classes (Extended Abstract).	STACS	1995	DBLP DOI BibTeX RDF
35	Christian Glaßer	Space-Efficient Informational Redundancy.	ISAAC	2008	DBLP DOI BibTeX RDF
31	Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc	How to meet when you forget: log-space rendezvous in arbitrary graphs.	PODC	2010	DBLP DOI BibTeX RDF	exploration, rendezvous, compact data structure
29	Burkhard Monien, Ivan Hal Sudborough	Time and Space Bounded Complexity Classes and Bandwidth Constrained Problems (A Survey).	MFCS	1981	DBLP DOI BibTeX RDF
28	Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum	Delegating computation: interactive proofs for muggles.	STOC	2008	DBLP DOI BibTeX RDF	muggles, delegation, interactive proofs
26	Eric Allender, David A. Mix Barrington, William Hesse	Uniform Circuits for Division: Consequences and Problems.	CCC	2001	DBLP DOI BibTeX RDF
25	Richard J. Lipton, Anastasios Viglas	On the Complexity of SAT.	FOCS	1999	DBLP DOI BibTeX RDF	time-space, log-space uniform circuits, lower bounds, satisfiability
22	Clifford Bergman, Giora Slutzki	Computational Complexity of Some Problems Involving Congruences on Algebras.	LICS	2000	DBLP DOI BibTeX RDF	fully invariant, subdirectly irreducible, nondeterministic log-space, nondeterministic polynomial time, congruence, simple
22	Steven Perron	A Propositional Proof System for Log Space.	CSL	2005	DBLP DOI BibTeX RDF
22	Michal Koucký 0001	Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n4.03).	COCOON	2001	DBLP DOI BibTeX RDF
21	Kalina Jasinska, Nikos Karampatziakis	Log-time and Log-space Extreme Classification.	CoRR	2016	DBLP BibTeX RDF
21	Ivan Hal Sudborough	The Complexity of Path Problems in Graphs and Path Systems of Bounded Bandwidth.	WG	1980	DBLP DOI BibTeX RDF
20	Kamal Ali, Mark Scarr	Robust methodologies for modeling web click distributions.	WWW	2007	DBLP DOI BibTeX RDF	distribution fitting
20	Burkhard Monien, Ivan Hal Sudborough	On Eliminating Nondeterminism From Turing Machines Which Use Less Than Logarithmic Worktape Space.	ICALP	1979	DBLP DOI BibTeX RDF
17	Takumi Kasai, Akeo Adachi, Shigeki Iwata	Classes of pebble games and complete problems.	ACM Annual Conference (2)	1978	DBLP DOI BibTeX RDF	Exponential time, Log-space, Two-person game, Winning strategy, Polynomial time, Turing machine, NP, Pebble game, Polynomial space
17	Thomas Thierauf, Fabian Wagner	Reachability in K3, 3-Free Graphs and K5-Free Graphs Is in Unambiguous Log-Space.	FCT	2009	DBLP DOI BibTeX RDF
17	Michael T. Goodrich, Jonathan Z. Sun	Checking Value-Sensitive Data Structures in Sublinear Space.	ISAAC	2007	DBLP DOI BibTeX RDF
14	Anders Dessmark, Andrzej Lingas, Anil Maheshwari	Multi-List Ranking: Complexity and Applications.	STACS	1993	DBLP DOI BibTeX RDF
13	Ming-Hsiu Lai, Ming-Feng Yu, Sau-Gee Chen	An efficient modified Phong shading algorithm & its low-complexity realization.	ISCAS (4)	2002	DBLP DOI BibTeX RDF
13	Patrick W. Dymond, Walter L. Ruzzo	Parallel RAMs with owned global memory and deterministic context-free language recognition.	J. ACM	2000	DBLP DOI BibTeX RDF	CROW-PRAM, DCFL recognition, owner write, parallel algorithms
13	Edward Pyne, Ran Raz, Wei Zhan	Certified Hardness vs. Randomness for Log-Space.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
13	Rafael Pass, Oren Renard	Characterizing the Power of (Persistent) Randomness in Log-space.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
13	Edward Pyne, Ran Raz, Wei Zhan	Certified Hardness vs. Randomness for Log-Space.	CoRR	2023	DBLP DOI BibTeX RDF
13	Edward Pyne, Ran Raz, Wei Zhan	Certified Hardness vs. Randomness for Log-Space.	FOCS	2023	DBLP DOI BibTeX RDF
13	Matthew Pitkin	lintegrate: A C/Python numerical integration library for working in log-space.	J. Open Source Softw.	2022	DBLP DOI BibTeX RDF
13	Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner	Planar Graph Isomorphism Is in Log-Space.	ACM Trans. Comput. Theory	2022	DBLP DOI BibTeX RDF
13	Hui Sun 0002, Jianzhong Huang 0001, Xiao Qin 0001, Changsheng Xie	DLSpace: Optimizing SSD Lifetime via An Efficient Distributed Log Space Allocation Strategy.	ACM Trans. Embed. Comput. Syst.	2019	DBLP DOI BibTeX RDF
13	Ofer Grossman, Yang P. Liu	Reproducibility and Pseudo-Determinism in Log-Space.	SODA	2019	DBLP DOI BibTeX RDF
13	Ofer Grossman, Yang P. Liu	Reproducibility and Pseudo-Determinism in Log-Space.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
13		Derandomizing the Lovasz Local Lemma via log-space statistical tests.	CoRR	2018	DBLP BibTeX RDF
13	Ofer Grossman, Yang P. Liu	Reproducibility and Pseudo-Determinism in Log-Space.	CoRR	2018	DBLP BibTeX RDF
13	Alexei Miasnikov, Svetla Vassileva	Log-space conjugacy problem in the Grigorchuk group.	Groups Complex. Cryptol.	2017	DBLP DOI BibTeX RDF
13	Han-Jung Chou, Pei-Li Kuo, Jing-Sin Liu	Numerical streamline path planning based on log-space harmonic potential function: A simulation study.	RCAR	2017	DBLP DOI BibTeX RDF
13	Kyle Hollins Wray, Dirk Ruiken, Roderic A. Grupen, Shlomo Zilberstein	Log-space harmonic function path planning.	IROS	2016	DBLP DOI BibTeX RDF
13	Anant Dhayal, Jayalal Sarma, Saurabh Sawlani	Polynomial Min/Max-weighted Reachability is in Unambiguous Log-space.	FSTTCS	2014	DBLP DOI BibTeX RDF
13	Wen-Ju Cheng	Randomized Search of Graphs in Log Space and Probabilistic Computation.		2014	RDF
13	Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek	Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
13	Bireswar Das, Samir Datta, Prajakta Nimbhorkar	Log-Space Algorithms for Paths and Matchings in k-Trees.	Theory Comput. Syst.	2013	DBLP DOI BibTeX RDF
13	Abuzer Yakaryilmaz	Log-space counter is useful for unary languages by help of a constant-size quantum register.	CoRR	2013	DBLP BibTeX RDF
13	Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek	Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions.	ICALP (1)	2013	DBLP DOI BibTeX RDF
13	Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran	On the power of unambiguity in log-space.	Comput. Complex.	2012	DBLP DOI BibTeX RDF
13	Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc	How to meet when you forget: log-space rendezvous in arbitrary graphs.	Distributed Comput.	2012	DBLP DOI BibTeX RDF
13	Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky 0001	Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space	CoRR	2012	DBLP BibTeX RDF
13	Abuzer Yakaryilmaz, A. C. Cem Say	NP has log-space verifiers with fixed-size public quantum registers	CoRR	2011	DBLP BibTeX RDF
13	Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar	Longest Paths in Planar DAGs in Unambiguous Log-Space.	Chic. J. Theor. Comput. Sci.	2010	DBLP BibTeX RDF
13	Ajesh Babu, Nutan Limaye, Girish Varma	Streaming algorithms for some problems in log-space.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
13	Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner	Graph Isomorphism for K3,3-free and K5-free graphs is in Log-space.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
13	Hiroaki Kotera	Image Color Mapping in Complex Log Space.	CIC	2010	DBLP DOI BibTeX RDF
13	Ajesh Babu, Nutan Limaye, Girish Varma	Streaming Algorithms for Some Problems in Log-Space.	TAMC	2010	DBLP DOI BibTeX RDF
13	Bireswar Das, Samir Datta, Prajakta Nimbhorkar	Log-space Algorithms for Paths and Matchings in k-trees.	STACS	2010	DBLP DOI BibTeX RDF
13	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
13	Derrick Stolee, Chris Bourke, N. V. Vinodchandran	A log-space algorithm for reachability in planar DAGs with few sources.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
13	Fabian Wagner, Thomas Thierauf	Reachability in K3,3-free Graphs and K5-free Graphs is in Unambiguous Log-Space.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
13	Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf	Planar Graph Isomorphism is in Log-space.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
13	Bireswar Das, Samir Datta, Prajakta Nimbhorkar	Log-space Algorithms for Paths and Matchings in k-trees	CoRR	2009	DBLP BibTeX RDF
13	Chris Bourke, Raghunath Tewari, N. V. Vinodchandran	Directed Planar Reachability Is in Unambiguous Log-Space.	ACM Trans. Comput. Theory	2009	DBLP DOI BibTeX RDF
13	Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner	Planar Graph Isomorphism is in Log-Space.	Algebraic Methods in Computational Complexity	2009	DBLP BibTeX RDF
13	Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner	Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.	FSTTCS	2009	DBLP DOI BibTeX RDF
13	Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner	Planar Graph Isomorphism is in Log-Space.	CCC	2009	DBLP DOI BibTeX RDF
13	Samir Datta, Nutan Limaye, Prajakta Nimbhorkar	3-connected Planar Graph Isomorphism is in Log-space	CoRR	2008	DBLP BibTeX RDF
13	Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner	A Log-space Algorithm for Canonization of Planar Graphs	CoRR	2008	DBLP BibTeX RDF
13	Samir Datta, Nutan Limaye, Prajakta Nimbhorkar	3-connected Planar Graph Isomorphism is in Log-space.	FSTTCS	2008	DBLP DOI BibTeX RDF
13	Chris Bourke, Raghunath Tewari, N. V. Vinodchandran	Directed Planar Reachability is in Unambiguous Log-Space.	CCC	2007	DBLP DOI BibTeX RDF
13	Omer Reingold	Undirected ST-Connectivity in Log-Space	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
13	Michael Szydlo	Merkle Tree Traversal in Log Space and Time.	EUROCRYPT	2004	DBLP DOI BibTeX RDF	authentication path, tail zipping, fractal traversal, binary tree, pebbling, Merkle tree, amortization
13	Chris Pollett	A theory for Log-Space and NLIN versus coNLIN.	J. Symb. Log.	2003	DBLP DOI BibTeX RDF
13	Michal Koucký 0001	Log-space constructible universal traversal sequences for cycles of length O(n4.03).	Theor. Comput. Sci.	2003	DBLP DOI BibTeX RDF
13	Michal Koucký 0001	Log-space Constructible Universal Traversal Sequences for Cycles of Length O(n4.03)	Electron. Colloquium Comput. Complex.	2001	DBLP BibTeX RDF
13	Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén	Log-Space Polynomial End-to-End Communication.	SIAM J. Comput.	1998	DBLP DOI BibTeX RDF
13	Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén	Log-Space Polynomial End-to-End Communication (Abstract).	PODC	1995	DBLP BibTeX RDF
13	Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén	Log-space polynomial end-to-end communication.	STOC	1995	DBLP DOI BibTeX RDF
13	Carme Àlvarez, Birgit Jenner	A Very Hard log-Space Counting Class.	Theor. Comput. Sci.	1993	DBLP DOI BibTeX RDF
13	Maria J. Serna	Approximating Linear Programming is Log-Space Complete for P.	Inf. Process. Lett.	1991	DBLP DOI BibTeX RDF
13	Seinosuke Toda	Positive Relativizations for Log Space Computability.	Theor. Comput. Sci.	1990	DBLP DOI BibTeX RDF
13	Carme Àlvarez, Birgit Jenner	A Very Hard Log Space Counting Class.	SCT	1990	DBLP DOI BibTeX RDF
13	Lefteris M. Kirousis, Paul G. Spirakis	Probabilistic Log-Space Reductions and Problems Probabilistically Hard for P.	SWAT	1988	DBLP DOI BibTeX RDF
13	Shigeki Iwata, Takumi Kasai	Simultaneous (Poly-Time, Log-Space) Lower Bounds.	Theor. Comput. Sci.	1987	DBLP DOI BibTeX RDF
13	Takumi Kasai, Shigeki Iwata	Gradually Intractable Problems and Nondeterministic Log-Space Lower Bounds.	Math. Syst. Theory	1985	DBLP DOI BibTeX RDF
13	Marek Ejsmont	On the log-space reducibility among array languages /preliminary version/.	Symposium on Computation Theory	1984	DBLP DOI BibTeX RDF
13	Walter J. Savitch	A Note on Relativized Log Space.	Math. Syst. Theory	1983	DBLP DOI BibTeX RDF
13	Leslie M. Goldschlager, Ralph A. Shaw, John Staples	The Maximum Flow Problem is Log Space Complete for P.	Theor. Comput. Sci.	1982	DBLP DOI BibTeX RDF
13	David P. Dobkin, Richard J. Lipton, Steven P. Reiss	Linear Programming is Log-Space Hard for P.	Inf. Process. Lett.	1979	DBLP DOI BibTeX RDF
13	Nancy A. Lynch	Log Space Machines with Multiple Oracle Tapes.	Theor. Comput. Sci.	1978	DBLP DOI BibTeX RDF
13	Nancy A. Lynch	Log Space Recognition and Translation of Parenthesis Languages.	J. ACM	1977	DBLP DOI BibTeX RDF
13	Leslie M. Goldschlager	The monotone and planar circuit value problems are log space complete for P.	SIGACT News	1977	DBLP DOI BibTeX RDF
13	Richard E. Ladner, Nancy A. Lynch	Relativization of Questions About Log Space Computability.	Math. Syst. Theory	1976	DBLP DOI BibTeX RDF
13	Richard E. Ladner	The circuit value problem is log space complete for P.	SIGACT News	1975	DBLP DOI BibTeX RDF
13	Richard J. Lipton, Nancy A. Lynch	A quantifier characterization for nondeterministic log space.	SIGACT News	1975	DBLP DOI BibTeX RDF
13	John Lind, Albert R. Meyer	A characterization of log-space computable functions.	SIGACT News	1973	DBLP DOI BibTeX RDF
12	Meena Mahajan, B. V. Raghavendra Rao	Small-Space Analogues of Valiant's Classes.	FCT	2009	DBLP DOI BibTeX RDF
12	Omer Reingold, Luca Trevisan, Salil P. Vadhan	Pseudorandom walks on regular digraphs and the RL vs. L problem.	STOC	2006	DBLP DOI BibTeX RDF	universal traversal sequence, zig-zag product, derandomization, expander graphs, mixing time, space-bounded computation
12	Jun Tarui, Seinosuke Toda	Some Observations on the Computational Complexity of Graph Accessibility Problem.	COCOON	1999	DBLP DOI BibTeX RDF
12	Thomas Zeugmann	Computing Large Polynomial Powers Very Fast in Parallel.	MFCS	1990	DBLP DOI BibTeX RDF
12	Michael Mñuk	A Div(n) Depth Boolean Circuit for Smooth Modular Inverse.	IMYCS	1990	DBLP DOI BibTeX RDF
10	Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk	Space Efficient Algorithms for Series-Parallel Graphs.	STACS	2001	DBLP DOI BibTeX RDF