Search results for "DNF"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
136	Lisa Hellerstein, Vijay Raghavan 0002	Exact learning of DNF formulas using DNF hypotheses.	STOC	2002	DBLP DOI BibTeX RDF	representations of boolean functions, algorithms, certificates, complexity theory, computational learning theory, disjunctive normal form, DNF
121	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
117	Linda Sellie	Exact learning of random DNF over the uniform distribution.	STOC	2009	DBLP DOI BibTeX RDF	learning theory, DNF
116	Homin K. Lee, Rocco A. Servedio, Andrew Wan	DNF are teachable in the average case.	Mach. Learn.	2007	DBLP DOI BibTeX RDF	DNF formulas, Teaching dimension
113	Howard Aizenstein, Leonard Pitt	Exact Learning of Read-k Disjoint DNF and Not-So-Disjoint DNF.	COLT	1992	DBLP DOI BibTeX RDF
99	Yasubumi Sakakibara	DNA-based algorithms for learning Boolean formulae.	Nat. Comput.	2003	DBLP DOI BibTeX RDF	population computation, weighted majority, DNA computing, massively parallel, Boolean formula, computational learning
99	Yasubumi Sakakibara	Solving Computational Learning Problems of Boolean Formulae on DNA Computers.	DNA Computing	2000	DBLP DOI BibTeX RDF
97	Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio	Learning functions represented as multiplicity automata.	J. ACM	2000	DBLP DOI BibTeX RDF	learning disjoint, learning polynomials, multiplicity automata, DNF, computational learning
94	Kwangsu Lee, Jung Yeon Hwang, Dong Hoon Lee 0001	Non-interactive Identity-Based DNF Signature Scheme and Its Extensions.	ICISC	2008	DBLP DOI BibTeX RDF	Signer Anonymity, Identity-Based Signature, Disjunctive Normal Form, Access Structure
94	Homin K. Lee, Rocco A. Servedio, Andrew Wan	DNF Are Teachable in the Average Case.	COLT	2006	DBLP DOI BibTeX RDF
94	Jeffrey C. Jackson, Rocco A. Servedio	On Learning Random DNF Formulas Under the Uniform Distribution.	APPROX-RANDOM	2005	DBLP DOI BibTeX RDF
86	Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi	Learnability and Automatizability.	FOCS	2004	DBLP DOI BibTeX RDF
81	Subhash Khot, Rishi Saket	Hardness of Minimizing and Learning DNF Expressions.	FOCS	2008	DBLP DOI BibTeX RDF
81	Karsten A. Verbeurgt	Learning Sub-classes of Monotone DNF on the Uniform Distribution.	ALT	1998	DBLP DOI BibTeX RDF
81	Yishay Mansour	An O(nlog log n) Learning Algorithm for DNF Under the Uniform Distribution.	COLT	1992	DBLP DOI BibTeX RDF
80	Jun Tarui, Tatsuie Tsukiji	Learning DNF by Approximating Inclusion-Exclusion Formulae.	CCC	1999	DBLP DOI BibTeX RDF	Inclusion-exclusion formula, PAC Learning, DNF
69	Louay Bazzi	Polylogarithmic Independence Can Fool DNF Formulas.	FOCS	2007	DBLP DOI BibTeX RDF
69	Wolfgang Lindner 0002	Learning DNF by Statistical and Proper Distance Queries Under the Uniform Distribution.	ALT	2005	DBLP DOI BibTeX RDF
69	Kouichi Hirata, Ryosuke Nagazumi, Masateru Harao	Extraction of Coverings as Monotone DNF Formulas.	Discovery Science	2003	DBLP DOI BibTeX RDF
66	Christopher Umans	The Minimum Equivalent DNF Problem and Shortest Implicants.	FOCS	1998	DBLP DOI BibTeX RDF	minimum equivalent DNF, shortest implicant, complexity of approximation, computational complexity, logic minimization, polynomial hierarchy
62	Hongtao Huang	Detection of Disjunctive Normal Form Predicate in Distributed Systems.	ICDCN	2008	DBLP DOI BibTeX RDF
62	Ken Sadohara	Learning of Boolean Functions Using Support Vector Machines.	ALT	2001	DBLP DOI BibTeX RDF
56	Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan	Learning Random Monotone DNF.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
56	Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks	Minimizing DNF Formulas and AC0d Circuits Given a Truth Table.	CCC	2006	DBLP DOI BibTeX RDF
56	Judy Goldsmith, Matthias Hagen, Martin Mundhenk	Complexity of DNF and Isomorphism of Monotone Formulas.	MFCS	2005	DBLP DOI BibTeX RDF
56	Yoshikazu Shima, Kouichi Hirata, Masateru Harao	Extraction of Frequent Few-Overlapped Monotone DNF Formulas with Depth-First Pruning.	PAKDD	2005	DBLP DOI BibTeX RDF
56	Ulrich Rückert 0002, Stefan Kramer 0001, Luc De Raedt	Phase Transitions and Stochastic Local Search in k-Term DNF Learning.	ECML	2002	DBLP DOI BibTeX RDF
56	Jeffrey C. Jackson, Christino Tamon, Tomoyuki Yamakami	Quantum DNF Learnability Revisited.	COCOON	2002	DBLP DOI BibTeX RDF
56	Rocco A. Servedio	On Learning Monotone DNF under Product Distributions.	COLT/EuroCOLT	2001	DBLP DOI BibTeX RDF
56	Krishnan Pillaipakkamnatt, Vijay Raghavan 0002	On the Limits of Proper Learnability of Subclasses of DNF Formulas.	COLT	1994	DBLP DOI BibTeX RDF
56	Avrim Blum, Roni Khardon, Eyal Kushilevitz, Leonard Pitt, Dan Roth	On Learning Read-k-Satisfy-j DNF.	COLT	1994	DBLP DOI BibTeX RDF
56	Sally A. Goldman, H. David Mathias	Learning k-Term DNF Formulas with an Incomplete Membership Oracle.	COLT	1992	DBLP DOI BibTeX RDF
49	Ingo Ahrns, Heiko Neumann	Space-Variant Dynamic Neural Fields for Visual Attention.	CVPR	1999	DBLP DOI BibTeX RDF
49	Nader H. Bshouty, Richard Cleve, Sampath Kannan, Christino Tamon	Oracles and Queries that are Sufficient for Exact Learning (Extended Abstract).	COLT	1994	DBLP DOI BibTeX RDF
44	Takayuki Sato, Kazuyuki Amano, Eiji Takimoto, Akira Maruoka	Monotone DNF Formula That Has a Minimal or Maximal Number of Satisfying Assignments.	COCOON	2008	DBLP DOI BibTeX RDF
44	Ryan O'Donnell, Karl Wimmer	Approximation by DNF: Examples and Counterexamples.	ICALP	2007	DBLP DOI BibTeX RDF
44	Kun Peng	Secure Multiparty Computation of DNF.	ICICS	2007	DBLP DOI BibTeX RDF
44	Michael Alekhnovich	Lower bounds for k-DNF resolution on random 3-CNFs.	STOC	2005	DBLP DOI BibTeX RDF	random 3CNF, res(k), resolution
44	Yoshikazu Shima, Shinji Mitsuishi, Kouichi Hirata, Masateru Harao	Extracting Minimal and Closed Monotone DNF Formulas.	Discovery Science	2004	DBLP DOI BibTeX RDF
44	Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener	On Converting CNF to DNF.	MFCS	2003	DBLP DOI BibTeX RDF
44	Nader H. Bshouty, Nadav Eiron	Learning Monotone DNF from a Teacher That Almost Does Not Answer Membership Queries.	COLT/EuroCOLT	2001	DBLP DOI BibTeX RDF
44	Adam R. Klivans, Rocco A. Servedio	Learning DNF in time 2Õ(n1/3).	STOC	2001	DBLP DOI BibTeX RDF
44	Shinichi Yanagi, Mineichi Kudo, Masaru Shimbo	Polynomial-sample learnability about distance-0 and 1 DNF formulas.	KES (2)	1998	DBLP DOI BibTeX RDF
44	Michele Flammini, Alberto Marchetti-Spaccamela, Ludek Kucera	Learning DNF Formulae Under Classes of Probability Distributions.	COLT	1992	DBLP DOI BibTeX RDF
43	Qingping Tao, Stephen D. Scott 0001	Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning.	Mach. Learn.	2008	DBLP DOI BibTeX RDF	Markov chain Monte Carlo, DNF, Winnow
42	Jeffrey C. Jackson	An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution	FOCS	1994	DBLP DOI BibTeX RDF	boosted weak learner, membership-query algorithm, learning DNF, nonuniform distributions, noisy examples, boosting techniques, uniform distribution
42	Howard Aizenstein, Lisa Hellerstein, Leonard Pitt	Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries	FOCS	1992	DBLP DOI BibTeX RDF	disjunctive normal, nonlearnability, polynomial-time membership, read-thrice DNF formulas, membership, boolean formulas, equivalence queries, exact learning
42	Howard Aizenstein, Leonard Pitt	Exact Learning of Read-Twice DNF Formulas (Extended Abstract)	FOCS	1991	DBLP DOI BibTeX RDF	read-twice DNF formulas, protocol, polynomial-time algorithm, Boolean formulas, membership queries, equivalence queries, disjunctive normal form, exact learning
39	Lisa Hellerstein, Vijay Raghavan 0002	Exact learning of DNF formulas using DNF hypotheses.	J. Comput. Syst. Sci.	2005	DBLP DOI BibTeX RDF
37	Khaled M. Elbassioni, Kazuhisa Makino, Imran Rauf	On the Readability of Monotone Boolean Formulae.	COCOON	2009	DBLP DOI BibTeX RDF
37	Ian Davidson, S. S. Ravi	The complexity of non-hierarchical clustering with instance and cluster level constraints.	Data Min. Knowl. Discov.	2007	DBLP DOI BibTeX RDF	Non-hierarchical clustering, Complexity, Constraints
37	Petar Popovski, Hiroyuki Yomo	Physical Network Coding in Two-Way Wireless Relay Channels.	ICC	2007	DBLP DOI BibTeX RDF
37	Ricard Gavaldà, Denis Thérien	Algebraic Characterizations of Small Classes of Boolean Functions.	STACS	2003	DBLP DOI BibTeX RDF
37	Johannes Köbler, Wolfgang Lindner 0002	The Complexity of Learning Concept Classes with Polynomial General Dimension.	ALT	2002	DBLP DOI BibTeX RDF
37	Richard Nock, Pascal Jappy, Jean Sallantin	Generalized Graph Colorability and Compressibility of Boolean Formulae.	ISAAC	1998	DBLP DOI BibTeX RDF
37	Ken Satoh	Analysis of Case-Based Representability of Boolean Functions by Monotone Theory.	ALT	1998	DBLP DOI BibTeX RDF
37	Michael J. Kearns, Ming Li 0001, Leslie G. Valiant	Learning Boolean Formulas.	J. ACM	1994	DBLP DOI BibTeX RDF	machine learning, inductive inference
35	Tao Peng 0003, Wanli Zuo, Fengling He	SVM based adaptive learning method for text classification from positive and unlabeled documents.	Knowl. Inf. Syst.	2008	DBLP DOI BibTeX RDF	Improved 1-DNF algorithm, Focused web crawling, Machine learning, SVM, Text classification, PSO
32	Mineichi Kudo, Tetsuya Murai	Extended DNF Expression and Variable Granularity in Information Tables.	IEEE Trans. Fuzzy Syst.	2008	DBLP DOI BibTeX RDF
32	Rong-Lei Sun	Study on the Non-expandability of DNF and Its Application to Incremental Induction.	ICIRA (1)	2008	DBLP DOI BibTeX RDF	Incremental induction, Machine learning, Artificial intelligence, Boolean algebra
32	Khaled M. Elbassioni	On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization.	ESA	2006	DBLP DOI BibTeX RDF
32	Dan Boneh, Eu-Jin Goh, Kobbi Nissim	Evaluating 2-DNF Formulas on Ciphertexts.	TCC	2005	DBLP DOI BibTeX RDF
32	Vitaly Feldman	On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.	COLT	2005	DBLP DOI BibTeX RDF
32	Luca Trevisan	A Note on Approximate Counting for k-DNF.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
32	Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio	Learning DNF from Random Walks.	FOCS	2003	DBLP DOI BibTeX RDF
32	Frédéric Koriche, Joël Quinqueton	Robust k-DNF Learning via Inductive Belief Merging.	ECML	2003	DBLP DOI BibTeX RDF
32	Andreas Alexander Albrecht, Kathleen Steinhöfel	A Simulated Annealing-Based Learning Algorithm for Boolean DNF.	Australian Joint Conference on Artificial Intelligence	1999	DBLP DOI BibTeX RDF
32	Herna L. Viktor, Ian Cloete	Extracting DNF Rules from Artificial Neural Networks.	IWANN	1995	DBLP DOI BibTeX RDF
25	Marcus Fontoura, Suhas Sadanandan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Srihari Venkatesan, Jason Y. Zien	Efficiently evaluating complex boolean expressions.	SIGMOD Conference	2010	DBLP DOI BibTeX RDF	dewey, interval, boolean expressions, pub/sub
25	María A. Franco, Natalio Krasnogor, Jaume Bacardit	Analysing bioHEL using challenging boolean functions.	GECCO (Companion)	2010	DBLP DOI BibTeX RDF	evolutionary algorithms, learning classifier systems, rule induction, large-scale datasets
25	Dominique Bouthinon, Henry Soldano, Véronique Ventos	Concept Learning from (Very) Ambiguous Examples.	MLDM	2009	DBLP DOI BibTeX RDF	Symbolic concept-learning, Ambiguity, Incomplete data
25	Kalpesh Kapoor, Jonathan P. Bowen	Test conditions for fault classes in Boolean specifications.	ACM Trans. Softw. Eng. Methodol.	2007	DBLP DOI BibTeX RDF	Fault-based testing, Boolean specification, fault classes
25	Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami	New Results for Learning Noisy Parities and Halfspaces.	FOCS	2006	DBLP DOI BibTeX RDF
25	Ashish Sabharwal, Carlos Ansótegui, Carla P. Gomes, Justin W. Hart, Bart Selman	QBF Modeling: Exploiting Player Symmetry for Simplicity and Efficiency.	SAT	2006	DBLP DOI BibTeX RDF
25	Peter Niebert, Doron A. Peled	Efficient Model Checking for LTL with Partial Order Snapshots.	TACAS	2006	DBLP DOI BibTeX RDF
25	Byoung-Tak Zhang, Ha-Young Jang	Molecular Learning of wDNF Formulae.	DNA	2005	DBLP DOI BibTeX RDF
25	Amos Fiat, Dmitry Pechyony	Decision Trees: More Theoretical Justification for Practical Algorithms.	ALT	2004	DBLP DOI BibTeX RDF
25	Michael Schmitt 0001	An Improved VC Dimension Bound for Sparse Polynomials.	COLT	2004	DBLP DOI BibTeX RDF
25	Martin Zinkevich, Avrim Blum, Tuomas Sandholm	On polynomial-time preference elicitation with value queries.	EC	2003	DBLP DOI BibTeX RDF	learning, combinatorial auctions, preference elicitation
25	Johannes Köbler, Wolfgang Lindner 0002	A General Dimension for Approximately Learning Boolean Functions.	ALT	2002	DBLP DOI BibTeX RDF
25	Nader H. Bshouty, Lynn Burroughs	On the Proper Learning of Axis Parallel Concepts.	COLT	2002	DBLP DOI BibTeX RDF
25	Nader H. Bshouty, Lynn Burroughs	Bounds for the Minimum Disagreement Problem with Applications to Learning Theory.	COLT	2002	DBLP DOI BibTeX RDF
25	Nader H. Bshouty, Dmitry Gavinsky	On Boosting with Optimal Poly-Bounded Distributions.	COLT/EuroCOLT	2001	DBLP DOI BibTeX RDF
25	Nader H. Bshouty, Vitaly Feldman	On Using Extended Statistical Queries to Avoid Membership Queries.	COLT/EuroCOLT	2001	DBLP DOI BibTeX RDF
25	Christer Berg, Staffan Ulfberg	Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers.	Comput. Complex.	1999	DBLP DOI BibTeX RDF	lower bounds, Circuit complexity, monotone circuits
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	Christopher Umans	On the Complexity and Inapproximability of Shortest Implicant Problems.	ICALP	1999	DBLP DOI BibTeX RDF
25	Jeffrey C. Jackson, Eli Shamir 0001, Clara Shwartzman	Learning with Queries Corrupted by Classification Noise.	ISTCS	1997	DBLP DOI BibTeX RDF
25	Jae-Young Chang, Sang-goo Lee	An optimization of disjunctive queries: union-pushdown.	COMPSAC	1997	DBLP DOI BibTeX RDF	disjunctive query optimization, disjunctive predicates, plan generation, union-pushdown, performance analysis, query processing, query optimizers
25	Lawrence Peh, Chi Ping Tsang	Weight Sensitive Boolean Extraction Produces Compact Expressions.	Australian Joint Conference on Artificial Intelligence	1997	DBLP DOI BibTeX RDF	weight sensitivity, neural network, rule extraction, boolean expression, disjunctive normal form
25	Francis K. H. Quek, Meide Zhao	Inductive learning in hand pose recognition.	FG	1996	DBLP DOI BibTeX RDF	hand pose recognition, gestural systems, user hand anatomy, perspective effects, rulebase, disjunctive normal form formulae, rule-based induction system, flexible matching, inductive learning, learning by example
25	Hartmut Klauck	On the Hardness of Global and Local Approximation.	SWAT	1996	DBLP DOI BibTeX RDF
25	Thomas R. Hancock, Tao Jiang 0001, Ming Li 0001, John Tromp	Lower Bounds on Learning Decision Lists and Trees (Extended Abstract).	STACS	1995	DBLP DOI BibTeX RDF
25	Robert H. Sloan, György Turán	Learning with Queries but Incomplete Information (Extended Abstract).	COLT	1994	DBLP DOI BibTeX RDF
25	Michael Frazier, Sally A. Goldman, Nina Mishra, Leonard Pitt	Learning from a Consistently Ignorant Teacher.	COLT	1994	DBLP DOI BibTeX RDF
25	Der-Shung Yang, Gunnar Blix, Larry A. Rendell	The Replication Problem: A Constructive Induction Approach.	EWSL	1991	DBLP DOI BibTeX RDF	Empirical learning, constructive induction
23	Evangelos Triantaphyllou, Jennifer Austin-Rodriguez	Optimization in Boolean Classification Problems.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Inductive inference problem, Boolean classification problem, Minimum number of clauses, One clause at a time approach, OCAT, GRASP approach, Randomized heuristics, Missing information, Unclassifiable examples, SAT, Learning algorithm, Medical diagnosis, Conjunctive normal form, CNF, Satisfiability problem, Disjunctive normal form, DNF
23	Vetle I. Torvik, Evangelos Triantaphyllou	Inference of Monotone Boolean Functions.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Isotone Boolean function, Antitone Boolean function, Boolean function inference problem, Free distributive lattice, Interactive learning of Boolean functions, Shannon function, Hansel theorem, Hansel chain, Sequential Hansel chains question-asking strategy, Binary search-Hansel chains question-asking strategy, Boolean function, Conjunctive normal form, CNF, Binary search, Classification problem, Disjunctive normal form, DNF, Monotone Boolean function
23	Salvador Nieto Sánchez, Evangelos Triantaphyllou	Optimization in Classifying Text Documents.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Indexing terms, Context descriptors, Document surrogate, Principle of least effort, PLE, One clause at a time algorithm, OCAT, Indexing vocabulary, Optimal indexing vocabulary, Semantic analysis methodologies, Word patterns, Text classification, Document classification, Computational linguistics, Vector space model, Keywords, Conjunctive normal form, CNF, Disjunctive normal form, DNF, VSM
23	Nader H. Bshouty	Exact Learning via the Monotone Theory (Extended Abstract)	FOCS	1993	DBLP DOI BibTeX RDF	Monotone theory, decision trees, boolean function, learnability, membership, CNF, equivalence queries, DNF, exact learning, concept classes