Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
21	Oded Regev 0001	New lattice based cryptographic constructions.	STOC	2003	DBLP DOI BibTeX RDF	average-case hardness, cryptography, quantum computing, lattices, public key encryption
21	Thomas Eiter, Kazuhisa Makino	Generating All Abductive Explanations for Queries on Propositional Horn Theories.	CSL	2003	DBLP DOI BibTeX RDF	Horn theories, polynomial total time computation, NP-hardness, abduction, propositional logic, Computational logic
21	Xiaodong Wu 0001, Danny Z. Chen	Optimal Net Surface Problems with Applications.	ICALP	2002	DBLP DOI BibTeX RDF	3-D Image Segmentations, Algorithms, NP-hardness, Surface Reconstructions, Geometric Graphs
21	Ming-Yang Kao, Jared Samet, Wing-Kin Sung	The Enhanced Double Digest Problem for DNA Physical Mapping.	SWAT	2000	DBLP DOI BibTeX RDF	graph-theoretic techniques, NP-hardness, fast algorithms, physical mapping
21	Piotr Berman, Marek Karpinski	On Some Tighter Inapproximability Results (Extended Abstract).	ICALP	1999	DBLP DOI BibTeX RDF	Approximation Hardness, Bounded Dependency Satisfiability, Breakpoint Graphs, Node Cover, Approximation Algorithms, Independent Set, MAX-CUT, Sorting by Reversals
21	Maria Luisa Bonet, Toniann Pitassi, Ran Raz	No Feasible Interpolation for TC0-Frege Proofs.	FOCS	1997	DBLP DOI BibTeX RDF	TC/sup 0/-Frege proofs, feasible interpolation, complexity-theoretic assumption, hardness assumption, lower bounds, theorem proving, Chinese Remainder Theorem, proof systems
21	Sanghyun Ahn, David Hung-Chang Du	A Multicast Tree Algorithm Considering Maximum Delay Bound for Real-Time Applications.	LCN	1996	DBLP DOI BibTeX RDF	multicast tree algorithm, maximum delay bound, multiple multicast tree concept, tree maintenance cost, DBMT problem, shortest path tree-based DBMT, minimal Steiner tree-based DBMT, MST DBMT, SPT DBMT, performance analysis, group communication, NP-hardness, heuristic algorithms, real-time applications, multicast routing, telecommunication traffic, real-time traffic
21	Hemant D. Pande, William Landi, Barbara G. Ryder	Interprocedural Def-Use Associations for C Systems with Single Level Pointers.	IEEE Trans. Software Eng.	1994	DBLP DOI BibTeX RDF	interprocedural def-use associations, C software systems, single level pointers, value-setting statements, value-fetches, program-point-specific pointer-induced aliases, interprocedural reaching definitions problem, software engineering, computational complexity, data structures, static analysis, NP-hardness, program compilers, polynomial-time algorithm, program diagnostics, C language, indirection
18	Vikraman Arvind, Srikanth Srinivasan 0001	On the hardness of the noncommutative determinant.	STOC	2010	DBLP DOI BibTeX RDF	noncommutative rings, determinant, arithmetic circuits, permanent
18	Ola Svensson	Conditional hardness of precedence constrained scheduling on identical machines.	STOC	2010	DBLP DOI BibTeX RDF	scheduling, approximation, inapproximability
18	Zdenek Sawa, Petr Jancar	Hardness of equivalence checking for composed finite-state systems.	Acta Informatica	2009	DBLP DOI BibTeX RDF
18	Linqing Tang	Conditional Hardness of Approximating Satisfiable Max 3CSP-q.	ISAAC	2009	DBLP DOI BibTeX RDF
18	Jirí Matousek 0001, Martin Tancer, Uli Wagner 0001	Hardness of embedding simplicial complexes in Rd.	SODA	2009	DBLP DOI BibTeX RDF
18	Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, Salil P. Vadhan	On the complexity of differentially private data release: efficient algorithms and hardness results.	STOC	2009	DBLP DOI BibTeX RDF	exponential mechanism, privacy, cryptography, traitor tracing, differential privacy
18	Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko	On Hardness of Pricing Items for Single-Minded Bidders.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
18	Friedrich Eisenbrand, Thomas Rothvoß	New Hardness Results for Diophantine Approximation.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
18	Venkatesan Guruswami, Valentine Kabanets	Hardness Amplification via Space-Efficient Direct Products.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	94B35, 68Q25, 94B05, 68P30, Subject classification. 68Q17
18	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q30, 68Q17, Subject classification. 68Q15
18	Ning Chen, Atri Rudra	Walrasian Equilibrium: Hardness, Approximations and Tractable Instances.	Algorithmica	2008	DBLP DOI BibTeX RDF	Walrasian equilibrium, Single-minded auction, Approximation, NP-hard, Combinatorial auction
18	Aggelos Kiayias, Moti Yung	Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
18	Dan Tsafrir, Tomer Hertz, David A. Wagner 0001, Dilma Da Silva	Portably solving file races with hardness amplification.	ACM Trans. Storage	2008	DBLP DOI BibTeX RDF	TOCTTOU, time-of-check-to-time-of-use, Race conditions
18	Hans Raj Tiwary	On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes.	Discret. Comput. Geom.	2008	DBLP DOI BibTeX RDF	Extended convex hull, Polytope intersection, Polytopes, Turing reduction, Minkowski addition
18	Luca Pulina, Armando Tacchella	Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings.	LPAR	2008	DBLP DOI BibTeX RDF
18	Guy Kindler, Assaf Naor, Gideon Schechtman	The UGC hardness threshold of the ℓp Grothendieck problem.	SODA	2008	DBLP BibTeX RDF
18	Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier	Parameterized Algorithms and Hardness Results for Some Graph Motif Problems.	CPM	2008	DBLP DOI BibTeX RDF
18	Jin-yi Cai, Pinyan Lu, Mingji Xia	Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.	FOCS	2008	DBLP DOI BibTeX RDF
18	Christos H. Papadimitriou, Michael Schapira, Yaron Singer	On the Hardness of Being Truthful.	FOCS	2008	DBLP DOI BibTeX RDF
18	Ladjel Bellatreche, Kamel Boukhalfa, Pascal Richard	Data Partitioning in Data Warehouses: Hardness Study, Heuristics and ORACLE Validation.	DaWaK	2008	DBLP DOI BibTeX RDF
18	Akinori Kawachi, Keisuke Tanaka, Keita Xagawa	Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems.	ASIACRYPT	2008	DBLP DOI BibTeX RDF	concurrent security, ad hoc anonymous identification schemes, identification schemes, Lattice-based cryptography
18	Edgar Galván López, Stephen Dignum, Riccardo Poli	The Effects of Constant Neutrality on Performance and Problem Hardness in GP.	EuroGP	2008	DBLP DOI BibTeX RDF
18	Jon Conrad, Carla P. Gomes, Willem Jan van Hoeve, Ashish Sabharwal, Jordan Suter	Connections in Networks: Hardness of Feasibility Versus Optimality.	CPAIOR	2007	DBLP DOI BibTeX RDF
18	Andrej Bogdanov, Muli Safra	Hardness Amplification for Errorless Heuristics.	FOCS	2007	DBLP DOI BibTeX RDF
18	Matthew Cary, Atri Rudra, Ashish Sabharwal	Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics.	ICALP	2007	DBLP DOI BibTeX RDF
18	Benoît Larose, Pascal Tesson	Universal Algebra and Hardness Results for Constraint Satisfaction Problems.	ICALP	2007	DBLP DOI BibTeX RDF
18	Riccardo Poli, Leonardo Vanneschi	Fitness-proportional negative slope coefficient as a hardness measure for genetic algorithms.	GECCO	2007	DBLP DOI BibTeX RDF	negative slope coefficient, theory, problem difficulty
18	Jonathan Katz	Efficient Cryptographic Protocols Based on the Hardness of Learning Parity with Noise.	IMACC	2007	DBLP DOI BibTeX RDF
18	W. Chen, J. Meng	The Hardness of the Closest Vector Problem With Preprocessing Over ellinfty Norm.	IEEE Trans. Inf. Theory	2006	DBLP DOI BibTeX RDF
18	Virginia Vassilevska, Ryan Williams 0001, Shan Leung Maverick Woo	Confronting hardness using a hybrid approach.	SODA	2006	DBLP DOI BibTeX RDF
18	Refael Hassin, Jérôme Monnot, Danny Segev	Approximation Algorithms and Hardness Results for Labeled Connectivity Problems.	MFCS	2006	DBLP DOI BibTeX RDF
18	Adi Akavia, Oded Goldreich 0001, Shafi Goldwasser, Dana Moshkovitz	On basing one-way functions on NP-hardness.	STOC	2006	DBLP DOI BibTeX RDF	adaptive versus non-adaptive machines, reductions, one-way functions, interactive proof systems, average-case complexity
18	Ishay Haviv, Oded Regev 0001	Hardness of the Covering Radius Problem on Lattices.	CCC	2006	DBLP DOI BibTeX RDF
18	Irit Dinur, Oded Regev 0001, Clifford D. Smyth	The Hardness of 3-Uniform Hypergraph Coloring.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q17
18	Ran Canetti, Shai Halevi, Michael Steiner 0001	Hardness Amplification of Weakly Verifiable Puzzles.	TCC	2005	DBLP DOI BibTeX RDF
18	François Nicolas, Eric Rivals	Hardness of Optimal Spaced Seed Design.	CPM	2005	DBLP DOI BibTeX RDF
18	Paul Horton, Wataru Fujibuchi	An Upper Bound on the Hardness of Exact Matrix Based Motif Discovery.	CPM	2005	DBLP DOI BibTeX RDF
18	Yossi Borenstein, Riccardo Poli	Information landscapes and problem hardness.	GECCO	2005	DBLP DOI BibTeX RDF	genetic algorithm, theory, fitness landscape
18	Changyong Zhang, Robert Rodosek	Modelling and Constraint Hardness Characterisation of the Unique-Path OSPF Weight Setting Problem.	International Conference on Computational Science (1)	2005	DBLP DOI BibTeX RDF
18	Lars Engebretsen, Jonas Holmerin	More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.	STACS	2005	DBLP DOI BibTeX RDF
18	Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia	W-Hardness Under Linear FPT-Reductions: Structural Properties and Further Applications.	COCOON	2005	DBLP DOI BibTeX RDF
18	Venkatesan Guruswami, Subhash Khot	Hardness of Max 3SAT with No Mixed Clauses.	CCC	2005	DBLP DOI BibTeX RDF
18	Thomas Erlebach, Alexander Hall	NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost Flow.	J. Sched.	2004	DBLP DOI BibTeX RDF	approximation algorithm, NP-complete, inapproximability, resource augmentation, broadcast scheduling
18	Andreas Goerdt, André Lanka	On the Hardness and Easiness of Random 4-SAT Formulas.	ISAAC	2004	DBLP DOI BibTeX RDF
18	Yossi Borenstein, Riccardo Poli	Fitness Distributions and GA Hardness.	PPSN	2004	DBLP DOI BibTeX RDF
18	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness of Dominating Set Problems.	ESA	2004	DBLP DOI BibTeX RDF
18	María Isabel González Vasco, Mats Näslund, Igor E. Shparlinski	New Results on the Hardness of Diffie-Hellman Bits.	Public Key Cryptography	2004	DBLP DOI BibTeX RDF
18	Leonardo Vanneschi, Manuel Clergue, Philippe Collard, Marco Tomassini, Sébastien Vérel	Fitness Clouds and Problem Hardness in Genetic Programming.	GECCO (2)	2004	DBLP DOI BibTeX RDF
18	Subhash Khot	Hardness of Approximating the Shortest Vector Problem in High Lp Norms.	FOCS	2003	DBLP DOI BibTeX RDF
18	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness for Small Occurrence Instances of NP-Hard Problems.	CIAC	2003	DBLP DOI BibTeX RDF
18	Emanuele Viola	Hardness vs. Randomness within Alternating Time.	CCC	2003	DBLP DOI BibTeX RDF
18	Thomas Erlebach, Alexander Hall	NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow.	SODA	2002	DBLP BibTeX RDF
18	Irit Dinur, Oded Regev 0001, Clifford D. Smyth	The Hardness of 3 - Uniform Hypergraph Coloring.	FOCS	2002	DBLP DOI BibTeX RDF
18	Hans-Joachim Böckenhauer, Dirk Bongartz, Juraj Hromkovic, Ralf Klasing, Guido Proietti, Sebastian Seibert, Walter Unger	On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality.	FSTTCS	2002	DBLP DOI BibTeX RDF	minimum-cost biconnected spanning subgraph, Approximation algorithm, inapproximability, augmentation
18	Guy Kortsarz	On the Hardness of Approximating Spanners.	Algorithmica	2001	DBLP DOI BibTeX RDF
18	Uriel Feige	Coping with the NP-Hardness of the Graph Bandwidth Problem.	SWAT	2000	DBLP DOI BibTeX RDF
18	Valentina Colla, Leonardo Maria Reyneri, Mirko Sgarbi	Parametric Characterization of Hardness Profiles of Steels with Nero-Wavelet Networks.	IWANN (2)	1999	DBLP DOI BibTeX RDF
18	Sanjeev Arora, Carsten Lund, Rajeev Motwani 0001, Madhu Sudan 0001, Mario Szegedy	Proof Verification and the Hardness of Approximation Problems.	J. ACM	1998	DBLP DOI BibTeX RDF	optimization, NP-completeness, randomness, proof verification
18	Guy Kortsarz	On the Hardness of Approximation Spanners.	APPROX	1998	DBLP DOI BibTeX RDF
18	David P. Williamson	Gadgets, Approximation, and Linear Programming: Improved Hardness Results for Cut and Satisfiability Problems (Abstract of Invited Lecture).	WG	1997	DBLP DOI BibTeX RDF
18	Hartmut Klauck	On the Hardness of Global and Local Approximation.	SWAT	1996	DBLP DOI BibTeX RDF
18	Dan Boneh, Ramarathnam Venkatesan	Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes.	CRYPTO	1996	DBLP DOI BibTeX RDF
14	Mihai Patrascu	Towards polynomial lower bounds for dynamic problems.	STOC	2010	DBLP DOI BibTeX RDF	3SUM, lower bounds, dynamic data structures
14	Dániel Marx	Tractable hypergraph properties for constraint satisfaction and conjunctive queries.	STOC	2010	DBLP DOI BibTeX RDF	submodular width, constraint satisfaction, conjunctive queries, fixed-parameter tractability
14	Louise Moody, Alan Waterworth, John G. Arthur, Avril D. McCarthy III, Peter J. Harley, Rod H. Smallwood	Beyond the visuals: tactile augmentation and sensory enhancement in an arthroscopy simulator.	Virtual Real.	2009	DBLP DOI BibTeX RDF	Tactile augmentation, Sensory enhancement, Sensory illusion, Mixed reality, Surgical simulator
14	Decheng Dai, Rong Ge 0001	New Results on Simple Stochastic Games.	ISAAC	2009	DBLP DOI BibTeX RDF
14	Peng-Jun Wan	Multiflows in multihop wireless networks.	MobiHoc	2009	DBLP DOI BibTeX RDF	approximation algorithms, multicommodity flow, capacity region
14	Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant	On the complexity of Nash equilibria of action-graph games.	SODA	2009	DBLP DOI BibTeX RDF
14	Matthias Krause 0001, Dirk Stegemann	More on the Security of Linear RFID Authentication Protocols.	Selected Areas in Cryptography	2009	DBLP DOI BibTeX RDF	RFID Authentication, HB ?+?, CKK, CKK 2, Algebraic Attacks, Lightweight Cryptography
14	Kenji Inoue, Fuyuki Kato, Suwoong Lee	Haptic device using flexible sheet and air jet for presenting virtual lumps under skin.	IROS	2009	DBLP DOI BibTeX RDF
14	Refael Hassin, R. Ravi 0001, F. Sibel Salman	Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.	ESA	2009	DBLP DOI BibTeX RDF
14	Battista Biggio, Giorgio Fumera, Fabio Roli	Multiple Classifier Systems for Adversarial Classification Tasks.	MCS	2009	DBLP DOI BibTeX RDF
14	Vadim Lyubashevsky	Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures.	ASIACRYPT	2009	DBLP DOI BibTeX RDF
14	Mate Soos, Karsten Nohl, Claude Castelluccia	Extending SAT Solvers to Cryptographic Problems.	SAT	2009	DBLP DOI BibTeX RDF
14	Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann	On Making Directed Graphs Transitive.	WADS	2009	DBLP DOI BibTeX RDF
14	Leonardo Vanneschi, Andrea Valsecchi, Riccardo Poli	Limitations of the fitness-proportional negative slope coefficient as a difficulty measure.	GECCO	2009	DBLP DOI BibTeX RDF	fitness clouds, fitness-proportional negative slope coefficient, fitness landscapes, problem difficulty
14	Andreas Karrenbauer	Matching Techniques Ride to Rescue OLED Displays.	COCOA	2009	DBLP DOI BibTeX RDF
14	Chris Peikert	Public-key cryptosystems from the worst-case shortest vector problem: extended abstract.	STOC	2009	DBLP DOI BibTeX RDF	cryptography, lattices
14	Madhur Tulsiani	CSP gaps and reductions in the lasserre hierarchy.	STOC	2009	DBLP DOI BibTeX RDF	constraint satisfaction, semidefinite programming, integrality gaps
14	Vadim Lyubashevsky, Daniele Micciancio	On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem.	CRYPTO	2009	DBLP DOI BibTeX RDF
14	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	On Pseudorandom Generators with Linear Stretch in NC0.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 94A60, 68P25
14	Dimitris Fotakis 0001, Spyros C. Kontogiannis, Paul G. Spirakis	Atomic congestion games among coalitions.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	convergence to equilibria, price of anarchy, congestion games, Algorithmic game theory
14	Iyad A. Kanj, Luay Nakhleh, Ge Xia	The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms.	Algorithmica	2008	DBLP DOI BibTeX RDF	Parameterized algorithms and complexity, Linguistics, Phylogenetic networks
14	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the impact of combinatorial structure on congestion games.	J. ACM	2008	DBLP DOI BibTeX RDF	convergence, local search, Nash equilibria, Congestion games
14	Qi Cheng 0001	Hard Problems of Algebraic Geometry Codes.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
14	Basile Couëtoux, Laurent Gourvès, Jérôme Monnot, Orestis Telelis	On Labeled Traveling Salesman Problems.	ISAAC	2008	DBLP DOI BibTeX RDF
14	Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick	Entangled Games are Hard to Approximate.	FOCS	2008	DBLP DOI BibTeX RDF
14	Patrick Briest	Uniform Budgets and the Envy-Free Pricing Problem.	ICALP (1)	2008	DBLP DOI BibTeX RDF
14	Henri Gilbert, Matthew J. B. Robshaw, Yannick Seurin	How to Encrypt with the LPN Problem.	ICALP (2)	2008	DBLP DOI BibTeX RDF	LPN, error-correcting code, symmetric encryption
14	Vladimir Shpilrain, Alexander Ushakov	An Authentication Scheme Based on the Twisted Conjugacy Problem.	ACNS	2008	DBLP DOI BibTeX RDF
14	Venkatesan T. Chakaravarthy, Sambuddha Roy	Arthur and Merlin as Oracles.	MFCS	2008	DBLP DOI BibTeX RDF
14	Ariel Rabkin	Personal knowledge questions for fallback authentication: security questions in the era of Facebook.	SOUPS	2008	DBLP DOI BibTeX RDF	security, authentication, questions