The FacetedDBLP logo    Search for: in:

Disable automatic phrases ?     Syntactic query expansion: ?

Searching for phrase np-hardness (changed automatically) with no syntactic query expansion in all metadata.

Publication years (Num. hits)
1980-1989 (16) 1990-1992 (16) 1993-1994 (24) 1995 (18) 1996 (28) 1997 (44) 1998 (41) 1999 (55) 2000 (48) 2001 (69) 2002 (99) 2003 (93) 2004 (126) 2005 (175) 2006 (190) 2007 (227) 2008 (252) 2009 (224) 2010 (93) 2011 (103) 2012 (111) 2013 (111) 2014 (115) 2015 (119) 2016 (152) 2017 (149) 2018 (159) 2019 (207) 2020 (227) 2021 (213) 2022 (233) 2023 (245) 2024 (67)
Publication types (Num. hits)
article(1890) book(2) incollection(9) inproceedings(2107) phdthesis(41)
Venues (Conferences, Journals, ...)
GrowBag graphs for keyword ? (Num. hits/coverage)

Group by:
The graphs summarize 1702 occurrences of 848 keywords

Results
Found 4049 publication records. Showing 4049 according to the selection in the facets
Hits ? Authors Title Venue Year Link Author keywords
90Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu Impossibility Results on Weakly Black-Box Hardness Amplification. Search on Bibsonomy FCT The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
75Sounaka Mishra, Kripasindhu Sikdar On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem. Search on Bibsonomy IFIP TCS The full citation details ... 2000 DBLP  DOI  BibTeX  RDF NP-optimization problems, Minimaximal and maximinimal NP-optimization problems, L-reduction, Approximation algorithms, Hardness of approximation, APX-hardness
68Ronen Shaltiel, Emanuele Viola Hardness amplification proofs require majority. Search on Bibsonomy STOC The full citation details ... 2008 DBLP  DOI  BibTeX  RDF amplification, natural proofs, black-box, hardness, average-case complexity, constant-depth circuits, majority
68Julia Chuzhoy, Sanjeev Khanna Hardness of cut problems in directed graphs. Search on Bibsonomy STOC The full citation details ... 2006 DBLP  DOI  BibTeX  RDF directed multicut, hardness of approximation, sparsest cut
61Alexander Healy, Salil P. Vadhan, Emanuele Viola Using nondeterminism to amplify hardness. Search on Bibsonomy STOC The full citation details ... 2004 DBLP  DOI  BibTeX  RDF noise stability, pseudorandom generators for space-bounded computation, average-case complexity, hardness amplification
57Vincent Conitzer, Tuomas Sandholm, Jérôme Lang When are elections with few candidates hard to manipulate?. Search on Bibsonomy J. ACM The full citation details ... 2007 DBLP  DOI  BibTeX  RDF hardness of manipulation, voting, Computational social choice
54Bernhard Fuchs On the Hardness of Range Assignment Problems. Search on Bibsonomy CIAC The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
54Ronen Shaltiel, Christopher Umans Low-end uniform hardness vs. randomness tradeoffs for AM. Search on Bibsonomy STOC The full citation details ... 2007 DBLP  DOI  BibTeX  RDF hardness vs. randomness tradeoff, hitting-set generator, derandomization, Arthur-Merlin games
54Ashkan Aazami, Michael D. Stilp Approximation Algorithms and Hardness for Domination with Propagation. Search on Bibsonomy APPROX-RANDOM The full citation details ... 2007 DBLP  DOI  BibTeX  RDF Power Dominating Set, Approximation Algorithms, Integer Programming, Planar Graphs, Greedy Algorithms, Dominating Set, Hardness of Approximation, PTAS
54Joseph Cheriyan, Mohammad R. Salavatipour Hardness and Approximation Results for Packing Steiner Trees. Search on Bibsonomy Algorithmica The full citation details ... 2006 DBLP  DOI  BibTeX  RDF Approximation algorithms, Steiner trees, Hardness of approximation, Packing problems
47Juan Arturo Herrera Ortiz, Carlos Oliver-Morales, Katya Rodríguez-Vázquez Amount and type of information: a GA-hardness taxonomy. Search on Bibsonomy GECCO The full citation details ... 2010 DBLP  DOI  BibTeX  RDF evolutionary algorithms, problem difficulty
47Magnus Johnsson, Christian Balkenius Recognizing texture and hardness by touch. Search on Bibsonomy IROS The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
47Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee Optimal Cryptographic Hardness of Learning Monotone Functions. Search on Bibsonomy ICALP (1) The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
47Lin Xu, Holger H. Hoos, Kevin Leyton-Brown Hierarchical Hardness Models for SAT. Search on Bibsonomy CP The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
47Neha Rungta, Eric G. Mercer Hardness for Explicit State Software Model Checking Benchmarks. Search on Bibsonomy SEFM The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
47Chi-Jen Lu On the Complexity of Parallel Hardness Amplification for One-Way Functions. Search on Bibsonomy TCC The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
47Adam R. Klivans, Alexander A. Sherstov Cryptographic Hardness for Learning Intersections of Halfspaces. Search on Bibsonomy FOCS The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
47Asa Packer NP - Hardness of Largest Contained and Smallest Containing Simplices for V- and H-Polytopes. Search on Bibsonomy Discret. Comput. Geom. The full citation details ... 2002 DBLP  DOI  BibTeX  RDF
47Guohua Jin, Luay Nakhleh, Sagi Snir, Tamir Tuller Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic. Search on Bibsonomy IEEE ACM Trans. Comput. Biol. Bioinform. The full citation details ... 2009 DBLP  DOI  BibTeX  RDF hardness and approximation, phylogenetic networks, Maximum parsimony, horizontal gene transfer
47Kim Thang Nguyen -Hardness of Pure Nash Equilibrium in Scheduling and Connection Games. Search on Bibsonomy SOFSEM The full citation details ... 2009 DBLP  DOI  BibTeX  RDF Nash equilibrium, hardness
47Venkatesan Guruswami, Sanjeev Khanna On the Hardness of 4-Coloring a 3-Colorable Graph. Search on Bibsonomy CCC The full citation details ... 2000 DBLP  DOI  BibTeX  RDF Graph Coloring, Hardness of approximation, PCP
43Subhash Khot, Ashok Kumar Ponnuswami Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. Search on Bibsonomy ICALP (1) The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
43Joshua Buresh-Oppenheim, Rahul Santhanam Making Hard Problems Harder. Search on Bibsonomy CCC The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
43Subhash Khot On the Unique Games Conjecture. Search on Bibsonomy FOCS The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
43Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi Learnability and Automatizability. Search on Bibsonomy FOCS The full citation details ... 2004 DBLP  DOI  BibTeX  RDF
43Madhu Sudan 0001, Luca Trevisan, Salil P. Vadhan Pseudorandom Generators without the XOR Lemma (Abstract). Search on Bibsonomy CCC The full citation details ... 1999 DBLP  DOI  BibTeX  RDF polynomial reconstruct ion, Pseudorandom generators, extractors, list-decoding
43Ronen Shaltiel, Christopher Umans Simple extractors for all min-entropies and a new pseudorandom generator. Search on Bibsonomy J. ACM The full citation details ... 2005 DBLP  DOI  BibTeX  RDF Hardness versus randomness, pseudorandom generator, randomness extractor
43Venkatesan Guruswami Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. Search on Bibsonomy Algorithmica The full citation details ... 2004 DBLP  DOI  BibTeX  RDF Set splitting, Hardness of approximations, PCP, Gadgets
40Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu On the Complexity of Hardness Amplification. Search on Bibsonomy IEEE Trans. Inf. Theory The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
40Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz 0002 Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. Search on Bibsonomy STOC The full citation details ... 2008 DBLP  DOI  BibTeX  RDF linear and semidefinite programming, metric labelling, multiway cut, integrality gaps, unique games conjecture
40Michael Elkin, David Peleg The Hardness of Approximating Spanner Problems. Search on Bibsonomy Theory Comput. Syst. The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
40Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. Search on Bibsonomy FOCS The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
40Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu On the Complexity of Hardness Amplification. Search on Bibsonomy CCC The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
40Joseph Cheriyan, Mohammad R. Salavatipour Hardness and Approximation Results for Packing Steiner Trees. Search on Bibsonomy ESA The full citation details ... 2004 DBLP  DOI  BibTeX  RDF
40Michael Elkin, David Peleg The Hardness of Approximating Spanner Problems. Search on Bibsonomy STACS The full citation details ... 2000 DBLP  DOI  BibTeX  RDF
39Julia Chuzhoy, Sanjeev Khanna Polynomial flow-cut gaps and hardness of directed cut problems. Search on Bibsonomy J. ACM The full citation details ... 2009 DBLP  DOI  BibTeX  RDF Directed multicut, hardness of approximation, sparsest cut
39Ishay Haviv, Oded Regev 0001 Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Search on Bibsonomy STOC The full citation details ... 2007 DBLP  DOI  BibTeX  RDF lattices, hardness of approximation, tensor product
39Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar Hardness of routing with congestion in directed graphs. Search on Bibsonomy STOC The full citation details ... 2007 DBLP  DOI  BibTeX  RDF all-or-nothing flow, hardness of approximation, multicommodity flow, edge-disjoint paths, integrality gap, congestion minimization
39Julia Chuzhoy, Sanjeev Khanna Polynomial flow-cut gaps and hardness of directed cut problems. Search on Bibsonomy STOC The full citation details ... 2007 DBLP  DOI  BibTeX  RDF concurrent flow, directed multicut, directed sparsest cut, flow-cut gaps, hardness of approximation, multicommodity flow
39Irit Dinur, Elchanan Mossel, Oded Regev 0001 Conditional hardness for approximate coloring. Search on Bibsonomy STOC The full citation details ... 2006 DBLP  DOI  BibTeX  RDF graph coloring, hardness of approximation, unique games conjecture
39Venkatesan Guruswami, Valentine Kabanets Hardness Amplification Via Space-Efficient Direct Products. Search on Bibsonomy LATIN The full citation details ... 2006 DBLP  DOI  BibTeX  RDF error-correcting codes, expanders, Direct products, hardness amplification
39Subhash Khot Hardness of approximating the shortest vector problem in lattices. Search on Bibsonomy J. ACM The full citation details ... 2005 DBLP  DOI  BibTeX  RDF Approximation algorithms, cryptography, lattices, hardness of approximation, shortest vector problem
39Julia Chuzhoy, Joseph Naor New hardness results for congestion minimization and machine scheduling. Search on Bibsonomy STOC The full citation details ... 2004 DBLP  DOI  BibTeX  RDF routing, approximation algorithms, hardness of approximation, machine scheduling, congestion minimization
39Surajit Chaudhuri, Mayur Datar, Vivek R. Narasayya Index Selection for Databases: A Hardness Study and a Principled Heuristic Solution. Search on Bibsonomy IEEE Trans. Knowl. Data Eng. The full citation details ... 2004 DBLP  DOI  BibTeX  RDF Index selection, hardness result, scalability, linear programming, approximation, NP-hardness, knapsack
39Jacobo Torán On the Hardness of Graph Isomorphism. Search on Bibsonomy FOCS The full citation details ... 2000 DBLP  DOI  BibTeX  RDF logarithmic space many-one reductions, probabilistic logarithmic space, hardness results, randomized logarithmic space reduction, computational complexity, graph theory, encoding, determinant, graph isomorphism, perfect matching, complexity classes, hardness
39Venkatesan Guruswami, Johan Håstad, Madhu Sudan 0001 Hardness of Approximate Hypergraph Coloring. Search on Bibsonomy FOCS The full citation details ... 2000 DBLP  DOI  BibTeX  RDF approximate hypergraph coloring, covering complexity, probabilistic verifier, PCP verifier, 2-colorable 4-uniform hypergraph, hardness assumption, computational complexity, computational geometry, minimisation, graph colouring, hardness, minimization problems
37Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs. Search on Bibsonomy ICALP The full citation details ... 1997 DBLP  DOI  BibTeX  RDF
36Deeparnab Chakrabarty, Gagan Goel On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. Search on Bibsonomy FOCS The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
36Michael Alekhnovich More on Average Case vs Approximation Complexity. Search on Bibsonomy FOCS The full citation details ... 2003 DBLP  DOI  BibTeX  RDF
36Klaus Ambos-Spies Measure Theoretic Completeness Notions for the Exponential Time Classes. Search on Bibsonomy MFCS The full citation details ... 2000 DBLP  DOI  BibTeX  RDF
36Venkatesan Guruswami Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Search on Bibsonomy APPROX The full citation details ... 2000 DBLP  DOI  BibTeX  RDF
35Andy 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. Search on Bibsonomy ASIACRYPT The full citation details ... 2008 DBLP  DOI  BibTeX  RDF Generic Group Model, Hardness Conditions, Lower Bounds, Straight-Line Programs
35Wouter M. Bergmann Tiest, Astrid M. L. Kappers Kinaesthetic and Cutaneous Contributions to the Perception of Compressibility. Search on Bibsonomy EuroHaptics The full citation details ... 2008 DBLP  DOI  BibTeX  RDF Softness, Weber fraction, Compliance, Hardness
35Armen P. Sarvazyan, Andrei R. Skovoroda, Yuri P. Pyt'ev Mechanical Introscopy -- A New Modality of Medical Imaging for Detection of Breast and Prostate Cancer. Search on Bibsonomy CBMS The full citation details ... 1995 DBLP  DOI  BibTeX  RDF stress-strain relations, mechanical introscopy, medical imaging modality, breast cancer detection, prostate cancer detection, soft body tissues internal structure reconstruction, mechanical stress/strain pattern surface distribution, pressure sensor array, elasticity modulus, internal lesions, lesion hardness, mathematical simulation, mass cancer screening method, safety, medical image processing, geometry, inverse problem, biomechanics, elasticity, hardness, pressure sensors, mechanical properties
33Peng Zhang 0008, Jin-yi Cai, Linqing Tang, Wenbo Zhao 0001 Approximation and Hardness Results for Label Cut and Related Problems. Search on Bibsonomy TAMC The full citation details ... 2009 DBLP  DOI  BibTeX  RDF
33Yan Gérard About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness. Search on Bibsonomy IWCIA The full citation details ... 2009 DBLP  DOI  BibTeX  RDF Flow problems, NP-complete, Timetable, Discrete Tomography
33Hanafiah B. Yussof, Masahiro Ohka, Jumpei Takata, Yasuo Nasu, Mitsuhiro Yamano Low force control scheme for object hardness distinction in robot manipulation based on tactile sensing. Search on Bibsonomy ICRA The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
33Marcelo Luis Errecalde, Diego Ingaramo, Paolo Rosso Proximity Estimation and Hardness of Short-Text Corpora. Search on Bibsonomy DEXA Workshops The full citation details ... 2008 DBLP  DOI  BibTeX  RDF short-text corpora, proximity estimation, cluster validity measures, clustering
33Parikshit Gopalan, Subhash Khot, Rishi Saket Hardness of Reconstructing Multivariate Polynomials over Finite Fields. Search on Bibsonomy FOCS The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
33David Pinto 0001, Paolo Rosso On the Relative Hardness of Clustering Corpora. Search on Bibsonomy TSD The full citation details ... 2007 DBLP  DOI  BibTeX  RDF
33Venkatesan Guruswami, Prasad Raghavendra Hardness of Learning Halfspaces with Noise. Search on Bibsonomy FOCS The full citation details ... 2006 DBLP  DOI  BibTeX  RDF
33Miroslav Chlebík, Janka Chlebíková Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes. Search on Bibsonomy SODA The full citation details ... 2005 DBLP  BibTeX  RDF
33Ju Yong Lee, Eunseuk Oh, Hongsik Choi Hardness on IP-subnet Aware Routing in WDM Network. Search on Bibsonomy ICOIN The full citation details ... 2005 DBLP  DOI  BibTeX  RDF
33Subhash Khot Hardness of Approximating the Shortest Vector Problem in Lattices. Search on Bibsonomy FOCS The full citation details ... 2004 DBLP  DOI  BibTeX  RDF
33Philipp Kostuch, Krzysztof Socha Hardness Prediction for the University Course Timetabling Problem. Search on Bibsonomy EvoCOP The full citation details ... 2004 DBLP  DOI  BibTeX  RDF
33George Boukeas, Constantinos Halatsis, Vassilis Zissimopoulos, Panagiotis Stamatopoulos Measures of Intrinsic Hardness for Constraint Satisfaction Problem Instances. Search on Bibsonomy SOFSEM The full citation details ... 2004 DBLP  DOI  BibTeX  RDF
33Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Search on Bibsonomy Comput. Complex. The full citation details ... 2003 DBLP  DOI  BibTeX  RDF Mathematics Subject Classification (2000). 68Q15
33Haipeng Guo, William H. Hsu GA-Hardness Revisited. Search on Bibsonomy GECCO The full citation details ... 2003 DBLP  DOI  BibTeX  RDF
33Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions. Search on Bibsonomy CP The full citation details ... 2002 DBLP  DOI  BibTeX  RDF
32Gabjong Han, Seokhee Jeon, Seungmoon Choi Improving perceived hardness of haptic rendering via stiffness shifting: an initial study. Search on Bibsonomy VRST The full citation details ... 2009 DBLP  DOI  BibTeX  RDF hardness perception, haptic rendering, stiffness
32Ryan O'Donnell, Yi Wu 0002 Conditional hardness for satisfiable 3-CSPs. Search on Bibsonomy STOC The full citation details ... 2009 DBLP  DOI  BibTeX  RDF khot's, satisfiable 3-CSPs, hardness of approximation, PCP
32Zeev Dvir, Amir Shpilka, Amir Yehudayoff Hardness-randomness tradeoffs for bounded depth arithmetic circuits. Search on Bibsonomy STOC The full citation details ... 2008 DBLP  DOI  BibTeX  RDF bounded depth circuits, hardness-randomness tradeoffs, identity testing, lower bounds, arithmetic circuits
32Parikshit Gopalan, Venkatesan Guruswami Hardness Amplification within NP against Deterministic Algorithms. Search on Bibsonomy CCC The full citation details ... 2008 DBLP  DOI  BibTeX  RDF Hardness Amplication, Error-Correcting Codes, Derandomization, NP
32Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraëte, Raphael Yuster Approximation algorithms and hardness results for cycle packing problems. Search on Bibsonomy ACM Trans. Algorithms The full citation details ... 2007 DBLP  DOI  BibTeX  RDF Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap
32Refael Hassin, Jérôme Monnot, Danny Segev Approximation algorithms and hardness results for labeled connectivity problems. Search on Bibsonomy J. Comb. Optim. The full citation details ... 2007 DBLP  DOI  BibTeX  RDF Labeled connectivity, Approximation algorithms, Hardness of approximation
32Guillaume Blin, Guillaume Fertin, Irena Rusu, Christine Sinoquet Extending the Hardness of RNA Secondary Structure Comparison. Search on Bibsonomy ESCAPE The full citation details ... 2007 DBLP  DOI  BibTeX  RDF arc-annotated sequences, NP-hardness, computational biology, edit distance, RNA structures
32Hans Raj Tiwary On the hardness of minkowski addition and related operations. Search on Bibsonomy SCG The full citation details ... 2007 DBLP  DOI  BibTeX  RDF coNP-hardness, extended convex hull, polytope intersection, computational geometry, polytopes, turing reduction, minkowski addition
32Julia Chuzhoy, Joseph Naor New hardness results for congestion minimization and machine scheduling. Search on Bibsonomy J. ACM The full citation details ... 2006 DBLP  DOI  BibTeX  RDF resource minimization, scheduling, network routing, Hardness of approximation, congestion minimization
32Matthew Andrews, Lisa Zhang Logarithmic hardness of the undirected edge-disjoint paths problem. Search on Bibsonomy J. ACM The full citation details ... 2006 DBLP  DOI  BibTeX  RDF Hardness of approximation, undirected graphs, edge-disjoint paths
32Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia On the computational hardness based on linear FPT-reductions. Search on Bibsonomy J. Comb. Optim. The full citation details ... 2006 DBLP  DOI  BibTeX  RDF FPT-reduction, Complexity, Linear, Hardness
32Vitaly Feldman Hardness of approximate two-level logic minimization and PAC learning with membership queries. Search on Bibsonomy STOC The full citation details ... 2006 DBLP  DOI  BibTeX  RDF DNF minimization, proper learning, two-level logic minimization, hardness of approximation, uniform distribution, membership queries, truth table
32Ramkumar Chinchani, Duc T. Ha, Anusha Iyer, Hung Q. Ngo 0001, Shambhu J. Upadhyaya On the Hardness of Approximating the Min-Hack Problem. Search on Bibsonomy J. Comb. Optim. The full citation details ... 2005 DBLP  DOI  BibTeX  RDF hardness of threat analysis, computer security
32Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs. Search on Bibsonomy SIROCCO The full citation details ... 2005 DBLP  DOI  BibTeX  RDF black hole search, approximation algorithm, mobile agent, NP-hardness, graph exploration
32Matthew Andrews, Lisa Zhang Hardness of the undirected edge-disjoint paths problem. Search on Bibsonomy STOC The full citation details ... 2005 DBLP  DOI  BibTeX  RDF hardness of approximation, undirected graphs, edge-disjoint paths
32Uriel Feige, Shafi Goldwasser, László Lovász 0001, Shmuel Safra, Mario Szegedy Interactive Proofs and the Hardness of Approximating Cliques. Search on Bibsonomy J. ACM The full citation details ... 1996 DBLP  DOI  BibTeX  RDF independent set in a graph, multilinearity testing np-completeness, hardness of approximation, probabilistically checkable proofs
29Iftach Haitner Semi-honest to Malicious Oblivious Transfer - The Black-Box Way. Search on Bibsonomy TCC The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
29Vadim Lyubashevsky Lattice-Based Identification Schemes Secure Under Active Attacks. Search on Bibsonomy Public Key Cryptography The full citation details ... 2008 DBLP  DOI  BibTeX  RDF
29Antoine Joux, Kim Nguyen Separating Decision Diffie-Hellman from Computational Diffie-Hellman in Cryptographic Groups. Search on Bibsonomy J. Cryptol. The full citation details ... 2003 DBLP  DOI  BibTeX  RDF Elliptic curve, Discrete logarithm, Diffie-Hellman, Weil pairing
29Lane A. Hemaspaandra, Jörg Rothe A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem. Search on Bibsonomy MFCS The full citation details ... 1998 DBLP  DOI  BibTeX  RDF
29Madhav V. Marathe, Venkatesh Radhakrishnan, Harry B. Hunt III, S. S. Ravi Hierarchical Specified Unit Disk Graphs (Extended Abstract). Search on Bibsonomy WG The full citation details ... 1993 DBLP  DOI  BibTeX  RDF
28Oded Regev 0001 On lattices, learning with errors, random linear codes, and cryptography. Search on Bibsonomy J. ACM The full citation details ... 2009 DBLP  DOI  BibTeX  RDF average-case hardness, cryptography, quantum computation, Lattice, public key encryption
28Wei-Lin Li, Peng Zhang 0008, Daming Zhu On Constrained Facility Location Problems. Search on Bibsonomy J. Comput. Sci. Technol. The full citation details ... 2008 DBLP  DOI  BibTeX  RDF approximation hardness, approximation algorithm, local search, Facility Location
28Mark Burgin Universality, Reducibility, and Completeness. Search on Bibsonomy MCU The full citation details ... 2007 DBLP  DOI  BibTeX  RDF problem completeness, algorithm, computability, reducibility, universal, computing power, problem hardness
28Jonas Holmerin, Subhash Khot A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. Search on Bibsonomy STOC The full citation details ... 2004 DBLP  DOI  BibTeX  RDF max-bisection, hardness of approximation, linear equations, PCPs
28Patricia A. Evans, Andrew D. Smith Complexity of Approximating Closest Substring Problems. Search on Bibsonomy FCT The full citation details ... 2003 DBLP  DOI  BibTeX  RDF Closest Substring, Approximation algorithms, Hardness of approximation
28Marcus Schaefer 0001, Frank Stephan 0001 Strong Reductions and Immunity for Exponential Time. Search on Bibsonomy STACS The full citation details ... 2003 DBLP  DOI  BibTeX  RDF hardness for exponential time, polynomial time reducibilities, Computational and structural complexity
28Eran Halperin, Robert Krauthgamer Polylogarithmic inapproximability. Search on Bibsonomy STOC The full citation details ... 2003 DBLP  DOI  BibTeX  RDF integrality ratio, polylogarithmic approximation, approximation algorithms, Steiner tree, hardness of approximation
28Subhash Khot On the Power of Unique 2-Prover 1-Round Games. Search on Bibsonomy CCC The full citation details ... 2002 DBLP  DOI  BibTeX  RDF 2-prover games, Hardness of approximation, probabilistically checkable proofs
28Ian Agol, Joel Hass, William P. Thurston 3-MANIFOLD KNOT GENUS is NP-complete. Search on Bibsonomy CCC The full citation details ... 2002 DBLP  DOI  BibTeX  RDF 2-prover games, Hardness of approximation, probabilistically checkable proofs
28Christopher Umans Pseudo-Random Generators for All Hardnesses. Search on Bibsonomy CCC The full citation details ... 2002 DBLP  DOI  BibTeX  RDF low-degree extension, hardness vs. randomness tradeoffs, pseudo-random generator
Displaying result #1 - #100 of 4049 (100 per page; Change: )
Pages: [1][2][3][4][5][6][7][8][9][10][>>]
Valid XHTML 1.1! Valid CSS! [Valid RSS]
Maintained by L3S.
Previously maintained by Jörg Diederich.
Based upon DBLP by Michael Ley.
open data data released under the ODC-BY 1.0 license