Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
28	Rudi Pendavingh, Petra Schuurman, Gerhard J. Woeginger	De Bruijn Graphs and DNA Graphs.	WG	2001	DBLP DOI BibTeX RDF	De Bruijn graph, DNA graphs, computational complexity, graph theory, NP-hardness, DNA computing, recognition algorithm
28	Sascha Ott	Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2.	WG	1999	DBLP DOI BibTeX RDF	Superstrings, lower bounds, approximability, APX-hardness
28	Sanjeev Arora	Reductions, Codes, PCPs, and Inapproximability.	FOCS	1995	DBLP DOI BibTeX RDF	NP-hard functions, code-like Levin reduction, complexity assumption, positive fraction, 3-colorable graph, code-like reduction, computational complexity, graph theory, error correction codes, error-correcting codes, NP-hardness, codes, inapproximability, PCPs, hardness, approximation ratio
25	Ron M. Roth, Krishnamurthy Viswanathan	On the Hardness of Decoding the Gale-Berlekamp Code.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
25	Shai Halevi, Tal Rabin	Degradation and Amplification of Computational Hardness.	TCC	2008	DBLP DOI BibTeX RDF
25	Jeanine Kierkels, Elise van den Hoven	Children's haptic experiences of tangible artifacts varying in hardness.	NordiCHI	2008	DBLP DOI BibTeX RDF	haptic experience, interaction design, tangible user interfaces, tabletop gaming
25	Venkatesan Guruswami, Prasad Raghavendra	Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
25	Patrick Briest, Piotr Krysta	Buying cheap is expensive: hardness of non-parametric multi-product pricing.	SODA	2007	DBLP BibTeX RDF
25	Jonathan A. Kelner, Evdokia Nikolova	On the Hardness and Smoothed Complexity of Quasi-Concave Minimization.	FOCS	2007	DBLP DOI BibTeX RDF
25	Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets	Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification.	FOCS	2006	DBLP DOI BibTeX RDF
25	Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran	Some Results on Average-Case Hardness Within the Polynomial Hierarchy.	FSTTCS	2006	DBLP DOI BibTeX RDF
25		On the Hardness of Embeddings Between Two Finite Metrics.	ICALP	2005	DBLP DOI BibTeX RDF
25	Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma	Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games.	CCC	2003	DBLP DOI BibTeX RDF
25	Aggelos Kiayias, Moti Yung	Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes.	ICALP	2002	DBLP DOI BibTeX RDF
25	Hiroo Iwata, Hiroaki Yano, Ryo Kawamura	Array Force Display for Hardness Distribution.	Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems	2002	DBLP DOI BibTeX RDF
25	Ryan O'Donnell	Hardness amplification within NP.	STOC	2002	DBLP DOI BibTeX RDF
25	Subhash Khot	Hardness results for approximate hypergraph coloring.	STOC	2002	DBLP DOI BibTeX RDF
25	Guy Kortsarz, Robert Krauthgamer, James R. Lee	Hardness of Approximation for Vertex-Connectivity Network-Design Problems.	APPROX	2002	DBLP DOI BibTeX RDF
25	Sanjeev Khanna, Nathan Linial, Shmuel Safra	On the Hardness of Approximating the Chromatic Number.	Comb.	2000	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 68Q17, 68Q25, 68R10
25	Valentine Kabanets	Easiness Assumptions and Hardness Tests: Trading Time for Zero Error.	CCC	2000	DBLP DOI BibTeX RDF	probabilistic complexity classes, uniform setting, derandomization
25	Mikel Aldaz, Joos Heintz, Guillermo Matera, José Luis Montaña, Luis Miguel Pardo	Combinatorial Hardness Proofs for Polynomial Evaluation.	MFCS	1998	DBLP DOI BibTeX RDF
25	Mike Burmester, Yvo Desmedt, Yongge Wang	Using Approximation Hardness to Achieve Dependable Computation.	RANDOM	1998	DBLP DOI BibTeX RDF
25	Leonardo Vanneschi	Fitness landscapes and problem hardness in genetic programming.	GECCO (Companion)	2009	DBLP DOI BibTeX RDF	genetic programming, fitness landscapes, problem hardness
25	Anindya De, Luca Trevisan	Extractors Using Hardness Amplification.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF	Extractors, Direct product theorems, Hardness amplification
25	Matthew Andrews, Lisa Zhang	Almost-tight hardness of directed congestion minimization.	J. ACM	2008	DBLP DOI BibTeX RDF	Hardness of approximation, undirected graphs, congestion minimization
25	Omid Amini, David Peleg, Stéphane Pérennes, Ignasi Sau, Saket Saurabh 0001	Degree-Constrained Subgraph Problems: Hardness and Approximation Results.	WAOA	2008	DBLP DOI BibTeX RDF	Degree-Constrained Subgraphs, Apx, Excluded Minor, Approximation Algorithms, Hardness of Approximation, PTAS
25	Subhash Khot, Rishi Saket	On hardness of learning intersection of two halfspaces.	STOC	2008	DBLP DOI BibTeX RDF	learning, approximation, hardness, halfspaces
25	Omid Amini, Stéphane Pérennes, Ignasi Sau	Hardness and Approximation of Traffic Grooming.	ISAAC	2007	DBLP DOI BibTeX RDF	SONET ADM, Approximation Algorithms, Optical Networks, PTAS, inapproximability, Traffic Grooming, APX-hardness
25	Leonardo Vanneschi, Sébastien Vérel	Fitness landscapes and problem hardness in evolutionary computation.	GECCO (Companion)	2007	DBLP DOI BibTeX RDF	evolutionary algorithms, fitness landscapes, problem hardness
25	Matthew Andrews, Lisa Zhang	Logarithmic hardness of the directed congestion minimization problem.	STOC	2006	DBLP DOI BibTeX RDF	directed graphs, hardness of approximation, congestion minimization
25	Luca Trevisan	On uniform amplification of hardness in NP.	STOC	2005	DBLP DOI BibTeX RDF	amplification of hardness, average-case complexity
25	Matthew Andrews, Lisa Zhang	Hardness of the undirected congestion minimization problem.	STOC	2005	DBLP DOI BibTeX RDF	hardness of approximation, undirected graphs, congestion minimization
25	Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev 0001	A new multilayered PCP and the hardness of hypergraph vertex cover.	STOC	2003	DBLP DOI BibTeX RDF	hypergraph vertex cover, long code, multilayered PCP, hardness of approximation
25	Erez Petrank, Dror Rawitz	The hardness of cache conscious data placement.	POPL	2002	DBLP DOI BibTeX RDF	Cache conscious data placement, cache conscious code rearrangement, computational complexity, memory management, hardness of approximation
25	Christopher Umans	Hardness of Approximating Sigma2p Minimization Problems.	FOCS	1999	DBLP DOI BibTeX RDF	computational complexity, hardness of approximation, logic minimization, dispersers, polynomial hierarchy
25	Ilya Dumer, Daniele Micciancio, Madhu Sudan 0001	Hardness of Approximating the Minimum Distance of a Linear Code.	FOCS	1999	DBLP DOI BibTeX RDF	minimum distance problem, computational complexity, hardness of approximation, linear codes
25	Martin Fürer	Improved Hardness Results for Approximating the Chromatic Number.	FOCS	1995	DBLP DOI BibTeX RDF	hardness results, chromatic number approximation, geometric proof, randomized twisting method, amortized free bits, polynomial lower bounds, computational complexity, graph theory, NP-hard, polynomial time algorithm, chromatic number
25	Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk	The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations	FOCS	1993	DBLP DOI BibTeX RDF	approximate optima, NP-hard, lattices, codes, polynomial time algorithm, linear equations, interactive proof systems, hardness, set-cover problem, binary codes
25	Oded Goldreich 0001, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman	Security Preserving Amplification of Hardness	FOCS	1990	DBLP DOI BibTeX RDF	regular one-way function, security preserving amplification, weak one-way function, polynomial fraction, inverting algorithm, signatures, pseudorandom generators, hardness
25	Noam Nisan, Avi Wigderson	Hardness vs. Randomness (Extended Abstract)	FOCS	1988	DBLP DOI BibTeX RDF	pseudorandom bit generator, complexity class C, arbitrary function, lower bounds, randomness, hardness
22	Karthik C. S., Pasin Manurangsi	On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.	Electron. Colloquium Comput. Complex.	2024	DBLP BibTeX RDF
22	Nabeel Seedat, Fergus Imrie, Mihaela van der Schaar	Dissecting Sample Hardness: A Fine-Grained Analysis of Hardness Characterization Methods for Data-Centric AI.	CoRR	2024	DBLP DOI BibTeX RDF
22	Karthik C. S., Pasin Manurangsi	On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.	CoRR	2023	DBLP DOI BibTeX RDF
22	Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan	A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems.	ITCS	2023	DBLP DOI BibTeX RDF
22	Eran Malach, Shai Shalev-Shwartz	When Hardness of Approximation Meets Hardness of Learning.	J. Mach. Learn. Res.	2022	DBLP BibTeX RDF
22	Amey Bhangale, Subhash Khot	UG-hardness to NP-hardness by Losing Half.	Theory Comput.	2022	DBLP BibTeX RDF
22	Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan	A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems.	CoRR	2022	DBLP DOI BibTeX RDF
22	Tatiana Gomez, Patricio Fuentealba, Andrés Robles-Navarro, Carlos Cárdenas	Links among the Fukui potential, the alchemical hardness and the local hardness of an atom in a molecule.	J. Comput. Chem.	2021	DBLP DOI BibTeX RDF
22	Shuichi Hirahara	Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
22	Amir Mahdi Sadeghzadeh, Faezeh Dehghan, Amir Mohammad Sobhanian, Rasool Jalili	Hardness of Samples Is All You Need: Protecting Deep Learning Models Using Hardness of Samples.	CoRR	2021	DBLP BibTeX RDF
22	Shuichi Hirahara	Average-case hardness of NP from exponential worst-case hardness assumptions.	STOC	2021	DBLP DOI BibTeX RDF
22	Eran Malach, Shai Shalev-Shwartz	When Hardness of Approximation Meets Hardness of Learning.	CoRR	2020	DBLP BibTeX RDF
22	Tomonori Sawada, Hiroki Okawara, Daisuke Nakashima, Shuhei Iwabuchi, Morio Matsumoto, Masaya Nakamura, Takeo Nagura	Reliability of Trapezius Muscle Hardness Measurement: A Comparison between Portable Muscle Hardness Meter and Ultrasound Strain Elastography.	Sensors	2020	DBLP DOI BibTeX RDF
22	Amey Bhangale, Subhash Khot	UG-hardness to NP-hardness by Losing Half.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF
22	Amey Bhangale, Subhash Khot	UG-Hardness to NP-Hardness by Losing Half.	CCC	2019	DBLP DOI BibTeX RDF
22	Kosuke Higashi, Shogo Okamoto, Yoji Yamada, Hikaru Nagano, Masashi Konyo	Hardness Perception Through Tapping: Peak and Impulse of the Reaction Force Reflect the Subjective Hardness.	EuroHaptics (1)	2018	DBLP DOI BibTeX RDF
22	Kun Li, Ming Li 0056, Hao Chen 0060	A novel optimization hardness indicator based on the relationship between optimization hardness and frequency features of real-parameter problems.	Soft Comput.	2015	DBLP DOI BibTeX RDF
22	Virginia Vassilevska Williams	Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk).	IPEC	2015	DBLP DOI BibTeX RDF
22	Gabjong Han, Seungmoon Choi	Extended Rate-Hardness: A Measure for Perceived Hardness.	EuroHaptics (1)	2010	DBLP DOI BibTeX RDF
22	Miquel Torrent-Sucarrat, Pedro Salvador, Paul Geerlings, Miquel Solà	On the quality of the hardness kernel and the Fukui function to evaluate the global hardness.	J. Comput. Chem.	2007	DBLP DOI BibTeX RDF
22	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.	Theor. Comput. Sci.	1999	DBLP DOI BibTeX RDF
21	Ken-ichi Kawarabayashi, Bruce A. Reed	Odd cycle packing.	STOC	2010	DBLP DOI BibTeX RDF	odd cycle, packing
21	Michael Bauland, Edith Hemaspaandra	Isomorphic Implication.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Computational complexity, Constraints, Propositional logic, Logic in computer science, Isomorphism problem
21	Martin Hoefer 0001, Lars Olbrich, Alexander Skopalik	Doing Good with Spam Is Hard.	SAGT	2009	DBLP DOI BibTeX RDF
21	Calin Anton, Lane Olson	Generating Satisfiable SAT Instances Using Random Subgraph Isomorphism.	Canadian AI	2009	DBLP DOI BibTeX RDF
21	Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe	The shield that never was: societies with single-peaked preferences are more open to manipulation and control.	TARK	2009	DBLP DOI BibTeX RDF
21	Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, Hoeteck Wee	Improved Non-committing Encryption with Applications to Adaptively Secure Protocols.	ASIACRYPT	2009	DBLP DOI BibTeX RDF	adaptive corruption, non-committing encryption, public-key encryption, secure multi-party computation
21	Yingchao Zhao 0001, Wei Chen 0013, Shang-Hua Teng	The Isolation Game: A Game of Distances.	ISAAC	2008	DBLP DOI BibTeX RDF
21	Dana Moshkovitz, Ran Raz	Two Query PCP with Sub-Constant Error.	FOCS	2008	DBLP DOI BibTeX RDF
21	Chandra Chekuri, Sanjeev Khanna	Edge-disjoint paths revisited.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	multicommodity flow relaxation, approximation algorithm, greedy algorithm, Edge-disjoint paths
21	Alexis Maciel, Toniann Pitassi	Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives.	LICS	2006	DBLP DOI BibTeX RDF
21	Subhash Khot, Nisheeth K. Vishnoi	The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1.	FOCS	2005	DBLP DOI BibTeX RDF
21	Yoshifumi Kitamura, Ken'ichi Douko, Makoto Kitayama, Fumio Kishino	Object deformation and force feedback for virtual chopsticks.	VRST	2005	DBLP DOI BibTeX RDF	virtual chopsticks, virtual environment, deformation, force feedback, object manipulation, FEM
21	Michael Bauland, Edith Hemaspaandra	Isomorphic Implication.	MFCS	2005	DBLP DOI BibTeX RDF
21	Jirí Srba	Strong bisimilarity of simple process algebras: complexity lower bounds.	Acta Informatica	2003	DBLP DOI BibTeX RDF
21	Chandra Chekuri, Sanjeev Khanna	Edge disjoint paths revisited.	SODA	2003	DBLP BibTeX RDF
21	Guy Kortsarz, Sunil M. Shende	Approximating the Achromatic Number Problem on Bipartite Graphs.	ESA	2003	DBLP DOI BibTeX RDF
21	Rune B. Lyngsø, Christian N. S. Pedersen	Complexity of Comparing Hidden Markov Models.	ISAAC	2001	DBLP DOI BibTeX RDF
21	Christopher L. Barrett, Riko Jacob, Madhav V. Marathe	Formal Language Constrained Path Problems.	SWAT	1998	DBLP DOI BibTeX RDF
21	Matthew Andrews, Lisa Zhang	Complexity of wavelength assignment in optical network optimization.	IEEE/ACM Trans. Netw.	2009	DBLP DOI BibTeX RDF	approximation algorithms, optical networking, hardness of approximation, routing and wavelength assignment
21	Eyal Kushilevitz, Enav Weinreb	On the complexity of communication complexity.	STOC	2009	DBLP DOI BibTeX RDF	protocol tree, lower bounds, communication complexity, hardness of approximation, pseudo random functions
21	Rong Ge 0002, Martin Ester, Byron J. Gao, Zengjian Hu, Binay K. Bhattacharya, Boaz Ben-Moshe	Joint cluster analysis of attribute data and relationship data: The connected k-center problem, algorithms and applications.	ACM Trans. Knowl. Discov. Data	2008	DBLP DOI BibTeX RDF	Attribute data, joint cluster analysis, relationship data, approximation algorithms, NP-hardness, document clustering, community identification, market segmentation
21	Julia Chuzhoy, Anupam Gupta 0001, Joseph Naor, Amitabh Sinha	On the approximability of some network design problems.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	cost-distance, fixed charge network flow, priority Steiner tree, network design, Hardness of approximation
21	Joseph Cheriyan, Mohammad R. Salavatipour	Packing element-disjoint steiner trees.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	element-disjoint, approximation algorithms, Steiner trees, hardness of approximation, Packing
21	Rong Ge 0002, Martin Ester, Wen Jin, Ian Davidson	Constraint-driven clustering.	KDD	2007	DBLP DOI BibTeX RDF	clustering, constraints, NP-hardness
21	Ran Canetti, Ronald L. Rivest, Madhu Sudan 0001, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee	Amplifying Collision Resistance: A Complexity-Theoretic Treatment.	CRYPTO	2007	DBLP DOI BibTeX RDF	hash functions, combiners, collision resistance, hardness amplification
21	Guido Proietti, Peter Widmayer	Partitioning the Nodes of a Graph to Minimize the Sum of Subgraph Radii.	ISAAC	2006	DBLP DOI BibTeX RDF	Clustering problems, Graph radius, NP-hardness, Graph partition, Facility location problems
21	Oded Regev 0001, Ricky Rosen	Lattice problems and norm embeddings.	STOC	2006	DBLP DOI BibTeX RDF	embedding, lattices, norms, hardness of approximation
21	Guillaume Blin, Hélène Touzet	How to Compare Arc-Annotated Sequences: The Alignment Hierarchy.	SPIRE	2006	DBLP DOI BibTeX RDF	arc-annotated sequences, algorithm, NP-hardness, computational biology, edit distance, RNA structures
21	Gabriele Di Stefano, Stefan Krause, Marco E. Lübbecke, Uwe T. Zimmermann	On Minimum k-Modal Partitions of Permutations.	LATIN	2006	DBLP DOI BibTeX RDF	monotone sequence, k-modal sequence, cocoloring, approximation algorithm, online algorithm, Mixed integer program, hardness, LP rounding
21	Bertrand M. T. Lin, T. C. Edwin Cheng	Two-Machine Flowshop Batching and Scheduling.	Ann. Oper. Res.	2005	DBLP DOI BibTeX RDF	strong NP-hardness, heuristics, lower bound, makespan, batch processing, production scheduling, flowshop
21	Emanuele Viola	On Constructing Parallel Pseudorandom Generators from One-Way Functions.	CCC	2005	DBLP DOI BibTeX RDF	Pseudorandom generator construction, one-way function, black-box, restriction, constant-depth circuit, noise sensitivity, hardness amplification
21	Oded Regev 0001	New lattice-based cryptographic constructions.	J. ACM	2004	DBLP DOI BibTeX RDF	average-case hardness, cryptography, quantum computing, Lattice, public key encryption
21	Wenci Yu, Han Hoogeveen, Jan Karel Lenstra	Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard.	J. Sched.	2004	DBLP DOI BibTeX RDF	intermediate delays, strong NP-hardness, computational complexity, makespan, flow shop scheduling
21	Bang Ye Wu	Constructing the Maximum Consensus Tree from Rooted Triples.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	algorithms, dynamic programming, NP-hardness, computational biology, evolutionary trees
21	Davide Bilò, Guido Proietti	Augmenting the Edge-Connectivity of a Spider Tree.	ISAAC	2004	DBLP DOI BibTeX RDF	Edge-Connectivity Augmentation, Spider Tress, Graph Algorithms, NP-hardness, Network Survivability
21	Joseph S. B. Mitchell, Micha Sharir	New results on shortest paths in three dimensions.	SCG	2004	DBLP DOI BibTeX RDF	shortest path, NP-hardness, motion planning, terrain
21	Rolf Niedermeier	Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms.	MFCS	2004	DBLP DOI BibTeX RDF	NP-hardness, parameterization, parameterized complexity, fixed-parameter algorithms
21	Michael Elkin	Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem.	STOC	2004	DBLP DOI BibTeX RDF	minimum spanning tree, hardness of approximation
21	Thomas Eiter, Kazuhisa Makino	Abduction and the Dualization Problem.	Discovery Science	2003	DBLP DOI BibTeX RDF	monotone dualization, Horn functions, polynomial total-time computation, NP-hardness, Abduction, model-based reasoning, hypergraph transversals