Search results for "np-hardness"

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