Search results for "self-reducibility"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
113	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
76	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
74	Joan Feigenbaum, Martin Strauss 0001	An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract).	STACS	1997	DBLP DOI BibTeX RDF
57	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
43	László Babai, Sophie Laplante	Stronger Separations for Random-Self-Reducibility, Rounds, and Advice.	CCC	1999	DBLP DOI BibTeX RDF
40	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
36	Martin Mundhenk	On Self-Reducible Sets of Low Information Content.	CIAC	1994	DBLP DOI BibTeX RDF
26	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
26	Pekka Orponen, Ker-I Ko, Uwe Schöning, Osamu Watanabe 0001	Instance Complexity.	J. ACM	1994	DBLP DOI BibTeX RDF	nonuniform complexity, paddability, self-reducibility, completeness, Kolmogorov complexity
25	Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik	On Coherence, Random-Self-Reducibility, and Self-Correction.	Comput. Complex.	1998	DBLP DOI BibTeX RDF
21	Prahladh Harsha, Daniel Mitropolsky, Alon Rosen	Downward Self-Reducibility in TFNP.	ITCS	2023	DBLP DOI BibTeX RDF
21	Prahladh Harsha, Daniel Mitropolsky, Alon Rosen	Downward Self-Reducibility in TFNP.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
21	Prahladh Harsha, Daniel Mitropolsky, Alon Rosen	Downward Self-Reducibility in TFNP.	CoRR	2022	DBLP DOI BibTeX RDF
21	Massimo Equi, Veli Mäkinen, Alexandru I. Tomescu	Conditional Indexing Lower Bounds Through Self-Reducibility.	CoRR	2020	DBLP BibTeX RDF
21	Tomoki Kawashima, Katsuyuki Takashima, Yusuke Aikawa, Tsuyoshi Takagi	An Efficient Authenticated Key Exchange from Random Self-Reducibility on CSIDH.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
21	Koen de Boer, Léo Ducas, Alice Pellet-Mary, Benjamin Wesolowski	Random Self-reducibility of Ideal-SVP via Arakelov Random Walks.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
21	Lane A. Hemaspaandra	The Power of Self-Reducibility: Selectivity, Information, and Approximation.	Complexity and Approximation	2020	DBLP DOI BibTeX RDF
21	Tomoki Kawashima, Katsuyuki Takashima, Yusuke Aikawa, Tsuyoshi Takagi	An Efficient Authenticated Key Exchange from Random Self-reducibility on CSIDH.	ICISC	2020	DBLP DOI BibTeX RDF
21	Koen de Boer, Léo Ducas, Alice Pellet-Mary, Benjamin Wesolowski	Random Self-reducibility of Ideal-SVP via Arakelov Random Walks.	CRYPTO (2)	2020	DBLP DOI BibTeX RDF
21	Lane A. Hemaspaandra	The Power of Self-Reducibility: Selectivity, Information, and Approximation.	CoRR	2019	DBLP BibTeX RDF
21	Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein	Information Lower Bounds via Self-Reducibility.	Theory Comput. Syst.	2016	DBLP DOI BibTeX RDF
21	Jeffrey Aborot, Henry N. Adorna, Jhoirene B. Clemente	On Self-Reducibility and Reoptimization of Closest Substring Problem.	CoRR	2016	DBLP BibTeX RDF
21	Ji-Won Huh, Shuji Isobe, Eisuke Koizumi, Hiroki Shizuya	On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions.	IEICE Trans. Inf. Syst.	2013	DBLP DOI BibTeX RDF
21	Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein	Information Lower Bounds via Self-reducibility.	CSR	2013	DBLP DOI BibTeX RDF
21	Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein	Information lower bounds via self-reducibility.	Electron. Colloquium Comput. Complex.	2012	DBLP BibTeX RDF
21	Nelly Fazio, Kevin Iga, Antonio Nicolosi, Ludovic Perret, William E. Skeith III	Random Self-Reducibility Properties of Learning Problems over Burnside Groups of Exponent 3.	IACR Cryptol. ePrint Arch.	2011	DBLP BibTeX RDF
21	Eric Allender, Michal Koucký 0001	Amplifying lower bounds by means of self-reducibility.	J. ACM	2010	DBLP DOI BibTeX RDF
21	Eric Allender, Michal Koucký 0001	Amplifying Lower Bounds by Means of Self-Reducibility.	Electron. Colloquium Comput. Complex.	2008	DBLP BibTeX RDF
21	André Hernich, Arfst Nickelsen	Combining Self-reducibility and Partial Information Algorithms.	MFCS	2005	DBLP DOI BibTeX RDF
21	Aduri Pavan, N. V. Vinodchandran	Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
21	Lane A. Hemaspaandra, Harald Hempel	P-immune sets with holes lack self-reducibility properties.	Theor. Comput. Sci.	2003	DBLP DOI BibTeX RDF
21	Lane A. Hemaspaandra, Harald Hempel	P-Immune Sets with Holes Lack Self-Reducibility Properties	CoRR	2001	DBLP BibTeX RDF
21	Lane A. Hemaspaandra, Harald Hempel	P-Immune Sets with Holes Lack Self-Reducibility Properties.	DMTCS	2001	DBLP DOI BibTeX RDF
21	Edith Hemaspaandra, Ashish V. Naik, Mitsunori Ogihara, Alan L. Selman	P-Selektive Sets and Reducing Search to Decision vs Self-Reducibility.	J. Comput. Syst. Sci.	1996	DBLP DOI BibTeX RDF
21	Lane A. Hemaspaandra, Marius Zimand	Strong Self-Reducibility Precludes Strong Immunity.	Math. Syst. Theory	1996	DBLP DOI BibTeX RDF
21	Jie Wang 0002	Some Results on Selectivity and Self-Reducibility.	Inf. Process. Lett.	1995	DBLP DOI BibTeX RDF
21	Lane A. Hemaspaandra, Riccardo Silvestri	Easily Checked Generalized Self-Reducibility.	SIAM J. Comput.	1995	DBLP DOI BibTeX RDF
21	Joan Feigenbaum, Lance Fortnow	Random-Self-Reducibility of Complete Sets.	SIAM J. Comput.	1993	DBLP DOI BibTeX RDF
21	Lane A. Hemachandra, Riccardo Silvestri	Easity Checked Self-Reducibility (Extended Abstract).	FCT	1993	DBLP DOI BibTeX RDF
21	Karl R. Abrahamson, Michael R. Fellows, Christopher B. Wilson	Parallel Self-Reducibility.	ICCI	1992	DBLP BibTeX RDF
21	Sanjeev N. Khadilkar, Somenath Biswas	Padding, Commitment and Self-Reducibility.	Theor. Comput. Sci.	1991	DBLP DOI BibTeX RDF
21	Joan Feigenbaum, Lance Fortnow	On the Random-Self-Reducibility of Complete Sets.	SCT	1991	DBLP DOI BibTeX RDF
21	Jürgen Kämper	A Result Relating Disjunctive Self-Reducibility to P-Immunity.	Inf. Process. Lett.	1990	DBLP DOI BibTeX RDF
21	José L. Balcázar	Self-Reducibility.	J. Comput. Syst. Sci.	1990	DBLP DOI BibTeX RDF
21	Joan Feigenbaum, Sampath Kannan, Noam Nisan	Lower Bounds on Random-Self-Reducibility.	SCT	1990	DBLP DOI BibTeX RDF
21	Tatsuaki Okamoto, Kazuo Ohta	Divertible Zero Knowledge Interactive Proofs and Commutative Random Self-Reducibility.	EUROCRYPT	1989	DBLP DOI BibTeX RDF
21	Klaus Ambos-Spies, Jürgen Kämper	On Disjunctive Self-Reducibility.	CSL	1988	DBLP DOI BibTeX RDF
21	José L. Balcázar	Logspace self-reducibility.	SCT	1988	DBLP DOI BibTeX RDF
21	Martin Tompa, Heather Woll	Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information	FOCS	1987	DBLP DOI BibTeX RDF
21	José L. Balcázar	Self-Reducibility.	STACS	1987	DBLP DOI BibTeX RDF
21	Ker-I Ko	On Self-Reducibility and Weak P-Selectivity.	J. Comput. Syst. Sci.	1983	DBLP DOI BibTeX RDF
14	Aggelos Kiayias, Moti Yung	Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
14	Dimitar Jetchev, Ramarathnam Venkatesan	Bits Security of the Elliptic Curve Diffie-Hellman Secret Keys.	CRYPTO	2008	DBLP DOI BibTeX RDF
14	Harold N. Gabow	Finding paths and cycles of superpolylogarithmic length.	STOC	2004	DBLP DOI BibTeX RDF	approximation algorithms, graph algorithms, cycle, path
14	Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen	Hidden translation and orbit coset in quantum computing.	STOC	2003	DBLP DOI BibTeX RDF
14	Leslie Ann Goldberg, Steven Kelk, Mike Paterson	The complexity of choosing an H-colouring (nearly) uniformly at random.	STOC	2002	DBLP DOI BibTeX RDF
14	Liming Cai, David W. Juedes, Iyad A. Kanj	The Inapproximability of Non NP-hard Optimization Problems.	ISAAC	1998	DBLP DOI BibTeX RDF
14	Rainer Schuler, Tomoyuki Yamakami	Structural Average Case Complexity.	FSTTCS	1992	DBLP DOI BibTeX RDF
14	Uwe Schöning	Robust Orale Machines.	MFCS	1988	DBLP DOI BibTeX RDF