Search results for "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
3	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
3	Martin Kummer	Degrees of Unsolvability in Abstract Complexity Theory.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
3	Kenneth W. Regan	The Topology of Provability in Complexity Theory.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Akitoshi Kawamura, Stephen A. Cook	Complexity theory for operators in analysis.	STOC	2010	DBLP DOI BibTeX RDF	higher-type complexity, second-order polynomials, computational complexity, computable analysis
2	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
2	Scott Aaronson, Avi Wigderson	Algebrization: a new barrier in complexity theory.	STOC	2008	DBLP DOI BibTeX RDF	communication complexity, oracles, arithmetization, interactive proofs, query complexity, low-degree polynomials
2	Kristina Zgodavova, Lubomir Lengyel, Ljudmil A. Golemanov	Contribution to the Research and Education of Innovation Engineering and New Product Development at the University.	Innovative Techniques in Instruction Technology, E-learning, E-assessment, and Education	2008	DBLP DOI BibTeX RDF	theory of mechatronics, process duality, innovation engineering, new mechatronic product development, complexity theory
2	Oded Goldreich	On Teaching the Basics of Complexity Theory.	Essays in Memory of Shimon Even	2006	DBLP DOI BibTeX RDF
2	Lars Kristiansen	Complexity-Theoretic Hierarchies.	CiE	2006	DBLP DOI BibTeX RDF	subrecursive classes, ?-calculi, Gödel’s T, types, Complexity theory
2	Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia	Linear FPT reductions and computational lower bounds.	STOC	2004	DBLP DOI BibTeX RDF	lower bound, complexity theory, NP-hard problems
2	Francis J. Mullany, Lester T. W. Ho, Louis G. Samuel, Holger Claussen	Self-deployment, Self-configuration: Critical Future Paradigms for Wireless Access Networks.	WAC	2004	DBLP DOI BibTeX RDF	Radio access networks, cognizant networks, ecology modeling, game theory, cellular automata, self-organization, complexity theory, auto-configuration, self-deployment
2	Yijia Chen, Jörg Flum, Martin Grohe	Bounded Nondeterminism and Alternation in Parameterized Complexity Theory.	IEEE Conference on Computational Complexity	2003	DBLP DOI BibTeX RDF
2	Luca Trevisan	Error-Correcting Codes in Complexity Theory.	CIAC	2003	DBLP DOI BibTeX RDF
2	Juraj Hromkovic, Georg Schnitger	Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes.	ICALP	2003	DBLP DOI BibTeX RDF	multicounter machines, randomization, nondeterminism, complexity theory, pushdown automata
2	Ernst W. Mayr	Complexity Theory and Algorithms.	Euro-Par	2002	DBLP DOI BibTeX RDF
2	Matthias Krause	On the Computational Power of Boolean Decision Lists.	STACS	2002	DBLP DOI BibTeX RDF	Boolean Complexity Theory, Lower Bounds, Learnability
2	Gianfranco Bilardi, Rainer Feldmann, Kieran T. Herley, Bruce M. Maggs	Topic 06: Complexity Theory and Algorithms.	Euro-Par	2001	DBLP DOI BibTeX RDF
2	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
2	Ahmad-Reza Sadeghi, Michael Steiner	Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference.	EUROCRYPT	2001	DBLP DOI BibTeX RDF	Cryptographic Assumptions, Square Exponent, Inverse Exponent, Discrete Logarithms, Complexity Theory, Diffie-Hellman, Generic Algorithms
2	Matthias Krause, Stefan Lucks	On the Minimal Hardware Complexity of Pseudorandom Function Generators.	STACS	2001	DBLP DOI BibTeX RDF	Boolean Complexity Theory, Computational Distinguishability, Cryptography, Pseudorandomness
2	Felipe Cucker	Solving polynomial systems: a complexity theory viewpoint.	ISSAC	2000	DBLP DOI BibTeX RDF
2	Bernard Chazelle	Irregularities of Distribution, Derandomization, and Complexity Theory.	FSTTCS	2000	DBLP DOI BibTeX RDF
2	Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer	Magic Functions.	FOCS	1999	DBLP DOI BibTeX RDF	interactive argument, magic function, selective decommitment, three-round protocol, cryptography, distributed computing, zero knowledge, complexity theory, signature scheme, commitment scheme
2	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
2	Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf	Quantum Lower Bounds by Polynomials.	FOCS	1998	DBLP DOI BibTeX RDF	Black-box computation, Decision trees, Quantum computation, Complexity theory
2	Daniel R. Simon	Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions?	EUROCRYPT	1998	DBLP DOI BibTeX RDF	cryptography, Hash functions, oracle, complexity theory
2	Heribert Vollmer	A Generalized Quantifier Concept in Computational Complexity Theory.	ESSLLI	1997	DBLP DOI BibTeX RDF
2	Jin-yi Cai, D. Sivakumar, Martin Strauss	Constant Depth Circuits and the Lutz Hypothesis.	FOCS	1997	DBLP DOI BibTeX RDF	Lutz hypothesis, Exponential Time, constant-depth, nearly exponential-size circuits, circuit complexity theory, computational complexity, pseudorandom generators, complexity classes, NP, constant depth circuits
2	Shafi Goldwasser	New Directions in Cryptography: Twenty Some Years Later.	FOCS	1997	DBLP DOI BibTeX RDF	probabilistic proof systems, cryptography, cryptography, complexity theory, interactive proof systems, pseudo random number generation
2	Christos H. Papadimitriou	The Complexity of Knowledge Representation. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	computational complexity, complexity, artificial intelligence, artificial intelligence, knowledge representation, knowledge representation, complexity theory, common-sense reasoning, common-sense reasoning
2	Stephen A. Fenner	Inverting the Turing Jump in Complexity Theory.	Structure in Complexity Theory Conference	1995	DBLP BibTeX RDF
2	Kenneth W. Regan	On Superlinear Lower Bounds in Complexity Theory.	Structure in Complexity Theory Conference	1995	DBLP BibTeX RDF
2	Benoit Dubuc, Steven W. Zucker	Indexing Visual Representations through the Complexity Map. (PDF / PS)	ICCV	1995	DBLP DOI BibTeX RDF	visual representations indexing, complexity map, Hausdorff space, countability properties, formal complexity theory, computer vision, computational vision, computational complexity, visual databases, differential geometry, differential geometry, perceptual grouping
2	Pavel Pudlák	Complexity Theory and Genetics.	Structure in Complexity Theory Conference	1994	DBLP BibTeX RDF
2	Klaus Ambos-Spies, Steven Homer, Uwe Schöning (eds.)	Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992	Complexity Theory: Current Research	1993	DBLP BibTeX RDF
2	Tibor Hegedüs	Can Complexity Theory Benefit from Learning Theory?	ECML	1993	DBLP DOI BibTeX RDF
2	Ronald V. Book	Relativizations of the P =?NP and other Problems: Some Developments in Structural Complexity Theory.	ISAAC	1992	DBLP DOI BibTeX RDF
2	André Berthiaume, Gilles Brassard	The Quantum Challenge to Structural Complexity Theory.	Structure in Complexity Theory Conference	1992	DBLP BibTeX RDF
2	Vikraman Arvind, Yenjo Han, Lane A. Hemachandra, Johannes Köbler, Antoni Lozano, Martin Mundhenk, Mitsunori Ogiwara, Uwe Schöning, Riccardo Silvestri, Thomas Thierauf	Reductions to Sets of Low Information Content.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Christoph Meinel, Stephan Waack	Upper and Lower Bounds for Certain Graph Accessibility Problems on Bounded Alternating omega-Branching Programs.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	John Tromp, Peter van Emde Boas	Associative Storage Modification Machines.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Jin-yi Cai, Lane A. Hemachandra, Jozef Vyskoc	Promise Problems and Guarded Access to Unambiguous Computation.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Ronald V. Book	Additional Queries and Algorithmically Random Languages.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Antoni Lozano, Jacobo Torán	On the Non-Uniform Complexity of the Graph Isomorphism Problem.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Harry Buhrman, Edith Spaan, Leen Torenvliet	Bounded Reductions.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Jay Belanger, Jie Wang	On Average P vs. Average NP.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Rodney G. Downey, Michael R. Fellows	Fixed Parameter Tractability and Completeness.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Anne Condon	The Complexity of Space Boundes Interactive Proof Systems.	Complexity Theory: Current Research	1992	DBLP BibTeX RDF
2	Mitsunori Ogiwara, Lane A. Hemachandra	A Complexity Theory for Feasible Closure Properties.	Structure in Complexity Theory Conference	1991	DBLP BibTeX RDF
2	Alan L. Selman	One-Way Functions in Complexity Theory.	MFCS	1990	DBLP DOI BibTeX RDF
2	Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi	Structural Complexity Theory: recent Surprises.	SWAT	1990	DBLP DOI BibTeX RDF
2	George Cybenko	Complexity Theory of Neural Networks and Classification Problems.	EURASIP Workshop	1990	DBLP DOI BibTeX RDF
2	Akshar Bharati, Rajeev Sangal, Vineet Chaitanya	Natural Language Processing, Complexity Theory and Logic (Extended Abstract).	FSTTCS	1990	DBLP DOI BibTeX RDF
2	Juris Hartmanis	New Developments in Structural Complexity Theory.	ICALP	1988	DBLP DOI BibTeX RDF
2	Alan L. Selman (eds.)	Structure in Complexity Theory, Proceedings of the Conference hold at the University of California, Berkeley, California, June 2-5, 1986	Structure in Complexity Theory Conference	1986	DBLP BibTeX RDF
2	Anne Condon, Richard E. Ladner	Probabilistic Game Automata.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Carol Tretkoff	Bounded Oracles and Complexity Classes Inside Linear Space.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Samuel R. Buss	The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	David A. Russo	Optimal Approximations of Complete Sets.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Ker-I Ko, Timothy J. Long, Ding-Zhu Du	A Note on One- Way Functions and Polynomial Time Isomorphisms.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Martin Dietzfelbinger, Wolfgang Maass	two Lower Bound Arguments with "Inaccessible" Numbers.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Ker-I Ko, Pekka Orponen, Uwe Schöning, Osamu Watanabe	What Is a Hard Instance of a Computational Problem?.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Eric Allender	The Complexity of Sparse Sets in P.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Ian Parberry, Georg Schnitger	Parallel Computation with Threshold Functions.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Christopher B. Wilson	Parallel Computation and the NC Hierarchy Relativized.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Mark W. Krentel	The Complexity of Optimization Problems.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Klaus Ambos-Spies	Randomness, Relativizations, and Polynomial Reducibilities.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Jin-yi Cai, Lane A. Hemachandra	The Boolean Hierarchy: Hardware over NP.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Ravi B. Boppana, J. C. Lagarias	One- Way Functions and Circuit Complexity.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Wolfgang Maass, Georg Schnitger	An Optimal Lower Bound for Turing Machines with One Work Tape and a Two- way Input Tape.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	James F. Lynch	A Depth- Size Tradeoff for Boolean Circuits with Unbounded Fan- In.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Leen Torenvliet, Peter van Emde Boas	Diagonalisation methods in a polynomial setting.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Dung T. Huynh	Resource- Bounded Kolmogorov Complexity of Hard Languages.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	José L. Balcázar, Josep Díaz, Joaquim Gabarró	On Non- uniform Polynomial Space.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Eric Allender	Isomorphisms and 1-L Reductions.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Peter Clote, Gaisi Takeuti	Exponential Time and Bounded Arithmetic.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Michael Sipser	Expanders, Randomness, or Time versus Space.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Stathis Zachos	Probabilistic Quantifiers, Adversaries, and Complexity Classes: An Overview.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Ming Li, Luc Longpré, Paul M. B. Vitányi	The Power of the Queue.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Ken McAloon	Separation Results for Bounded Alternation.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Jin-yi Cai	With Probability One, A Random Oracle Separates PSPACE from the Polynomial- Time Hierarchy.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Jonathan F. Buss	Relativized Alternation.	Structure in Complexity Theory Conference	1986	DBLP DOI BibTeX RDF
2	Sven Skyum, Leslie G. Valiant	A Complexity Theory Based on Boolean Algebra	J. ACM	1985	DBLP DOI BibTeX RDF
2	Michael Sipser	A Topological View of Some Problems in Complexity Theory.	MFCS	1984	DBLP DOI BibTeX RDF
1	Theodore Zamenopoulos	A complexity theory of design intentionality.	AI EDAM	2012	DBLP DOI BibTeX RDF
1	Martin Ziegler	Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra.	Ann. Pure Appl. Logic	2012	DBLP DOI BibTeX RDF
1	Oded Goldreich	Invitation to complexity theory.	ACM Crossroads	2012	DBLP DOI BibTeX RDF
1	Harlan Kadish, J. M. Landsberg	Padded polynomials, their cousins, and geometric complexity theory	CoRR	2012	DBLP BibTeX RDF
1	Markus Bläser, Bodo Manthey	Smoothed Complexity Theory	CoRR	2012	DBLP BibTeX RDF
1	Lane A. Hemaspaandra	SIGACT news complexity theory column 73.	SIGACT News	2012	DBLP DOI BibTeX RDF
1	Kord Eickmeyer	Randomness in complexity theory and logics.		2011	RDF
1	Sam Buss, Yijia Chen, Jörg Flum, Sy-David Friedman, Moritz Müller	Strong isomorphism reductions in complexity theory.	J. Symb. Log.	2011	DBLP BibTeX RDF
1	Sungho Lee	Public Management and Complexity Theory. Richer Decision-Making in Public Services (Routledge Critical Studies in Public Management) by Mary Lee Rhodes, Joanne Murphy, Jenny Muir and John A. Murray.	J. Artificial Societies and Social Simulation	2011	DBLP BibTeX RDF
1	Ketan Mulmuley	On P vs. NP and geometric complexity theory: Dedicated to Sri Ramakrishna.	J. ACM	2011	DBLP DOI BibTeX RDF
1	Benjamin Doerr, Carola Winzen	Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity	CoRR	2011	DBLP BibTeX RDF
1	Kord Eickmeyer, Martin Grohe	Randomisation and Derandomisation in Descriptive Complexity Theory	Logical Methods in Computer Science	2011	DBLP DOI BibTeX RDF
1	Lane A. Hemaspaandra	SIGACT news complexity theory column 71.	SIGACT News	2011	DBLP DOI BibTeX RDF
1	Lane A. Hemaspaandra	SIGACT news complexity theory column 72.	SIGACT News	2011	DBLP DOI BibTeX RDF
1	Lane A. Hemaspaandra	SIGACT news complexity theory column 69.	SIGACT News	2011	DBLP DOI BibTeX RDF