Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
14	Chung-Hui Chen, Chih-Jen Liu	A Study of Screen Printability of UV Soy Ink on Plastics.	CSSE (6)	2008	DBLP DOI BibTeX RDF
14	Amit Chakrabarti, Graham Cormode, Andrew McGregor 0001	Robust lower bounds for communication and stream computation.	STOC	2008	DBLP DOI BibTeX RDF	lower bounds, data streams, communication complexity
14	Anup Rao 0001	Parallel repetition in projection games and a concentration bound.	STOC	2008	DBLP DOI BibTeX RDF	chsh game, parallel repetition, unique games conjecture
14	Chris Peikert, Brent Waters	Lossy trapdoor functions and their applications.	STOC	2008	DBLP DOI BibTeX RDF	public key encryption, trapdoor functions
14	Prasad Raghavendra	Optimal algorithms and inapproximability results for every CSP?	STOC	2008	DBLP DOI BibTeX RDF	dictatorship tests, rounding schemes, semidefinite programming, constraint satisfaction problem, unique games conjecture
14	Omkant Pandey, Rafael Pass, Vinod Vaikuntanathan	Adaptive One-Way Functions and Applications.	CRYPTO	2008	DBLP DOI BibTeX RDF	Cryptographic Assumptions, Non-malleable Commitment, Non-malleable Zero-knowledge
14	Sylvain Guillemot	Parameterized Complexity and Approximability of the SLCS Problem.	IWPEC	2008	DBLP DOI BibTeX RDF
14	Liqun Chen 0002, Zhaohui Cheng, Nigel P. Smart	Identity-based key agreement protocols from pairings.	Int. J. Inf. Sec.	2007	DBLP DOI BibTeX RDF	Identity based Crytography, Pairings
14	Luca Trevisan, Salil P. Vadhan	Pseudorandomness and Average-Case Complexity Via Uniform Reductions.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	Subject classification, 68Q10
14	Eu-Jin Goh, Stanislaw Jarecki, Jonathan Katz, Nan Wang 0001	Efficient Signature Schemes with Tight Reductions to the Diffie-Hellman Problems.	J. Cryptol.	2007	DBLP DOI BibTeX RDF
14	Hans-Joachim Böckenhauer, Juraj Hromkovic, Joachim Kneis, Joachim Kupke 0002	The Parameterized Approximability of TSP with Deadlines.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
14	Wei Wu 0001, Yi Mu 0001, Willy Susilo, Xinyi Huang 0001	Provably Secure Identity-Based Undeniable Signatures with Selective and Universal Convertibility.	Inscrypt	2007	DBLP DOI BibTeX RDF	Provable Security, Undeniable Signatures, Identity-based, Convertible
14	Amos Beimel, Renen Hallak, Kobbi Nissim	Private Approximation of Clustering and Vertex Cover.	TCC	2007	DBLP DOI BibTeX RDF
14	Dariusz Lipinski, Jerzy Ratajski	Modeling of Microhardness Profile in Nitriding Processes Using Artificial Neural Network.	ICIC (2)	2007	DBLP DOI BibTeX RDF	nitriding, microhardness, neural network, modeling
14	Akinori Kawachi, Keisuke Tanaka, Keita Xagawa	Multi-bit Cryptosystems Based on Lattice Problems.	Public Key Cryptography	2007	DBLP DOI BibTeX RDF
14	Carlos D. Toledo-Suárez, Manuel Valenzuela-Rendón, Hugo Terashima-Marín, Eduardo Uresti-Charre	On the relativity in the assessment of blind optimization algorithms and the problem-algorithm coevolution.	GECCO	2007	DBLP DOI BibTeX RDF	algorithmic assessment, blind search, coevolution
14	David Kempe 0001, Adam Meyerson, Nainesh Solanki, Ramnath K. Chellappa	Pricing of partially compatible products.	EC	2007	DBLP DOI BibTeX RDF	duopoly, graph, pricing, compatibility, cut
14	Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown	: The Design and Analysis of an Algorithm Portfolio for SAT.	CP	2007	DBLP DOI BibTeX RDF
14	Paul Medvedev, Konstantinos Georgiou, Gene Myers, Michael Brudno	Computability of Models for Sequence Assembly.	WABI	2007	DBLP DOI BibTeX RDF
14	Leonardo Vanneschi, Marco Tomassini, Philippe Collard, Sébastien Vérel, Yuri Pirola, Giancarlo Mauri	A Comprehensive View of Fitness Landscapes with Neutrality and Fitness Clouds.	EuroGP	2007	DBLP DOI BibTeX RDF
14	Daniel R. L. Brown, Kristian Gjøsteen	A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator.	CRYPTO	2007	DBLP DOI BibTeX RDF	Elliptic Curve Cryptography, Random Number Generation
14	Michael R. Fellows, Jens Gramm, Rolf Niedermeier	On The Parameterized Intractability Of Motif Search Problems.	Comb.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 03D15, 68Q17, 68Q25
14	Sylvain Guillemot	Parameterized Problems on Coincidence Graphs.	ISAAC	2006	DBLP DOI BibTeX RDF
14	Patrick Briest, Piotr Krysta	Single-minded unlimited supply pricing on sparse instances.	SODA	2006	DBLP DOI BibTeX RDF
14	Heiner Ackermann, Heiko Röglin, Berthold Vöcking	On the Impact of Combinatorial Structure on Congestion Games.	FOCS	2006	DBLP DOI BibTeX RDF
14	Uriel Feige, Jan Vondrák	Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.	FOCS	2006	DBLP DOI BibTeX RDF
14	Vadim Lyubashevsky, Daniele Micciancio	Generalized Compact Knapsacks Are Collision Resistant.	ICALP (2)	2006	DBLP DOI BibTeX RDF
14	Iftach Haitner, Danny Harnik, Omer Reingold	Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions.	ICALP (2)	2006	DBLP DOI BibTeX RDF
14	Alexander Grigoriev, Joyce van Loon, René Sitters, Marc Uetz	How to Sell a Graph: Guidelines for Graph Retailers.	WG	2006	DBLP DOI BibTeX RDF	Pricing problems, tollbooth problem, highway problem, computational complexity, dynamic programming, fully polynomial time approximation scheme
14	Gaurav Sharma 0002, Ness B. Shroff, Ravi R. Mazumdar	Maximum Weighted Matching with Interference Constraints.	PerCom Workshops	2006	DBLP DOI BibTeX RDF
14	Ron Steinfeld, Josef Pieprzyk, Huaxiong Wang	On the Provable Security of an Efficient RSA-Based Pseudorandom Generator.	ASIACRYPT	2006	DBLP DOI BibTeX RDF
14	Osher Yadgar, Sarit Kraus	Coverage Density as a Dominant Property of Large-Scale Sensor Networks.	CIA	2006	DBLP DOI BibTeX RDF
14	Russell Impagliazzo	Can every randomized algorithm be derandomized?	STOC	2006	DBLP DOI BibTeX RDF	algebraic circuit complexity, probabilistic algorithms, derandomization, circuit complexity, complexity classes, pseudo-randomness
14	Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider	Clique-width minimization is NP-hard.	STOC	2006	DBLP DOI BibTeX RDF	absolute approximation, NP-completeness, clique-width, pathwidth
14	Leonardo Vanneschi, Marco Tomassini, Philippe Collard, Sébastien Vérel	Negative Slope Coefficient: A Measure to Characterize Genetic Programming Fitness Landscapes.	EuroGP	2006	DBLP DOI BibTeX RDF
14	Iyad A. Kanj, Luay Nakhleh, Ge Xia	Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms.	COCOON	2006	DBLP DOI BibTeX RDF
14	Albert Atserias	Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries.	CCC	2006	DBLP DOI BibTeX RDF
14	R. C. Chakinala, Abishek Kumarasubramanian, Kofi A. Laing, R. Manokaran, C. Pandu Rangan, Rajmohan Rajaraman	Playing push vs pull: models and algorithms for disseminating dynamic data in networks.	SPAA	2006	DBLP DOI BibTeX RDF	push & pull, approximation algorithms, NP-Completeness, network design, data dissemination, multicast tree
14	Matthew Hamilton, Rhonda Chaytor, Todd Wareham	The Parameterized Complexity of Enumerating Frequent Itemsets.	IWPEC	2006	DBLP DOI BibTeX RDF
14	Emanuele Viola	The complexity of constructing pseudorandom generators from hard functions.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q01, Subject classification
14	Carla P. Gomes, Cèsar Fernández, Bart Selman, Christian Bessière	Statistical Regimes Across Constrainedness Regions.	Constraints An Int. J.	2005	DBLP DOI BibTeX RDF	runtime distributions, typical case analysis, phase transitions, heavy-tailed distributions, backtrack search
14	Lan Liu 0001, Xi Chen 0001, Jing Xiao, Tao Jiang 0001	Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem.	ISAAC	2005	DBLP DOI BibTeX RDF	L-reduction, positive result, negative result, bounded number, mates, complexity, approximation, children, SNP, recombinant, Haplotyping, pedigree
14	Edith Elkind, Helger Lipmaa	Small Coalitions Cannot Manipulate Voting.	Financial Cryptography	2005	DBLP DOI BibTeX RDF	vote manipulation, Electronic voting, one-way functions
14	Juanhua Su, Hejun Li, Qiming Dong, Ping Liu	Modelling of Rolling and Aging Processes in Copper Alloy by Levenberg-Marquardt BP Algorithm.	ICNC (2)	2005	DBLP DOI BibTeX RDF
14	Lincong Wang, Ramgopal R. Mettu, Bruce Randall Donald	An Algebraic Geometry Approach to Protein Structure Determination from NMR Data.	CSB	2005	DBLP DOI BibTeX RDF
14	Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami	Computational Indistinguishability Between Quantum States and Its Cryptographic Application.	EUROCRYPT	2005	DBLP DOI BibTeX RDF
14	Manfred K. Warmuth, S. V. N. Vishwanathan	Leaving the Span.	COLT	2005	DBLP DOI BibTeX RDF
14	Ryo Yoshinaka	Higher-Order Matching in the Linear Lambda Calculus in the Absence of Constants Is NP-Complete.	RTA	2005	DBLP DOI BibTeX RDF
14	Oded Regev 0001	On lattices, learning with errors, random linear codes, and cryptography.	STOC	2005	DBLP DOI BibTeX RDF	cryptography, quantum computing, lattices, public key encryption, computational learning theory, statistical queries
14	Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos	Low-distortion embeddings of general metrics into the line.	STOC	2005	DBLP DOI BibTeX RDF	approxiation algorithms, metric embeddings
14	Adam Cannon, Lenore Cowen	Approximation Algorithms for the Class Cover Problem.	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	disk cover, margin classifier, classification, approximation algorithms, set cover
14	Staal Amund Vinterbo	Privacy: A Machine Learning View.	IEEE Trans. Knowl. Data Eng.	2004	DBLP DOI BibTeX RDF
14	Kaoru Kurosawa, Swee-Huay Heng	From Digital Signature to ID-based Identification/Signature.	Public Key Cryptography	2004	DBLP DOI BibTeX RDF	GDH group, signature scheme, ID-based cryptography, identification scheme
14	Carla P. Gomes, Cèsar Fernández, Bart Selman, Christian Bessiere	Statistical Regimes Across Constrainedness Regions.	CP	2004	DBLP DOI BibTeX RDF
14	Benoît Libert, Jean-Jacques Quisquater	Improved Signcryption from q-Diffie-Hellman Problems.	SCN	2004	DBLP DOI BibTeX RDF	provable security, bilinear maps, signcryption
14	Rafael Pass	Bounded-concurrent secure multi-party computation with a dishonest majority.	STOC	2004	DBLP DOI BibTeX RDF	constant-round protocols, simulation-sound zero-knowledge, secure multi-party computation, concurrent composition
14	Uriel Feige, Daniel Reichman 0001	On Systems of Linear Equations with Two Variables per Equation.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
14	Moses Charikar, Venkatesan Guruswami, Anthony Wirth	Clustering with Qualitative Information.	FOCS	2003	DBLP DOI BibTeX RDF
14	Marcin Rychlik	On Probabilistic Quantified Satisfability Games.	MFCS	2003	DBLP DOI BibTeX RDF
14	Miroslav Chlebík, Janka Chlebíková	Inapproximability Results for Bounded Variants of Optimization Problems.	FCT	2003	DBLP DOI BibTeX RDF
14	Vincent Conitzer, Tuomas Sandholm	Automated mechanism design: complexity results stemming from the single-agent setting.	ICEC	2003	DBLP DOI BibTeX RDF	automated mechanism design, game theory
14	Evangelos Kranakis, Paolo Penna, Konrad Schlude, David Scot Taylor, Peter Widmayer	Improving Customer Proximity to Railway Stations.	CIAC	2003	DBLP DOI BibTeX RDF
14	Eu-Jin Goh, Stanislaw Jarecki	A Signature Scheme as Secure as the Diffie-Hellman Problem.	EUROCRYPT	2003	DBLP DOI BibTeX RDF	Computational Diffie-Hellman, Discrete Logarithm, Random Oracle Model, Signature Schemes, Exact Security, Tight Reductions
14	Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin	Secure Applications of Pedersen's Distributed Key Generation Protocol.	CT-RSA	2003	DBLP DOI BibTeX RDF	distributed key generation, discrete logarithm, random oracle model, Threshold cryptography, exact security
14	Louigi Addario-Berry, Benny Chor, Michael T. Hallett, Jens Lagergren, Alessandro Panconesi, Todd Wareham	Ancestral Maximum Likelihood of Evolutionary Trees Is Hard.	WABI	2003	DBLP DOI BibTeX RDF
14	Béla Csaba, Marek Karpinski, Piotr Krysta	Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems.	SODA	2002	DBLP BibTeX RDF
14	Dimitris Fotakis 0001, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis	The Structure and Complexity of Nash Equilibria for a Selfish Routing Game.	ICALP	2002	DBLP DOI BibTeX RDF
14	Petr Jancar, Antonín Kucera 0001, Faron Moller, Zdenek Sawa	Equivalence-Checking with One-Counter Automata: A Generic Method for Proving Lower Bounds.	FoSSaCS	2002	DBLP DOI BibTeX RDF
14	Jonathan Katz, Moti Yung	Threshold Cryptosystems Based on Factoring.	ASIACRYPT	2002	DBLP DOI BibTeX RDF
14	Craig Gentry, Michael Szydlo	Cryptanalysis of the Revised NTRU Signature Scheme.	EUROCRYPT	2002	DBLP DOI BibTeX RDF	NSS, NTRUSign, Orthogonal Lattice, Cyclotomic Integer, Galois Congruence, Cryptanalysis, Signature Scheme, Lattice Reduction, NTRU
14	Michael R. Fellows, Jens Gramm, Rolf Niedermeier	On the Parameterized Intractability of CLOSEST SUBSTRINGsize and Related Problems.	STACS	2002	DBLP DOI BibTeX RDF
14	Subhash Khot	On the power of unique 2-prover 1-round games.	STOC	2002	DBLP DOI BibTeX RDF
14	Christopher Umans	Pseudo-random generators for all hardnesses.	STOC	2002	DBLP DOI BibTeX RDF
14	Uriel Feige	Relations between average case complexity and approximation complexity.	STOC	2002	DBLP DOI BibTeX RDF
14	Luca Trevisan, Salil P. Vadhan	Pseudorandomness and Average-Case Complexity via Uniform Reductions.	CCC	2002	DBLP DOI BibTeX RDF
14	Chin Soon Lee, Neil D. Jones, Amir M. Ben-Amram	The size-change principle for program termination.	POPL	2001	DBLP DOI BibTeX RDF	omega automaton, program analysis, termination, partial evaluation, PSPACE-completeness
14	Avrim Blum, Adam Kalai, Jon M. Kleinberg	Admission Control to Minimize Rejections.	WADS	2001	DBLP DOI BibTeX RDF
14	Elchanan Mossel, Christopher Umans	On the Complexity of Approximating the VC Dimension.	CCC	2001	DBLP DOI BibTeX RDF
14	Christian Cachin, Jan Camenisch, Joe Kilian, Joy Müller	One-Round Secure Computation and Secure Autonomous Mobile Agents.	ICALP	2000	DBLP DOI BibTeX RDF
14	Michael Elkin, David Peleg	Strong Inapproximability of the Basic k-Spanner Problem.	ICALP	2000	DBLP DOI BibTeX RDF
14	Dagmar Handke, Guy Kortsarz	Tree Spanners for Subgraphs and Related Tree Covering Problems.	WG	2000	DBLP DOI BibTeX RDF
14	Richard Nock	Complexity in the Case against Accuracy: When Building one Function-Free Horn Clause is as Hard as Any.	ALT	1999	DBLP DOI BibTeX RDF
14	Jin-yi Cai	Some Recent Progress on the Complexity of Lattice Problems.	CCC	1999	DBLP DOI BibTeX RDF
14	Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi	Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.	MFCS	1998	DBLP DOI BibTeX RDF
14	Sergei G. Vorobyov	Subtyping Functional+Nonempty Record Types.	CSL	1998	DBLP DOI BibTeX RDF
14	Fritz Henglein, Jakob Rehof	The Complexity of Subtype Entailment for Simple Types.	LICS	1997	DBLP DOI BibTeX RDF	subtype entailment complexity, atomic entailment, coNP-completeness, complexity-theoretic marker, exponential explosion, subtype inference, structural complexity bounds, computability, satisfiability, axiomatization, linear-time algorithm
14	Edith Hemaspaandra, Gerd Wechsung	The Minimization Problem for Boolean Formulas.	FOCS	1997	DBLP DOI BibTeX RDF	computational complexity, minimization, propositional logic, Boolean formulas, polynomial hierarchy
14	Ulrik Brandes, Dagmar Handke	NP-Completness Results for Minimum Planar Spanners.	WG	1997	DBLP DOI BibTeX RDF
14	Mihir Bellare, Daniele Micciancio	A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Cost.	EUROCRYPT	1997	DBLP DOI BibTeX RDF
14	Joan Feigenbaum, Martin Strauss 0001	An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract).	STACS	1997	DBLP DOI BibTeX RDF
14	Ulrike Schultze, Richard J. Boland Jr.	Hard and Soft Information Genres: An Analysis of two Notes Databases.	HICSS (6)	1997	DBLP DOI BibTeX RDF
14	Cynthia A. Phillips, Clifford Stein 0001, Joel Wein	Task Scheduling in Networks (Extended Abstract).	SWAT	1994	DBLP DOI BibTeX RDF
14	Bhaskar DasGupta, Hava T. Siegelmann, Eduardo D. Sontag	On a Learnability Question Associated to Neural Networks with Continuous Activations (Extended Abstract).	COLT	1994	DBLP DOI BibTeX RDF
14	Tao Jiang 0001, Edward McDowell, Bala Ravikumar	The Structure and Complexity of Minimal NFA's over a Unary Alphabet.	FSTTCS	1991	DBLP DOI BibTeX RDF
14	Harry G. Mairson	Deciding ML Typability is Complete for Deterministic Exponential Time.	POPL	1990	DBLP DOI BibTeX RDF	ML
14	Kenneth W. Regan	A Uniform Reduction Theorem - Extending a Result of J. Grollmann and A. Selman.	ICALP	1986	DBLP DOI BibTeX RDF
14	Stavros S. Cosmadakis, Paris C. Kanellakis	Functional and Inclusion Dependencies: A Graph Theoretic Approach.	PODS	1984	DBLP DOI BibTeX RDF
14	Florian Berger, Rolf Klein	A traveller's problem.	SCG	2010	DBLP DOI BibTeX RDF	affine mappings, continuous dijkstra, frogger, pseudo-polynomial approximation, computational geometry, partition, np-hardness, motion planning, undecidability
14	Edgar Galván López, James McDermott, Michael O'Neill 0001, Anthony Brabazon	Towards an understanding of locality in genetic programming.	GECCO	2010	DBLP DOI BibTeX RDF	difficulty, genetic programming, locality, fitness landscape, neutrality, problem hardness
14	Yannis Smaragdakis, Christoph Csallner, Ranjith Subramanian	Scalable satisfiability checking and test data generation from modeling diagrams.	Autom. Softw. Eng.	2009	DBLP DOI BibTeX RDF	Modeling, Testing, Databases, NP-hardness, Test data generation, ORM, ORM-