Search results for "intractability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
56	John Atkins, William E. Hart	On the Intractability of Protein Folding with a Finite Alphabet of Amino Acids.	Algorithmica	1999	DBLP DOI BibTeX RDF	Protein folding, Protein structure prediction, Intractability
56	Satoshi Hada, Toshiaki Tanaka	A Relationship between One-Wayness and Correlation Intractability.	Public Key Cryptography	1999	DBLP DOI BibTeX RDF	correlation intractability, zero-knowledge, One-way functions, random oracle, interactive proofs, round complexity
46	Kaoru Kurosawa, Katja Schmidt-Samoa	New Online/Offline Signature Schemes Without Random Oracles.	Public Key Cryptography	2006	DBLP DOI BibTeX RDF	Online/offline signatures, trapdoor hash, division intractability, strong RSA assumption
46	Geneviève Arboit, Jean-Marc Robert 0001	From Fixed-Length Messages to Arbitrary-Length Messages Practical RSA Signature Padding Schemes.	CT-RSA	2001	DBLP DOI BibTeX RDF	padding scheme, atomic primitive, hash-and-sign, division intractability, smooth numbers, Digital signature, RSA, provable security
41	Johannes Köbler, Rainer Schuler	Average-case intractability vs. worst-case intractability.	Inf. Comput.	2004	DBLP DOI BibTeX RDF
41	Johannes Köbler, Rainer Schuler	Average-Case Intractability vs. Worst-Case Intractability	Electron. Colloquium Comput. Complex.	1998	DBLP BibTeX RDF
41	Johannes Köbler, Rainer Schuler	Average-Case Intractability vs. Worst-Case Intractability.	MFCS	1998	DBLP DOI BibTeX RDF
35	Song Y. Yan, Carsten Maple, Glyn James	A New Scheme for Deniable/Repudiable Authentication.	CASC	2007	DBLP DOI BibTeX RDF	Deniable/repudiable authentication, quadratic residuosity problem, intractability
35	Siguna Müller	On the Security of Williams Based Public Key Encryption Scheme.	Public Key Cryptography	2001	DBLP DOI BibTeX RDF	(Weak)- Sole-Samplability, Factorization Intractability, Oracle Hashing, Williams' Encryption Scheme, Chosen Ciphertext Security, Plaintext Awareness
32	Boaz Barak, Oded Goldreich 0001	Universal Arguments and their Applications.	CCC	2002	DBLP DOI BibTeX RDF	Probabilistic proof systems, computationally-sound proof systems, zero-knowledge proof systems, probabilistic checkable proofs (PCP), collision-free hashing, witness indistinguishable proof systems, error-correcting codes, proofs of knowledge
31	Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann	Deconstructing Intractability: A Case Study for Interval Constrained Coloring.	CPM	2009	DBLP DOI BibTeX RDF
31	Andy Rupp, Gregor Leander, Endre Bangerter, Alexander W. Dent, Ahmad-Reza Sadeghi	Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems.	ASIACRYPT	2008	DBLP DOI BibTeX RDF	Generic Group Model, Hardness Conditions, Lower Bounds, Straight-Line Programs
31	Ian Davidson, S. S. Ravi	Intractability and clustering with constraints.	ICML	2007	DBLP DOI BibTeX RDF
31	Jens Gramm, Jiong Guo, Rolf Niedermeier	Parameterized Intractability of Distinguishing Substring Selection.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
31	Isaac Elias	Settling the Intractability of Multiple Alignment.	ISAAC	2003	DBLP DOI BibTeX RDF
25	Stephan Kreutzer, Siamak Tazari	Lower Bounds for the Complexity of Monadic Second-Order Logic.	LICS	2010	DBLP DOI BibTeX RDF	Parameterized Intractability, Graph Structure Theory, Treewidth, Parameterized Complexity, Finite Model Theory, Monadic Second-Order Logic
25	Benny Chor, Tamir Tuller	Finding a maximum likelihood tree is hard.	J. ACM	2006	DBLP DOI BibTeX RDF	approximate vertex cover, tree reconstruction, Maximum likelihood, maximum parsimony, intractability
25	Ran Canetti, Oded Goldreich 0001, Shai Halevi	The random oracle methodology, revisited.	J. ACM	2004	DBLP DOI BibTeX RDF	CS-proofs, Correlation intractability, the random-oracle model, cryptography, diagonalization
25	Khanh P. V. Doan, Kit Po Wong	SHAPES: A Novel Approach for Learning Search Heuristics in Under-Constrained Optimization Problems.	IEEE Trans. Knowl. Data Eng.	1997	DBLP DOI BibTeX RDF	weight assignment, search, heuristics, Explanation-Based Learning, intractability
25	Russell Impagliazzo, Moni Naor	Efficient Cryptographic Schemes Provably as Secure as Subset Sum	FOCS	1989	DBLP DOI BibTeX RDF	cryptographic schemes, universal one-way hash function, pseudorandom generator, NC, subset sum, intractability
21	Yuval Ishai, Manoj Prabhakaran 0001, Amit Sahai	Secure Arithmetic Computation with No Honest Majority.	TCC	2009	DBLP DOI BibTeX RDF
21	Aggelos Kiayias, Moti Yung	Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
21	Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai	Cryptography with constant computational overhead.	STOC	2008	DBLP DOI BibTeX RDF	constant computational overhead, cryptography, universal hashing
21	Felix Brandt 0001	How to obtain full privacy in auctions.	Int. J. Inf. Sec.	2006	DBLP DOI BibTeX RDF	Cryptographic protocols, Auctions, Homomorphic encryption
21	Ariel Fuxman, Phokion G. Kolaitis, Renée J. Miller, Wang Chiew Tan	Peer data exchange.	ACM Trans. Database Syst.	2006	DBLP DOI BibTeX RDF	data integration, Data exchange, schema mapping, conjunctive queries, certain answers, metadata model management
21	Ariel Fuxman, Phokion G. Kolaitis, Renée J. Miller, Wang Chiew Tan	Peer data exchange.	PODS	2005	DBLP DOI BibTeX RDF
21	Matthias Fitzi, Thomas Holenstein, Jürg Wullschleger	Multi-party Computation with Hybrid Security.	EUROCRYPT	2004	DBLP DOI BibTeX RDF
21	Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Toby Walsh	The Tractability of Global Constraints.	CP	2004	DBLP DOI BibTeX RDF
21	Ingrid Biehl, Tsuyoshi Takagi	A New Distributed Primality Test for Shared RSA Keys Using Quadratic Fields.	ACISP	2002	DBLP DOI BibTeX RDF	Distributed RSA, quadratic fields, parallel computation, primality test
21	Claus-Peter Schnorr	Security of Blind Discrete Log Signatures against Interactive Attacks.	ICICS	2001	DBLP DOI BibTeX RDF
21	Daniel Bleichenbacher, Phong Q. Nguyen	Noisy Polynomial Interpolation and Noisy Chinese Remaindering.	EUROCRYPT	2000	DBLP DOI BibTeX RDF
21	Martin Farach, Sampath Kannan	Efficient Algorithms for Inverting Evolution.	J. ACM	1999	DBLP DOI BibTeX RDF
21	Ran Canetti, Shafi Goldwasser	An Efficient Threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack.	EUROCRYPT	1999	DBLP DOI BibTeX RDF
21	Berry Schoenmakers	A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic.	CRYPTO	1999	DBLP DOI BibTeX RDF
21	Michael J. Kearns, Leslie G. Valiant	Cryptographic Limitations on Learning Boolean Formulae and Finite Automata.	J. ACM	1994	DBLP DOI BibTeX RDF
21	Liming Cai, Jianer Chen, Rodney G. Downey, Michael R. Fellows	On the Structure of Parameterized Problems in NP (Extended Abstract).	STACS	1994	DBLP DOI BibTeX RDF
21	Oded Goldreich 0001, Hugo Krawczyk, Michael Luby	On the Existence of Pseudorandom Generators.	CRYPTO	1988	DBLP DOI BibTeX RDF
20	Nico Döttling, Tamer Mour	On the Black-Box Complexity of Correlation Intractability.	ITCS	2024	DBLP DOI BibTeX RDF
20	Ge Luo 0002, Weisi Fan, Miaoran Li, Youbiao He, Yinfei Yang, Forrest Sheng Bao	On the Intractability to Synthesize Factual Inconsistencies in Summarization.	EACL (Findings)	2024	DBLP BibTeX RDF
20	Abhishek Singh 0007	On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times.	Inf. Process. Lett.	2023	DBLP DOI BibTeX RDF
20	Yuseok Kim, Suk Hee Park	Highly Productive 3D Printing Process to Transcend Intractability in Materials and Geometries via Interactive Machine-Learning-Based Technique.	Adv. Intell. Syst.	2023	DBLP DOI BibTeX RDF
20	Stavros D. Ioannidis, Bart de Keijzer, Carmine Ventre	Clearing Financial Networks with Derivatives: From Intractability to Algorithms.	CoRR	2023	DBLP DOI BibTeX RDF
20	Dhruv Malik, Conor Igoe, Yuanzhi Li, Aarti Singh	Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality.	CoRR	2023	DBLP DOI BibTeX RDF
20	Thibault Prunet, Nabil Absi, Diego Cattaruzza	The Intractability of the Picker Routing Problem.	CoRR	2023	DBLP DOI BibTeX RDF
20	Paul W. Goldberg, Kasper Høgh, Alexandros Hollender	The Frontier of Intractability for EFX with Two Agents.	CoRR	2023	DBLP DOI BibTeX RDF
20	Rustem Takhanov, Maxat Tezekbayev, Artur Pak, Arman Bolatov, Zhibek Kadyrsizova, Zhenisbek Assylbekov	Intractability of Learning the Discrete Logarithm with Gradient-Based Methods.	CoRR	2023	DBLP DOI BibTeX RDF
20	Nico Döttling, Tamer Mour	On The Black-Box Complexity of Correlation Intractability.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
20	Paul W. Goldberg, Kasper Høgh, Alexandros Hollender	The Frontier of Intractability for EFX with Two Agents.	SAGT	2023	DBLP DOI BibTeX RDF
20	Rustem Takhanov, Maxat Tezekbayev, Artur Pak, Arman Bolatov, Zhibek Kadyrsizova, Zhenisbek Assylbekov	Intractability of Learning the Discrete Logarithm with Gradient-Based Methods.	ACML	2023	DBLP BibTeX RDF
20	Xing Tan 0002, Pascal Bercher	Intractability of Optimal Multi-Agent Pathfinding on Directed Graphs.	ECAI	2023	DBLP DOI BibTeX RDF
20	Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain 0002, Zhengzhong Jin, Jiaheng Zhang	Correlation Intractability and SNARGs from Sub-exponential DDH.	CRYPTO (4)	2023	DBLP DOI BibTeX RDF
20	Dhruv Malik, Conor Igoe, Yuanzhi Li, Aarti Singh	Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality.	ICML	2023	DBLP BibTeX RDF
20	Dmitriy S. Malyshev, O. V. Pristavchenko	An intractability result for the vertex 3-colourability problem.	Optim. Lett.	2022	DBLP DOI BibTeX RDF
20	Pål Grønås Drange, Markus Fanebust Dregi, Daniel Lokshtanov, Blair D. Sullivan	On the threshold of intractability.	J. Comput. Syst. Sci.	2022	DBLP DOI BibTeX RDF
20	Matteo Castiglioni, Alberto Marchesi 0001, Nicola Gatti 0001	Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting.	CoRR	2022	DBLP BibTeX RDF
20	Jiehua Chen 0001, Sanjukta Roy	Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule.	CoRR	2022	DBLP BibTeX RDF
20	Naoto Ohsaka	On the Parameterized Intractability of Determinant Maximization.	CoRR	2022	DBLP DOI BibTeX RDF
20	Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain 0002, Zhengzhong Jin, Jiaheng Zhang	Correlation Intractability and SNARGs from Sub-exponential DDH.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
20	Naoto Ohsaka	On the Parameterized Intractability of Determinant Maximization.	ISAAC	2022	DBLP DOI BibTeX RDF
20	Hans L. Bodlaender	From the W-hierarchy to XNLP - Classes of Fixed Parameter Intractability.	WALCOM	2022	DBLP DOI BibTeX RDF
20	Ajinkya Gaikwad, Soumen Maity, Shuvam Kant Tripathi	Parameterized Intractability of Defensive Alliance Problem.	CALDAM	2022	DBLP DOI BibTeX RDF
20	Laura van de Braak, Ronald de Haan, Iris van Rooij, Mark Blokpoel	Intractability of Bayesian belief-updating during communication.	CogSci	2022	DBLP BibTeX RDF
20	Andrea Caucchiolo, Ferdinando Cicalese	On the Intractability Landscape of Digraph Intersection Representations.	IWOCA	2022	DBLP DOI BibTeX RDF
20	Xing Tan 0002, Mahzabeen Emu, Salimur Choudhury	Task Offloading in Mobile Edge Computing: Intractability and Proposed Approaches.	WI/IAT	2022	DBLP DOI BibTeX RDF
20	Matteo Castiglioni, Alberto Marchesi 0001, Nicola Gatti 0001	Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting. (PDF / PS)	AAMAS	2022	DBLP BibTeX RDF
20	Arnab Bhattacharyya 0001, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx	Parameterized Intractability of Even Set and Shortest Vector Problem.	J. ACM	2021	DBLP DOI BibTeX RDF
20	Tamer Mour	Correlation Intractability vs. One-wayness.	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
20	Louis Dublois	Algorithms and Intractability of Some NP-hard Domination Problems with Private Structure. (Algorithmes et Intractabilité de Certains Problèmes de Domination NP-difficiles avec Structure Privée).		2021	RDF
20	Patricia Rich, Mark Blokpoel, Ronald de Haan, Iris van Rooij	How Intractability Spans the Cognitive and Evolutionary Levels of Explanation.	Top. Cogn. Sci.	2020	DBLP DOI BibTeX RDF
20	Arun U	The "cardinality of extended solution set" criterion for establishing the intractability of NP problems.	CoRR	2020	DBLP BibTeX RDF
20	Phablo F. S. Moura, Yoshiko Wakabayashi	Strong intractability results for generalized convex recoloring problems.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
20	Zvika Brakerski, Venkata Koppula, Tamer Mour	NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
20	Ruta Jawale, Dakshita Khurana	Lossy Correlation Intractability and PPAD Hardness from Sub-exponential LWE.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
20	Ali Atiia, Corbin Hopper, Katsumi Inoue, Silvia Vidal, Jérôme Waldispühl	Computational intractability law molds the topology of biological networks.	Appl. Netw. Sci.	2020	DBLP DOI BibTeX RDF
20	Robert Kudelic, Kornelije Rabuzin	Dealing with Intractability of Information System Subsystems Development Order via Control Flow Graph Reducibility.	EEET	2020	DBLP DOI BibTeX RDF
20	Zvika Brakerski, Venkata Koppula, Tamer Mour	NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations.	CRYPTO (3)	2020	DBLP DOI BibTeX RDF
20	Aafaf Ouaddah	Chapter Eight - A blockchain based access control framework for the security and privacy of IoT with strong anonymity unlinkability and intractability guarantees.	Adv. Comput.	2019	DBLP DOI BibTeX RDF
20	Yang Bo, Milind Dawande, Woonghee Tim Huh, Ganesh Janakiraman, Mahesh Nagarajan	Determining Process Capacity: Intractability and Efficient Special Cases.	Manuf. Serv. Oper. Manag.	2019	DBLP DOI BibTeX RDF
20	Igor Carboni Oliveira	Randomness and Intractability in Kolmogorov Complexity.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF
20	Arnab Bhattacharyya 0001, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx	Parameterized Intractability of Even Set and Shortest Vector Problem.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF
20	Arnab Bhattacharyya 0001, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx	Parameterized Intractability of Even Set and Shortest Vector Problem.	CoRR	2019	DBLP BibTeX RDF
20	Mikhail Anokhin	Constructing a pseudo-freefamily of finite computational groups under the generalinteger factoring intractability assumption.	Groups Complex. Cryptol.	2019	DBLP DOI BibTeX RDF
20	Ilias Diakonikolas, Gautam Kamath 0001, Daniel Kane 0001, Jerry Li 0001, Ankur Moitra, Alistair Stewart	Robust Estimators in High-Dimensions Without the Computational Intractability.	SIAM J. Comput.	2019	DBLP DOI BibTeX RDF
20	Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson	Multi-prover interactive proofs: how to remove intractability assumptions.	Providing Sound Foundations for Cryptography	2019	DBLP DOI BibTeX RDF
20	Iris van Rooij, Mark Blokpoel, Johan Kwisthout, Todd Wareham	Cognition and intractability: a guide to classical and parameterized complexity analysis.		2019	DOI RDF
20	Igor Carboni Oliveira	Randomness and Intractability in Kolmogorov Complexity.	ICALP	2019	DBLP DOI BibTeX RDF
20	Richard Hoshino, Max Notarangelo	Computational Intractability and Solvability for the Birds of a Feather Game.	AAAI	2019	DBLP DOI BibTeX RDF
20	Iris van Rooij, Cory D. Wright, Johan Kwisthout, Todd Wareham	Rational analysis, intractability, and the prospects of 'as if'-explanations.	Synth.	2018	DBLP DOI BibTeX RDF
20	William S. Zwicker	Cycles and Intractability in a Large Class of Aggregation Rules.	J. Artif. Intell. Res.	2018	DBLP DOI BibTeX RDF
20	Arnab Bhattacharyya 0001, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi	Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
20	Arnab Bhattacharyya 0001, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi	Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.	CoRR	2018	DBLP BibTeX RDF
20	Mikhail Anokhin	A certain family of subgroups of ℤn* is weakly pseudo-free under the general integer factoring intractability assumption.	Groups Complex. Cryptol.	2018	DBLP DOI BibTeX RDF
20	Ran Canetti, Alex Lombardi, Daniel Wichs	Non-Interactive Zero Knowledge and Correlation Intractability from Circular-Secure FHE.	IACR Cryptol. ePrint Arch.	2018	DBLP BibTeX RDF
20	Ran Canetti, Yilei Chen 0001, Leonid Reyzin, Ron D. Rothblum	Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption.	IACR Cryptol. ePrint Arch.	2018	DBLP BibTeX RDF
20	Kunal Agrawal, Sanjoy K. Baruah	Intractability Issues in Mixed-Criticality Scheduling.	ECRTS	2018	DBLP DOI BibTeX RDF
20	Arnab Bhattacharyya 0001, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi	Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.	ICALP	2018	DBLP DOI BibTeX RDF
20	Ralph Christian Bottesch	On W[1]-Hardness as Evidence for Intractability.	MFCS	2018	DBLP DOI BibTeX RDF
20	Ran Canetti, Yilei Chen 0001, Leonid Reyzin, Ron D. Rothblum	Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption.	EUROCRYPT (1)	2018	DBLP DOI BibTeX RDF
20	Phablo F. S. Moura, Yoshiko Wakabayashi	Strong intractability of generalized convex recoloring problems.	Electron. Notes Discret. Math.	2017	DBLP DOI BibTeX RDF
20	Jacopo Banfi, Nicola Basilico, Francesco Amigoni	Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes.	IEEE Robotics Autom. Lett.	2017	DBLP DOI BibTeX RDF