Search results for "Reducibility"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
174	Yevgeniy Dodis, Silvio Micali	Parallel Reducibility for Information-Theoretically Secure Computation.	CRYPTO	2000	DBLP DOI BibTeX RDF
90	Xizhong Zheng, Robert Rettinger	On the Extensions of Solovay-Reducibility..	COCOON	2004	DBLP DOI BibTeX RDF
84	Roland Sh. Omanadze, Andrea Sorbi	Strong Enumeration Reducibilities.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 03D30
73	Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik	On Coherence, Random-self-reducibility, and Self-correction.	CCC	1996	DBLP DOI BibTeX RDF	self-correctability, random-self-reducibility, polynomial advice, adaptive versus nonadaptive oracle machines, Computational complexity, coherence, Kolmogorov complexity
66	Robert Rettinger, Xizhong Zheng	Solovay Reducibility on D-c.e Real Numbers.	COCOON	2005	DBLP DOI BibTeX RDF
66	Rodney G. Downey, Denis R. Hirschfeldt, Geoffrey LaForte	Randomness and Reducibility.	MFCS	2001	DBLP DOI BibTeX RDF
66	Christoph Meinel, Anna Slobodová	A Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams.	STACS	1997	DBLP DOI BibTeX RDF
66	Emmanuel Kounalis	Testing for Inductive (Co)-Reducibility.	CAAP	1990	DBLP DOI BibTeX RDF	Proof by consistency, Ground terms in normal form, Term rewriting systems, Test Sets, Equations
61	Eric Allender, Michal Koucký 0001	Amplifying Lower Bounds by Means of Self-Reducibility.	CCC	2008	DBLP DOI BibTeX RDF	self-reducibility, lower bounds, circuit complexity
60	Wolfgang Merkle, Frank Stephan 0001	On C-Degrees, H-Degrees and T-Degrees.	CCC	2007	DBLP DOI BibTeX RDF
60	Steven Homer	Minimal degrees for polynomial reducibilities.	J. ACM	1987	DBLP DOI BibTeX RDF
54	Randy Goebel	Folk Reducibility and AI-Complete Problems.	KI	2008	DBLP DOI BibTeX RDF
54	Charles M. Harris	Enumeration Reducibility with Polynomial Time Bounds.	CiE	2006	DBLP DOI BibTeX RDF
54	Sam Lindley, Ian Stark	Reducibility and TT-Lifting for Computation Types.	TLCA	2005	DBLP DOI BibTeX RDF
54	Charles M. Harris	Symmetric Enumeration Reducibility.	CiE	2005	DBLP DOI BibTeX RDF
54	Joan Feigenbaum, Martin Strauss 0001	An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract).	STACS	1997	DBLP DOI BibTeX RDF
49	Victor L. Selivanov	Wadge Reducibility and Infinite Computations.	Math. Comput. Sci.	2008	DBLP DOI BibTeX RDF	Wadge reducibility, Baire space, Baire domain, ?-language, k-partition, complexity, topology, computability, automaton
49	Mark Burgin	Universality, Reducibility, and Completeness.	MCU	2007	DBLP DOI BibTeX RDF	problem completeness, algorithm, computability, reducibility, universal, computing power, problem hardness
49	Dieter Spreen	Strong reducibility of partial numberings.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF	Partial numberings, Total numberings, Complete numberings, Degree structure, Reducibility
48	Andrea Sorbi	Strong Positive Reducibilities.	TAMC	2009	DBLP DOI BibTeX RDF
48	Christian Glaßer, Stephen D. Travers, Klaus W. Wagner	Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy.	Developments in Language Theory	2006	DBLP DOI BibTeX RDF
48	Kouichi Sakurai, Hiroki Shizuya	Relationships Among the Computational Powers of Breaking Discrete Log Cryptosystems.	EUROCRYPT	1995	DBLP DOI BibTeX RDF
44	David Jao, Stephen D. Miller, Ramarathnam Venkatesan	Do All Elliptic Curves of the Same Order Have the Same Difficulty of Discrete Log?	ASIACRYPT	2005	DBLP DOI BibTeX RDF	random reducibility, modular forms, L-functions, generalized Riemann hypothesis, elliptic curves, expanders, Ramanujan graphs, isogenies, rapid mixing, discrete log
44	André Große, Jörg Rothe, Gerd Wechsung	Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.	ICTCS	2001	DBLP DOI BibTeX RDF	complexity of smallest solutions, self-reducibility, graph colorability, Hamiltonian cycles, graph isomorphisms, partial solutions
42	Colin Riba	Union of Reducibility Candidates for Orthogonal Constructor Rewriting.	CiE	2008	DBLP DOI BibTeX RDF
42	Sergey M. Dudakov	Isolation and Reducibility Properties and the Collapse Result.	CSR	2006	DBLP DOI BibTeX RDF
42	Domenico Lembo, Riccardo Rosati 0001, Marco Ruzzi	On the First-Order Reducibility of Unions of Conjunctive Queries over Inconsistent Databases.	EDBT Workshops	2006	DBLP DOI BibTeX RDF
42	Victor L. Selivanov, Klaus W. Wagner	A Reducibility for the Dot-Depth Hierarchy.	MFCS	2004	DBLP DOI BibTeX RDF
42	Kouichi Hirata, Hiroshi Sakamoto	Prediction-Preserving Reducibility with Membership Queries on Formal Languages.	FCT	2001	DBLP DOI BibTeX RDF	prediction-preserving reduction with membership queries, prediction with membership queries, pattern languages, learning theory, context-free grammars, grammatical inference
42	Heribert Vollmer	On Different Reducibility Notions for Function Classes.	STACS	1994	DBLP DOI BibTeX RDF
37	Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky	Reducibility and Completeness in Multi-Party Private Computations	FOCS	1994	DBLP DOI BibTeX RDF	Oblivious Transfer protocol, multi-party private computations, n-privacy, Boolean functions, completeness, reducibility, black-box, multi-party protocols
37	Stavros S. Cosmadakis	Logical Reducibility and Monadic NP	FOCS	1993	DBLP DOI BibTeX RDF	syntactically restricted first-order reductions, logical reducibility, monadic NP, polynomial-time many-one reductions, directed reachability, encodings, first-order logic, NP-complete problems, relational structures
36	Sanjay Jain 0001, Frank Stephan 0001	Mitotic Classes.	COLT	2007	DBLP DOI BibTeX RDF
36	Isabelle Gnaedig, Hélène Kirchner	Computing constructor forms with non terminating rewrite programs.	PPDP	2006	DBLP DOI BibTeX RDF	constructor, abstraction, termination, narrowing, ordering constraint, sufficient completeness
36	Klaus Ambos-Spies	Problems with Cannot Be Reduced to Any Proper Subproblems.	MFCS	2003	DBLP DOI BibTeX RDF
36	Dieter Hofbauer, Maria Huber	Test Sets for the Universal and Existential Closure of Regular Tree Languages.	RTA	1999	DBLP DOI BibTeX RDF
36	Vikraman Arvind, Johannes Köbler, Martin Mundhenk	Hausdorff Reductions to Sparse Sets and to Sets of High Information Content.	MFCS	1993	DBLP DOI BibTeX RDF
36	Reinhard Bündgen, Wolfgang Küchlin	Computing Ground Reducability and Inductively Complete Positions.	RTA	1989	DBLP DOI BibTeX RDF
35	Yannick Forster 0002, Felix Jahn	Constructive and Synthetic Reducibility Degrees: Post's Problem for Many-One and Truth-Table Reducibility in Coq.	CSL	2023	DBLP DOI BibTeX RDF
35	Yuefei Sui	A New Reducibility between Turing- and wtt-Reducibility.	Math. Log. Q.	1994	DBLP DOI BibTeX RDF
35	Timothy J. Long	On gamma-Reducibility Versus Polynomial Time Many-One Reducibility.	Theor. Comput. Sci.	1981	DBLP DOI BibTeX RDF
35	Timothy J. Long	On gamma-Reducibility versus Polynomial Time Many-One Reducibility (Extended Abstract)	STOC	1979	DBLP DOI BibTeX RDF
35	Herbert Fleischner	On the Equivalence of Mealy-Type and Moore-Type Automata and a Relation between Reducibility and Moore-Reducibility.	J. Comput. Syst. Sci.	1977	DBLP DOI BibTeX RDF
32	Roberto M. Amadio	On Stratified Regions.	APLAS	2009	DBLP DOI BibTeX RDF	Types and effects, Reducibility candidates, Termination
32	Malgorzata Biernacka, Dariusz Biernacki	Context-based proofs of termination for typed delimited-control operators.	PPDP	2009	DBLP DOI BibTeX RDF	reducibility predicates, type system, continuation-passing style, delimited continuations, reduction semantics
32	Victor L. Selivanov	Fine Hierarchy of Regular Aperiodic omega -Languages.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF	acceptor, regular aperiodic ?-language, Wagner hierarchy, reducibility, Automaton, transducer
32	Gianna M. Del Corso, Antonio Gulli, Francesco Romani	Fast PageRank Computation Via a Sparse Linear System (Extended Abstract).	WAW	2004	DBLP DOI BibTeX RDF	Web Matrix Reducibility and Permutation, Search Engines, Link Analysis
32	Victor L. Selivanov	Wadge Degrees of omega-Languages of Deterministic Turing Machines.	STACS	2003	DBLP DOI BibTeX RDF	Wadge degree, $omega$-language, Cantor space, set-theoretic operation, hierarchy, reducibility
32	Paliath Narendran, Michaël Rusinowitch	The Theory of Total Unary RPO Is Decidable.	Computational Logic	2000	DBLP DOI BibTeX RDF	recursive path ordering, ground reducibility, ordered rewriting, tree automata, first-order theory
32	Helena Handschuh, Yiannis Tsiounis, Moti Yung	Decision Oracles are Equivalent to Matching Oracles.	Public Key Cryptography	1999	DBLP DOI BibTeX RDF	Diffie-Hellman variants, randomized reductions, uniform reductions, homomorphic encryption functions (ElGamal, Goldwasser-Micali, Okamoto-Uchiyama, Naccache-Stern), random self-reducibility, universal malleability, public-key encryption, decision problems, matching problems
32	Adel Bouhoula, Jean-Pierre Jouannaud	Automata-Driven Automated Induction.	LICS	1997	DBLP DOI BibTeX RDF	automata-driven automated induction, inductive theorem proving, first-order functions, finitely many unary membership predicates, rational subsets, ground reducibility, inductive prover, theorem proving, tree automata, Horn Clauses, proof obligations
32	Rodney G. Downey, André Nies	Undecidability Results for Low Complexity Degree Structures.	CCC	1997	DBLP DOI BibTeX RDF	undecidability results, low complexity degree structures, EXPTIME degrees, polynomial time Turing, many-one reducibility, coding method, ideal lattices, hyper-polynomial time classes, Boolean algebra, Boolean algebras
30	Colin Riba	On the Values of Reducibility Candidates.	TLCA	2009	DBLP DOI BibTeX RDF
30	Colin Riba	On the Stability by Union of Reducibility Candidates.	FoSSaCS	2007	DBLP DOI BibTeX RDF
30	Kai-Sheng Lu, Xiao-Yu Feng, Guo-Zhang Gao	The separability, reducibility and controllability of RLCM networks over F(z).	ISCAS (1)	2005	DBLP DOI BibTeX RDF
30	Tsuyoshi Iwagaki, Satoshi Ohtake, Hideo Fujiwara	Reducibility of Sequential Test Generation to Combinational Test Generation for Several Delay Fault Models.	Asian Test Symposium	2003	DBLP DOI BibTeX RDF
30	Pavel Pudlák	On Reducibility and Symmetry of Disjoint NP-Pairs.	MFCS	2001	DBLP DOI BibTeX RDF
30	Erich Grädel, Marc Spielmann	Logspace Reducibility via Abstract State Machines.	World Congress on Formal Methods	1999	DBLP DOI BibTeX RDF
30	László Babai, Sophie Laplante	Stronger Separations for Random-Self-Reducibility, Rounds, and Advice.	CCC	1999	DBLP DOI BibTeX RDF
30	Hubert Comon, Florent Jacquemard	Ground Reducibility is EXPTIME-Complete.	LICS	1997	DBLP DOI BibTeX RDF
30	Michael F. Singer	Testing reducibility of linear differential operators: A group theoretic perspective.	Appl. Algebra Eng. Commun. Comput.	1996	DBLP DOI BibTeX RDF	Linear differential operator, Berlekamp algorithm, Differential Galois theory, Factorization
30	Hubert Comon, Florent Jacquemard	Ground Reducibility and Automata with Disequality Constraints.	STACS	1994	DBLP DOI BibTeX RDF
30	Karol Habart	Randomness and Turing Reducibility Restraints.	CSL	1990	DBLP DOI BibTeX RDF
24	Shuji Isobe, Eisuke Koizumi, Yuji Nishigaki, Hiroki Shizuya	On the Complexity of Computing Discrete Logarithms over Algebraic Tori.	CANS	2009	DBLP DOI BibTeX RDF	algebraic tori, order certified discrete logarithms, Turing reduction
24	Russell Impagliazzo, Nathan Segerlind	Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	Modular counting axioms, Nullstellensatz refutations, propositional proof complexity
24	Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang	Redundancy in Complete Sets.	STACS	2006	DBLP DOI BibTeX RDF
24	George Barmpalias	Computably Enumerable Sets in the Solovay and the Strong Weak Truth Table Degrees.	CiE	2005	DBLP DOI BibTeX RDF
24	Marcus Schaefer 0001, Frank Stephan 0001	Strong Reductions and Immunity for Exponential Time.	STACS	2003	DBLP DOI BibTeX RDF	hardness for exponential time, polynomial time reducibilities, Computational and structural complexity
24	Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 0001	The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.	Theory Comput. Syst.	2002	DBLP DOI BibTeX RDF
24	Peter A. Fejer, Richard A. Shore	Every incomplete computably enumerable truth-table degree is branching.	Arch. Math. Log.	2001	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03D30, 03D25
24	Rodney G. Downey, Denis R. Hirschfeldt, André Nies	Randomness, Computability, and Density.	STACS	2001	DBLP DOI BibTeX RDF
24	Massimiliano Goldwurm, Beatrice Palano, Massimo Santini 0001	On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages.	STACS	2001	DBLP DOI BibTeX RDF	Uniform random generation, ambiguous context-free languages, auxiliary pushdown automata, circuit complexity
24	Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe 0001	On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems.	STACS	2001	DBLP DOI BibTeX RDF
24	Jens Lechtenbörger, Gottfried Vossen	On Herbrand Semantics and Conflict Serializability of Read-Write Transactions.	PODS	2000	DBLP DOI BibTeX RDF
24	Jochen Meßner	On Optimal Algorithms and Optimal Proof Systems.	STACS	1999	DBLP DOI BibTeX RDF
24	Kouichi Sakurai, Hiroki Shizuya	A Structural Comparison of the Computational Difficulty of Breaking Discrete Log Cryptosystems.	J. Cryptol.	1998	DBLP DOI BibTeX RDF	Computational number theory, Computational number theory, Securi, Security, Randomness, Randomness, Public-key cryptography, Public-key cryptography, Elliptic curves, Elliptic curves, Key exchange, Key exchange, Discrete logarithm, Discrete logarithm, Key words, Cryptosystem, Cryptosystem
24	Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng	A Comparison of Weak Completeness Notions.	CCC	1996	DBLP DOI BibTeX RDF	Weak Completeness, Measure, Genericity, Completeness
24	Rachid Guerraoui	Revistiting the Relationship Between Non-Blocking Atomic Commitment and Consensus.	WDAG	1995	DBLP DOI BibTeX RDF
24	Martin Mundhenk	On Self-Reducible Sets of Low Information Content.	CIAC	1994	DBLP DOI BibTeX RDF
24	Mitsunori Ogiwara	NC^k(NP) = AC^(k-1)(NP).	STACS	1994	DBLP DOI BibTeX RDF
24	Pierluigi Crescenzi, Luca Trevisan	On Approximation Scheme Preserving Reducability and Its Applications.	FSTTCS	1994	DBLP DOI BibTeX RDF
24	Jean H. Gallier	Proving Properties of Typed Lambda Terms: Realizability, Covers, and Sheaves (Abstract).	RTA	1993	DBLP DOI BibTeX RDF
24	Osamu Watanabe 0001, Seinosuke Toda	Structural Analyses on the Complexity of Inverting Functions.	SIGAL International Symposium on Algorithms	1990	DBLP DOI BibTeX RDF
24	Donald Beaver, Joan Feigenbaum, Joe Kilian, Phillip Rogaway	Security with Low Communication Overhead.	CRYPTO	1990	DBLP DOI BibTeX RDF
24	Lyle Ramshaw	Eliminating go to's while preserving program structure.	J. ACM	1988	DBLP DOI BibTeX RDF
24	Klaus Ambos-Spies	On the Relative Complexity of Subproblems of Intractable Problems.	STACS	1985	DBLP DOI BibTeX RDF
24	Johann A. Makowsky	Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory. (Errata: ICALP 1981: 551)	ICALP	1980	DBLP DOI BibTeX RDF
20	Thomas Ehrhard	A Finiteness Structure on Resource Terms.	LICS	2010	DBLP DOI BibTeX RDF	finiteness spaces, algebraic system F, linear logic, lambda-calculus, reducibility, denotational semantics
20	Harry Buhrman, Lance Fortnow, Michal Koucký 0001, Bruno Loff	Derandomizing from Random Strings.	CCC	2010	DBLP DOI BibTeX RDF	Truth-table Reducibility, Kolmogorov Complexity, Derandomization
20	Sanatan Rai, George L. Vairaktarakis	NP-complete Problems and Proof Methodology.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Polynomial time reduction, strong NP-completeness, ordinary NP-completeness, Computational complexity, Reducibility, NP-complete problem, NP-hard problem
20	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
20	Chun-Yuan Chiu, Yu-Liang Kuo, Eric Hsiao-Kuang Wu, Gen-Huey Chen	Bandwidth-Constrained Routing Problem in Wireless Ad Hoc Networks.	IEEE Trans. Parallel Distributed Syst.	2008	DBLP DOI BibTeX RDF	reducibility and completeness, routing protocols, Algorithm/protocol design and analysis, mobile communication systems
20	Victor L. Selivanov, Klaus W. Wagner	Complexity of Aperiodicity for Topological Properties of Regular omega-Languages.	CiE	2008	DBLP DOI BibTeX RDF	Regular aperiodic ?-language, Wadge reducibility, aperiodic automaton, deterministic Muller automaton, nondeterministic Büchi automaton, monadic second-order formula
20	Bruce M. Kapron, Lior Malka, Srinivasan Venkatesh 0001	A Characterization of Non-interactive Instance-Dependent Commitment-Schemes (NIC).	ICALP	2007	DBLP DOI BibTeX RDF	random self-reducibility, zero-knowledge, commitment-schemes
20	Takayuki Nagoya, Seinosuke Toda	Relating Complete and Partial Solution for Problems Similar to Graph Automorphism.	MFCS	2007	DBLP DOI BibTeX RDF	graph auto- morphism, Computational complexity, reducibility, partial solution
20	Victor L. Selivanov	A Useful Undecidable Theory.	CiE	2007	DBLP DOI BibTeX RDF	discrete weak semilattice, partition, theory, reducibility, undecidability, Semilattice
20	V. Baleva	The jump operation for structure degrees.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF	Structure degrees, Enumeration degrees, Degrees of structures, Reducibility, Degree, Jump
20	Riccardo Camerlo	Universality of Embeddability Relations for Coloured Total Orders.	Order	2005	DBLP DOI BibTeX RDF	coloured total order, Borel reducibility, ?1 1-universality, dendrite
20	Jacob van der Woude	A Characterization of the Eigenvalue of a General (Min, Max, +)-System.	Discret. Event Dyn. Syst.	2001	DBLP DOI BibTeX RDF	(min,max,+)-systems, convergence of iterations, eigenvalue, reducibility
20	Hideo Fujiwara	A New Class of Sequential Circuits with Combinational Test Generation Complexity.	IEEE Trans. Computers	2000	DBLP DOI BibTeX RDF	complexity, test generation, design for testability, sequential circuits, reducibility, partial scan, Balanced structure