Search results for "Intractability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
20	Marco Cadoli, Francesco M. Donini, Marco Schaerf	Is Intractability of Non-Monotonic Reasoning a Real Drawback?	AAAI	1994	DBLP BibTeX RDF
20	Stefan Lucks	How to Exploit the Intractability of Exact TSP for Cryptography.	FSE	1994	DBLP DOI BibTeX RDF
20	Lawrence P. Huang, Randal E. Bryant	Intractability in linear switch-level simulation.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	1993	DBLP DOI BibTeX RDF
20	Karl R. Abrahamson, Rodney G. Downey, Michael R. Fellows	Fixed-Parameter Intractability II (Extended Abstract).	STACS	1993	DBLP DOI BibTeX RDF
20	Yishay Mansour, Baruch Schieber	The Intractability of Bounded Protocols for On-Line Sequence Transmission over Non-FIFO Channels.	J. ACM	1992	DBLP DOI BibTeX RDF	non-FIFO channels, sequence transmission, lower bound, data link
20	Ramarathnam Venkatesan, Sivaramakrishnan Rajagopalan	Average Case Intractability of Matrix and Diophantine Problems (Extended Abstract)	STOC	1992	DBLP DOI BibTeX RDF
20	Rodney G. Downey, Michael R. Fellows	Fixed-Parameter Intractability.	SCT	1992	DBLP DOI BibTeX RDF
20	David J. Haglin, Shankar M. Venkatesan	Approximation and Intractability Results for the Maximum Cut Problem and its Variants.	IEEE Trans. Computers	1991	DBLP DOI BibTeX RDF
20	Osamu Watanabe 0001	On Intractability of the Class UP.	Math. Syst. Theory	1991	DBLP DOI BibTeX RDF
20	Neil V. Murray, Erik Rosenthal	Reexamining Intractability of Tableau Methods.	ISSAC	1990	DBLP DOI BibTeX RDF
20	Moon-Jung Chung, Bala Ravikumar	Strong Nondeterministic Turing Reduction - A Technique for Proving Intractability.	J. Comput. Syst. Sci.	1989	DBLP DOI BibTeX RDF
20	M. Stallman	Course outline: course announcement (Spring 1989) CSE/OR 691 I: Surviving Intractability.	SIGACT News	1989	DBLP DOI BibTeX RDF
20	Yishay Mansour, Baruch Schieber	The Intractability of Bounded Protocols for Non-FIFO Channels.	PODC	1989	DBLP DOI BibTeX RDF
20	Kaoru Kurosawa, Toshiya Itoh, Masashi Takeuchi	Public Key Cryptosystem using a reciprocal number with the same Intractability as Factoring a Large number.	Cryptologia	1988	DBLP DOI BibTeX RDF
20	Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson	Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions	STOC	1988	DBLP DOI BibTeX RDF
20	Kevin J. Compton, C. Ward Henson, Saharon Shelah	Nonconvergence, undecidability, and intractability in asymptotic problems.	Ann. Pure Appl. Log.	1987	DBLP DOI BibTeX RDF
20	Moon-Jung Chung, Bala Ravikumar	Strong nondeterministic reduction - a technique for proving intractability.	SCT	1987	DBLP BibTeX RDF
20	J. Fang, Gérard D. Cohen, Philippe Godlewski, Gerard Battail	On the Inherent Intractability of Soft Decision Decoding of Linear Codes.	Coding Theory and Applications	1986	DBLP DOI BibTeX RDF
20	Armin Haken	The Intractability of Resolution.	Theor. Comput. Sci.	1985	DBLP DOI BibTeX RDF
20	Howard A. Blair	The Intractability of Validity in Logic Programming and Dynamic Logic.	Logic of Programs	1983	DBLP DOI BibTeX RDF
20	M. R. Garey, David S. Johnson	Computers and Intractability: A Guide to the Theory of NP-Completeness.		1979	RDF
20	Elwyn R. Berlekamp, Robert J. McEliece, Henk C. A. van Tilborg	On the inherent intractability of certain coding problems (Corresp.).	IEEE Trans. Inf. Theory	1978	DBLP DOI BibTeX RDF
20	Leonard M. Adleman, Kenneth L. Manders	Reducibility, Randomness, and Intractability (Abstract)	STOC	1977	DBLP DOI BibTeX RDF
11	Nelson Antunes, Gonçalo Jacinto, António Pacheco 0001	An analytical framework to infer multihop path reliability in MANETs.	SIGMETRICS	2010	DBLP DOI BibTeX RDF	multihop path reliability, piecewise deterministic markov processes, mobility, mobile ad hoc networks, random walk
11	Gösta Grahne, Adrian Onet	Data correspondence, exchange and repair.	ICDT	2010	DBLP DOI BibTeX RDF
11	Shun'ichi Amano, Claire David, Leonid Libkin, Filip Murlak	On the tradeoff between mapping and querying power in XML data exchange.	ICDT	2010	DBLP DOI BibTeX RDF
11	Serge Abiteboul, T.-H. Hubert Chan, Evgeny Kharlamov, Werner Nutt, Pierre Senellart	Aggregate queries for discrete and continuous probabilistic XML.	ICDT	2010	DBLP DOI BibTeX RDF	XML, algorithms, complexity, aggregation, probabilistic databases
11	Jason D. Hartline, Brendan Lucier	Bayesian algorithmic mechanism design.	STOC	2010	DBLP DOI BibTeX RDF	Bayesian incentive compatibility, algorithms, mechanism design, social welfare
11	Evgeny Kharlamov, Werner Nutt, Pierre Senellart	Updating probabilistic XML.	EDBT/ICDT Workshops	2010	DBLP DOI BibTeX RDF	XML, complexity, updates, probabilistic databases
11	Edward R. Dougherty, Marcel Brun, Jeffrey M. Trent, Michael L. Bittner	Conditioning-Based Modeling of Contextual Genomic Regulation.	IEEE ACM Trans. Comput. Biol. Bioinform.	2009	DBLP DOI BibTeX RDF	Microarray, regulatory networks
11	Georg Gottlob, Zoltán Miklós 0001, Thomas Schwentick	Generalized hypertree decompositions: NP-hardness and tractable variants.	J. ACM	2009	DBLP DOI BibTeX RDF	TreeProjection Problem, hypertree decomposition, NP-complete, hypergraph, Conjunctive query, tractable, acyclic
11	Shengbao Wang, Zhenfu Cao, ZhaoHui Cheng, Kim-Kwang Raymond Choo	Perfect forward secure identity-based authenticated key agreement protocol in the escrow mode.	Sci. China Ser. F Inf. Sci.	2009	DBLP DOI BibTeX RDF	modular security proof, provable security, bilinear pairing, authenticated key agreement, perfect forward secrecy
11	Pierre Flener, Justin Pearson, Meinolf Sellmann, Pascal Van Hentenryck, Magnus Ågren 0002	Dynamic structural symmetry breaking for constraint satisfaction problems.	Constraints An Int. J.	2009	DBLP DOI BibTeX RDF	Dominance detection, CSP, Tractability, Symmetry breaking
11	Koray Kayabol, Ercan E. Kuruoglu, Bülent Sankur	Bayesian Separation of Images Modeled With MRFs Using MCMC.	IEEE Trans. Image Process.	2009	DBLP DOI BibTeX RDF
11	Wuping Chen, Lei Zhang 0009, Bo Qin, Qianhong Wu, Huanguo Zhang	Certificateless One-Way Authenticated Two-Party Key Agreement Protocol.	IAS	2009	DBLP DOI BibTeX RDF
11	Jin-yi Cai, Pinyan Lu, Mingji Xia	A Computational Proof of Complexity of Some Restricted Counting Problems.	TAMC	2009	DBLP DOI BibTeX RDF
11	Georg Gottlob, Gianluigi Greco, Bruno Marnette	HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results.	Graph Theory, Computational Intelligence and Thought	2009	DBLP DOI BibTeX RDF
11	Anne Benoit, Yves Robert, Arnold L. Rosenberg, Frédéric Vivien	Static strategies forworksharing with unrecoverable interruptions.	IPDPS	2009	DBLP DOI BibTeX RDF
11	Marc Pouzet, Pascal Raymond	Modular static scheduling of synchronous data-flow networks: an efficient symbolic representation.	EMSOFT	2009	DBLP DOI BibTeX RDF	real-time systems, compilation, semantics, np-completeness, partial orders, synchronous languages, block-diagrams, preorders
11	Jaakko Luttinen, Alexander Ilin, Juha Karhunen	Bayesian Robust PCA for Incomplete Data.	ICA	2009	DBLP DOI BibTeX RDF
11	Eike Kiltz, Krzysztof Pietrzak, Martijn Stam, Moti Yung	A New Randomness Extraction Paradigm for Hybrid Encryption.	EUROCRYPT	2009	DBLP DOI BibTeX RDF	hash proof systems, Chosen-ciphertext security, ElGamal, hybrid encryption, randomness extraction
11	Foto N. Afrati, Phokion G. Kolaitis	Repair checking in inconsistent databases: algorithms and complexity.	ICDT	2009	DBLP DOI BibTeX RDF	coNP-complete problem, equality-generating dependencies, repair checking, tuple-generating dependencies, weakly acyclic set, polynomial time, consistent query answering, inconsistent databases, database repairs
11	Marcelo Arenas, Pablo Barceló, Juan L. Reutter	Query languages for data exchange: beyond unions of conjunctive queries.	ICDT	2009	DBLP DOI BibTeX RDF
11	David A. Cohen, Martin James Green, Chris Houghton	Constraint Representations and Structural Tractability.	CP	2009	DBLP DOI BibTeX RDF
11	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
11	E. Allen Emerson	Model Checking: Progress and Problems.	VMCAI	2009	DBLP DOI BibTeX RDF
11	Yasunori Ishihara, Takuji Morimoto, Shougo Shimizu, Kenji Hashimoto, Toru Fujiwara	A Tractable Subclass of DTDs for XPath Satisfiability with Sibling Axes.	DBPL	2009	DBLP DOI BibTeX RDF
11	Benny Applebaum, David Cash, Chris Peikert, Amit Sahai	Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems.	CRYPTO	2009	DBLP DOI BibTeX RDF	Key-dependent message security, Learning problems, Encryption, Lattice-based cryptography
11	Sushmita Roy, Terran Lane, Margaret Werner-Washburne	Learning structurally consistent undirected probabilistic graphical models.	ICML	2009	DBLP DOI BibTeX RDF
11	Evgeny V. Shchepin, Nodari Vakhania	On the geometry, preemptions and complexity of multiprocessor and shop scheduling.	Ann. Oper. Res.	2008	DBLP DOI BibTeX RDF	Shop scheduling, Algorithm, Time complexity, Multiprocessor scheduling, Preemption
11	Felix Brandt 0001, Tuomas Sandholm	On the Existence of Unconditionally Privacy-Preserving Auction Protocols.	ACM Trans. Inf. Syst. Secur.	2008	DBLP DOI BibTeX RDF	auctions, multiparty computation
11	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
11	Dan Boneh, Xavier Boyen	Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups.	J. Cryptol.	2008	DBLP DOI BibTeX RDF	Digital signatures, Bilinear pairings, Standard model, Strong unforgeability
11	Ron M. Roth, Krishnamurthy Viswanathan	On the Hardness of Decoding the Gale-Berlekamp Code.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
11	Tanya G. Roosta, Martin J. Wainwright, Shankar S. Sastry	Convergence Analysis of Reweighted Sum-Product Algorithms.	IEEE Trans. Signal Process.	2008	DBLP DOI BibTeX RDF
11	David Lindley	The limits of computability.	Commun. ACM	2008	DBLP DOI BibTeX RDF
11	Carlos Aguilar Melchor, Benoît Crespin, Philippe Gaborit, Vincent Jolivet, Pierre Rousseau	High-Speed Private Information Retrieval Computation on GPU.	SECURWARE	2008	DBLP DOI BibTeX RDF
11	Paul G. Spirakis	Approximate Equilibria for Strategic Two Person Games.	SAGT	2008	DBLP DOI BibTeX RDF
11	Christos H. Papadimitriou	The Search for Equilibrium Concepts.	SAGT	2008	DBLP DOI BibTeX RDF
11	Nouha Oualha, Melek Önen, Yves Roudier	A Security Protocol for Self-Organizing Data Storage.	SEC	2008	DBLP DOI BibTeX RDF
11	Loreto Bravo, Wenfei Fan, Floris Geerts, Shuai Ma 0001	Increasing the Expressivity of Conditional Functional Dependencies without Extra Complexity.	ICDE	2008	DBLP DOI BibTeX RDF
11	Charu C. Aggarwal, Philip S. Yu	LOCUST: An Online Analytical Processing Framework for High Dimensional Classification of Data Streams.	ICDE	2008	DBLP DOI BibTeX RDF
11	Volker Haarslev, Hsueh-Ieng Pai, Nematollaah Shiri	Uncertainty Reasoning for Ontologies with General TBoxes in Description Logic.	URSW (LNCS Vol.)	2008	DBLP DOI BibTeX RDF
11	Fang Wei 0001, Georg Lausen	A unified apriori-like algorithm for conjunctive query containment.	IDEAS	2008	DBLP DOI BibTeX RDF
11	Venkatesan Guruswami	List Error-Correction with Optimal Information Rate (Invited Talk).	ICITS	2008	DBLP DOI BibTeX RDF
11	Shai Halevi, Steven A. Myers, Charles Rackoff	On Seed-Incompressible Functions.	TCC	2008	DBLP DOI BibTeX RDF
11	Roy Grønmo, Fredrik Sørensen, Birger Møller-Pedersen, Stein Krogdahl	Semantics-Based Weaving of UML Sequence Diagrams.	ICMT@TOOLS	2008	DBLP DOI BibTeX RDF
11	Benny Applebaum, Boaz Barak, David Xiao	On Basing Lower-Bounds for Learning on Worst-Case Assumptions.	FOCS	2008	DBLP DOI BibTeX RDF
11	Hubie Chen	Quantified Constraint Satisfaction and the Polynomially Generated Powers Property.	ICALP (2)	2008	DBLP DOI BibTeX RDF
11	Zhongjing Ma, Roland P. Malhamé, Peter E. Caines	Distributed control for radial loss network systems via the ash Certainty Equivalence (mean field) principle.	CDC	2008	DBLP DOI BibTeX RDF
11	Yingpeng Sang, Hong Shen 0001	Privacy preserving set intersection based on bilinear groups.	ACSC	2008	DBLP BibTeX RDF	non interactive zero-knowledge proof, cryptographic protocol, privacy preservation, set intersection, bilinear groups
11	Tomasz P. Michalak, Andrew James Dowell, Peter McBurney, Michael J. Wooldridge	Pre-processing Techniques for Anytime Coalition Structure Generation Algorithms.	KRAMAS	2008	DBLP DOI BibTeX RDF
11	Christian Colombo 0001, Gordon J. Pace, Gerardo Schneider	Dynamic Event-Based Runtime Monitoring of Real-Time and Contextual Properties.	FMICS	2008	DBLP DOI BibTeX RDF
11	Sanpawat Kantabutra, Pattama Longani	The Complexity of the Grid Wireless Mobility Model.	SNPD	2008	DBLP DOI BibTeX RDF	Wireless Mobility Model, Complexity
11	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
11	Yiling Wen, Jianfeng Ma 0001	An Aggregate Signature Scheme with Constant Pairing Operations.	CSSE (3)	2008	DBLP DOI BibTeX RDF
11	Eugénia Moreira Bernardino, Anabela Moreira Bernardino, Juan Manuel Sánchez-Pérez, Juan Antonio Gómez Pulido, Miguel A. Vega-Rodríguez	Solving the Terminal Assignment Problem Using a Local Search Genetic Algorithm.	DCAI	2008	DBLP DOI BibTeX RDF	Genetic Algorithm, Local Search Algorithm, Terminal Assignment Problem
11	Michael J. Jacobson Jr., Renate Scheidler, Daniel Weimer	An Adaptation of the NICE Cryptosystem to Real Quadratic Orders.	AFRICACRYPT	2008	DBLP DOI BibTeX RDF
11	Peishun Wang, Huaxiong Wang, Josef Pieprzyk	Threshold Privacy Preserving Keyword Searches.	SOFSEM	2008	DBLP DOI BibTeX RDF	secure index, threshold, key distribution, Keyword search
11	Michael R. Fellows, Danny Hermelin, Moritz Müller, Frances A. Rosamond	A Purely Democratic Characterization of W[1].	IWPEC	2008	DBLP DOI BibTeX RDF
11	David S. Johnson	The NP-completeness column: Finding needles in haystacks.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	PPAD, game theory, local search, Nash equilibrium, fixed point, PLS
11	Ron Banner, Ariel Orda	Multipath routing algorithms for congestion minimization.	IEEE/ACM Trans. Netw.	2007	DBLP DOI BibTeX RDF	computer networks, routing protocols, congestion avoidance
11	Thomas Eiter, Kazuhisa Makino	On computing all abductive explanations from a propositional Horn theory.	J. ACM	2007	DBLP DOI BibTeX RDF	Horn theories, dualization problem, polynomial total-time computation, NP-hardness, Abduction, model-based reasoning, propositional logic, tractability, prime implicates, characteristic set, enumeration algorithms
11	Liming Cai, Michael R. Fellows, David W. Juedes, Frances A. Rosamond	The Complexity of Polynomial-Time Approximation.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
11	Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Toby Walsh	The Complexity of Reasoning with Global Constraints.	Constraints An Int. J.	2007	DBLP DOI BibTeX RDF	Generalized arc consistency, Computational complexity, Constraint propagation, Global constraints
11	Dian-Wu Yue, Q. T. Zhang, Xiaowei Cui	Characteristic Functions for Optimum-Combining Output SINR With AWGN and Correlated Interference.	IEEE Trans. Commun.	2007	DBLP DOI BibTeX RDF
11	Dengguo Feng, Chuankun Wu	Advances in cryptography and information security - introduction of 2002-2006 progress of SKLOIS.	Frontiers Comput. Sci. China	2007	DBLP DOI BibTeX RDF	authentication and authorization, cryptography, network security, cryptanalysis
11	Yongjie Zhang 0003, Wei Zhang 0026	Can Irrational Investors Survive? A Social-Computing Perspective.	IEEE Intell. Syst.	2007	DBLP DOI BibTeX RDF	financial computing, agent-based computing, artificial intelligence, social computing, computer applications, computing methodologies, social and behavioral sciences
11	Lidan Miao, Hairong Qi 0001, Harold Szu	A Maximum Entropy Approach to Unsupervised Mixed-Pixel Decomposition.	IEEE Trans. Image Process.	2007	DBLP DOI BibTeX RDF
11	Jingyi Zhang, Wai Lok Woo, Satnam Singh Dlay	Blind Source Separation of Postnonlinear Convolutive Mixture.	IEEE Trans. Speech Audio Process.	2007	DBLP DOI BibTeX RDF
11	Sven Hartmann, Sebastian Link	Numerical Constraints for XML.	WoLLIC	2007	DBLP DOI BibTeX RDF
11	Sudheendra Murthy, Abhishek Goswami, Arunabha Sen	Interference-Aware Multicasting in Wireless Mesh Networks.	Networking	2007	DBLP DOI BibTeX RDF	Minimum Interference Multicast, Weakly Induced Connected Subgraph, NP-Complete, Wireless Mesh Network
11	Sylvain Guillemot, Vincent Berry	Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem.	CPM	2007	DBLP DOI BibTeX RDF
11	Jiong Guo, Rolf Niedermeier	Linear Problem Kernels for NP-Hard Problems on Planar Graphs.	ICALP	2007	DBLP DOI BibTeX RDF
11	Spyros C. Kontogiannis, Paul G. Spirakis	Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games.	ICALP	2007	DBLP DOI BibTeX RDF	Well Supported Approximate Equilibria, Bimatrix Games
11	Lionel Paris, Richard Ostrowski, Pierre Siegel, Lakhdar Sais	From Horn Strong Backdoor Sets to Ordered Strong Backdoor Sets.	MICAI	2007	DBLP DOI BibTeX RDF
11	Elizabeth Novoa	Simple Model-Based Exploration and Exploitation of Markov Decision Processes Using the Elimination Algorithm.	MICAI	2007	DBLP DOI BibTeX RDF
11	Samir Khuller, Maria Vanina Martinez, Dana S. Nau, Gerardo I. Simari, Amy Sliva, V. S. Subrahmanian	Finding Most Probable Worlds of Probabilistic Logic Programs.	SUM	2007	DBLP DOI BibTeX RDF
11	Wun-She Yap, Sherman S. M. Chow, Swee-Huay Heng, Bok-Min Goi	Security Mediated Certificateless Signatures.	ACNS	2007	DBLP DOI BibTeX RDF	security mediated, SMC cryptography, certificateless
11	Haralampos Tsaknakis, Paul G. Spirakis	An Optimization Approach for Approximate Nash Equilibria.	WINE	2007	DBLP DOI BibTeX RDF