Search results for "computational complexity theory"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Jin-yi Cai, Hong Zhu	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
2	Heribert Vollmer	A Generalized Quantifier Concept in Computational Complexity Theory.	ESSLLI	1997	DBLP DOI BibTeX RDF
1	Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy	The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory.	J. Comput. Syst. Sci.	2011	DBLP DOI BibTeX RDF
1	Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy	The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory.	Electronic Colloquium on Computational Complexity (ECCC)	2009	DBLP BibTeX RDF
1	Hamilton Emmons, Sanatan Rai	Computational Complexity Theory.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Recognition problem, Time complexity function, Nondeterministic polynomial algorithm, Computational complexity, Combinatorial optimization, Reducibility, NP-complete problem, Efficient algorithm, Complexity theory, NP-hard problem, Polynomial algorithm, Decision problem, Exponential algorithm
1	Mario J. Pérez-Jiménez	A Computational Complexity Theory in Membrane Computing.	Workshop on Membrane Computing	2009	DBLP DOI BibTeX RDF
1	Kesheng Wu, Ekow J. Otoo, Kenji Suzuki	Optimizing two-pass connected-component labeling algorithms.	Pattern Anal. Appl.	2009	DBLP DOI BibTeX RDF	Union-find algorithm, Optimization, Decision tree, Equivalence relation, Connected-component labeling
1	Eric Allender	Computational Complexity Theory.	Wiley Encyclopedia of Computer Science and Engineering	2008	DBLP DOI BibTeX RDF
1	Damian W. I. Rouson, Robert Rosenberg, Xiaofeng Xu, Irene Moulitsas, Stavros C. Kassinos	A grid-free abstraction of the Navier-Stokes equations in Fortran 95/2003.	ACM Trans. Math. Softw.	2008	DBLP DOI BibTeX RDF	coordinate-free programming, grid-free programming, complexity, Fortran, scientific computing, computational fluid dynamics, Navier-Stokes equations
1	Shujing Wang, Yan Zhang	A Logic Programming Based Framework for Security Protocol Verification.	ISMIS	2008	DBLP DOI BibTeX RDF
1	Venkatesan Guruswami	List Decoding and Pseudorandom Constructions.	AAECC	2007	DBLP DOI BibTeX RDF
1	Francesco Gagliardi	Some Issues About Cognitive Modelling and Functionalism.	AI*IA	2007	DBLP DOI BibTeX RDF	Mesoscopic Functionalism, Empirical Underdetermination, Scientific Pluralism, Heuristics, Cognitive Modelling
1	Wolfgang Maass	Liquid Computing.	CiE	2007	DBLP DOI BibTeX RDF
1	Rahul Tripathi	The 1-Versus-2 Queries Problem Revisited.	ISAAC	2007	DBLP DOI BibTeX RDF
1	Gavriel Segre	Some elementary rigorous remark about the replica formalism in the Statistical Physics' approach to threshold phenomena in Computational Complexity Theory	CoRR	2006	DBLP BibTeX RDF
1	Tarsem S. Purewal Jr.	Revisiting a limit on efficient quantum computation.	ACM Southeast Regional Conference	2006	DBLP DOI BibTeX RDF	computational complexity, quantum computing
1	Kevin W. Hamlen, J. Gregory Morrisett, Fred B. Schneider	Computability classes for enforcement mechanisms.	ACM Trans. Program. Lang. Syst.	2006	DBLP DOI BibTeX RDF	Program rewriting, reference monitors, security automata, execution monitoring, inlined reference monitoring, edit automata
1	Jan Krajícek	Forcing with Random Variables and Proof Complexity.	CiE	2006	DBLP DOI BibTeX RDF
1	Lance Fortnow, Adam R. Klivans	Efficient Learning Algorithms Yield Circuit Lower Bounds.	COLT	2006	DBLP DOI BibTeX RDF
1	Akinori Kawachi, Tomoyuki Yamakami	Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding.	ICALP	2006	DBLP DOI BibTeX RDF
1	John C. Mitchell	Security analysis of network protocols: logical and computational methods.	PPDP	2005	DBLP DOI BibTeX RDF	security, network, protocols
1	Harumichi Nishimura, Tomoyuki Yamakami	An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract).	MFCS	2004	DBLP DOI BibTeX RDF	Algorithmic argument, nonadaptive query, quantum computation, query complexity, advice
1	Christian Cachin	Modeling Complexity in Secure Distributed Computing.	Future Directions in Distributed Computing	2003	DBLP DOI BibTeX RDF
1	Klaus Ambos-Spies, Edgar Busse	Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata.	DMTCS	2003	DBLP DOI BibTeX RDF
1	Liara Aparecida dos Santos Leal, Dalcidio Moraes Claudio, Laira Vieira Toscani, Paulo Blauth Menezes	A Categorical Approach to NP-Hard Optimization Problems.	EUROCAST	2003	DBLP DOI BibTeX RDF
1	Sabine Glesner	Program Checking with Certificates: Separating Correctness-Critical Code.	FME	2003	DBLP DOI BibTeX RDF	safety-scalability, real-scale applications, verification, validation, certificates, correctness, program checking
1	Madhav V. Marathe	Towards a Predictive Computational Complexity Theory.	ICALP	2002	DBLP DOI BibTeX RDF
1	Jörg Rothe	Some facets of complexity theory and cryptography: A five-lecture tutorial.	ACM Comput. Surv.	2002	DBLP DOI BibTeX RDF	public-key cryptography, Complexity theory, one-way functions, interactive proof systems, zero-knowledge protocols
1	Larry J. Stockmeyer, Dharmendra S. Modha	Links Between Complexity Theory and Constrained Block Coding. (PDF / PS)	IEEE Conference on Computational Complexity	2001	DBLP DOI BibTeX RDF
1	Jirí Wiedermann, Jan van Leeuwen	Emergence of a Super-Turing Computational Potential in Artificial Living Systems.	ECAL	2001	DBLP DOI BibTeX RDF
1	Liara Aparecida dos Santos Leal, Paulo Blauth Menezes, Dalcidio Moraes Claudio, Laira Vieira Toscani	Optimization Problems Categories.	EUROCAST	2001	DBLP DOI BibTeX RDF
1	John Watrous	On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes.	FOCS	1999	DBLP DOI BibTeX RDF	GapL functions, selective quantum processes, computational complexity theory, quantum computation, space-bounded computation, algebraic numbers
1	Heribert Vollmer	A Generalized Quantifier Concept in Computational Complexity Theory	CoRR	1998	DBLP BibTeX RDF
1	Daniel Leivant	A Characterization of NC by Tree Recurrence.	FOCS	1998	DBLP DOI BibTeX RDF
1	Heribert Vollmer, Klaus W. Wagner	Measure One Results in Computational Complexity Theory.	Advances in Algorithms, Languages, and Complexity	1997	DBLP BibTeX RDF
1	Thomas Schwentick	Padding and the Expressive Power of Existential Second-Order Logics.	CSL	1997	DBLP DOI BibTeX RDF
1	Iain A. Stewart	A Perspective on Lindström Quantifiers and Oracles.	ESSLLI	1997	DBLP DOI BibTeX RDF
1	Harry Buhrman, Lance Fortnow	Resource-Bounded Kolmogorov Complexity Revisited.	STACS	1997	DBLP DOI BibTeX RDF
1	Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich	The future of computational complexity theory: part II.	SIGACT News	1996	DBLP DOI BibTeX RDF
1	Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser	The future of computational complexity theory: part I.	SIGACT News	1996	DBLP DOI BibTeX RDF
1	Michael C. Loui	Computational Complexity Theory.	ACM Comput. Surv.	1996	DBLP DOI BibTeX RDF
1	Dieter van Melkebeek	Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	computational complexity theory, sparse hard set problem for P
1	Juris Hartmanis	On the Computing Paradigm and Computational Complexity.	MFCS	1995	DBLP DOI BibTeX RDF
1	Lance Fortnow	My Favorite Ten Complexity Theorems of the Past Decade.	FSTTCS	1994	DBLP DOI BibTeX RDF
1	Takashi Mihara, Tetsuro Nishino	Quantum Computation and NP-Complete Problems.	ISAAC	1994	DBLP DOI BibTeX RDF
1	Uwe Hartmann	On the Complexity of Learning in Classifier Systems.	PPSN	1994	DBLP DOI BibTeX RDF
1	Martin Beaudry, Pierre McKenzie, Denis Thérien	The Membership Problem in Aperiodic Transformation Monoids.	J. ACM	1992	DBLP DOI BibTeX RDF	aperiodic, membership, varieties, monoids
1	Tatsuaki Okamoto, Kouichi Sakurai, Hiroki Shizuya	How Intractable Is the Discrete Logarithm for a General Finite Group?	EUROCRYPT	1992	DBLP DOI BibTeX RDF
1	Joan Daemen	Limitations of the Even-Mansour Construction.	ASIACRYPT	1991	DBLP DOI BibTeX RDF
1	Hiroki Shizuya, Toshiya Itoh, Kouichi Sakurai	On the Complexity of Hyperelliptic Discrete Logarithm Problem.	EUROCRYPT	1991	DBLP DOI BibTeX RDF
1	Akshar Bharati, Rajeev Sangal, Vineet Chaitanya	Natural Language Processing, Complexity Theory and Logic (Extended Abstract).	FSTTCS	1990	DBLP DOI BibTeX RDF
1	William I. Gasarch, Lane A. Hemachandra, Albrecht Hoene	On Checking Versus Evaluation of Multiple Queries.	MFCS	1990	DBLP DOI BibTeX RDF