1 The Communication Complexity of Correlation (2009)
Prahladh Harsha, Rahul Jain, David Mcallester, Jaikumar Radhakrishnan
Abstract—Let X and Y be finite non-empty sets and (X, Y) a pair of random variables taking values in X × Y. We consider communication protocols between two parties, Alice and Bob, for generating X...
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman, János A. Csirik
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
1 Generalization Bounds and Consistency (2008)
This chapter gives generalization bounds for structured output learning. We show
Random-World Semantics and Syntactic Independence for Expressive Languages (2008)
McAllester, David, Milch, Brian, Goodman, Noah D.
We consider three desiderata for a language combining logic and probability: logical expressivity, random-world semantics, and the existence of a useful syntactic condition for probabilistic...
Random-World Semantics and Syntactic Independence for Expressive Languages (2008)
McAllester, David, Milch, Brian, Goodman, Noah D.
We consider three desiderata for a language combining logic and probability: logical expressivity, random-world semantics, and the existence of a useful syntactic condition for probabilistic...
The generalized A* architecture (2008)
Pedro Felzenszwalb, David Mcallester
We consider the problem of finding a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated within this framework. We...
Matthias Blume, David Mcallester
Even in statically typed languages it is useful to have certain invariants checked dynamically. Findler and Felleisen gave an algorithm for dynamically checking expressive higherorder types called...
Matthias Blume, David Mcallester
Even in statically typed languages it is useful to have certain invariants checked dynamically. Findler and Felleisen gave an algorithm for dynamically checking expressive higherorder types called...
Walksat in the 2004 SAT Competition (2008)
Henry Kautz, David Mcallester, Bart Selman
The first convincing demonstration that local search could be used to solve challenging satisfiability problems was provided by the GSAT algorithm [9]. GSAT performs gradient descent search in the...
Non-Deterministic Lisp with Dependency-Directed Backtracking (2008)
Ramin Zabih Y, David Mcallester, David Chapman
Extending functional Lisp with McCarthy's nondeterministic operator AMB yields a language which can concisely express search problems. Dependencydirected backtracking is a powerful search...
Exponentiated gradient algorithms and PAC-Bayesian (2008)
Peter L. Bartlett, Michael Collins, David Mcallester, Ben Taskar
Large margin methods for structured classification:
The generalized A* architecture (2008)
Pedro F. Felzenszwalb, David Mcallester
We consider the problem of computing a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated in this framework. We...
[Mathematical Logic and Formal Languages] Mathematical Logic—computability theory (2008)
Robert Givan, David Mcallester
We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The...
The generalized A* architecture (2008)
Pedro F. Felzenszwalb, David Mcallester
We consider the problem of computing a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated in this framework. We...
This paper gives distribution-free concentration inequalities for the missing mass and the error rate of histogram rules. Negative association methods can be used to reduce these concentration...
William W. Cohen, Henry Kautz, David Mcallester
The web contains a large quantity of unstructured information. In many cases, it is possible to heuristically extract structured information, but the resulting databases are "soft":...
Alpha-Beta-Conspiracy Search (Draft of Oct. 20, 1993) (2007)
: We introduce a variant of ff-fi search in which each node is associated with two depths rather than one. The purpose of ff-fi search is to find strategies for each player that together establish a...
Draft Of June, David Mcallester
: Ontic is a higher order formal specification language designed for expressing formal concepts as clearly and concisely as possible. The consiceness and clarity is achieved through the use of...
Logical Reasoning Systems (2007)
this article. However, it is possible to give a somewhat superficial description of its limitations. First order logic allows one to state properties of concepts but it does not generally allow us to...
On The Declarative Value of Nondeterminism (2007)
: This paper describes Ontic, a higher order formal specification language designed for expressing formal concepts as clearly and concisely as possible. The consiceness and clarity is achieved...
Mit Artificial, David Mcallester
: This paper describes Ontic, a higher order formal specification language designed for expressing formal concepts as clearly and concisely as possible. The consiceness and clarity is achieved...
Harald Ganzinger, David Mcallester
Abstract. It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logic programming has been inappropriate for the study of the running...
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Conference submission (1/22/02). ATTac-2001: A Learning, Autonomous Bidding Agent (2007)
Peter Stone, Robert E. Schapire, Michael L. Littman, David Mcallester
This paper presents a general approach to building autonomous bidding agents to bid in multiple simultaneous auctions for interacting goods. The core of our approach is learning a model of the...
Witold Charatonik, David Mcallester, Damian Niwinski, Andreas Podelski, Igor Walukiewicz
The Horn-calculus is a logic programming language allowing arbitrary nesting of least and greatest fixed points. The Horn-programs can naturally expresses safety and liveness properties for reactive...
A GLIMPSE OF TRUTH'MAINTENANCE (2007)
A. I. Memo, Jon Doyle, I Gerald, Jay Sussman, Richard M. Sta!iman, Guy L. Steele, ...
Many procedurally-oriented problem solving systems can be viewed as performing a mix'ture of computation and deduction, with much of the computation serving to decid e what deductions should be...
Peter Stone, Robert E. Schapire, Janos A. Csirik, Michael L. Littman, David Mcallester
Abstract. Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This paper presents a general approach to building autonomous bidding agents to...
Invited to IJCAI Distinguished Paper Track. Learning Theory and Language Modeling (2007)
David Mcallester, Robert E. Schapire
Here we consider some of our recent work on Good-Tuing estimators in the larger context of learning theory and language modeling. The Good-turing estimators have played a significant role in natural...
Witold Charatonik, David Mcallester, Damian Niwinski, Andreas Podelski, Igor Walukiewicz
The Horn-calculus is a logic programming language allowing arbitrary nesting of least and greatest fixed points. The Horn-programs can naturally expresses safety and liveness properties for reactive...
Roberto Sebastiani, Roberto Sebastiani, David Mcallester, David Mcallester
istituto per la ricerca scientifica e tecnologica
Chernoff bounds and related large deviation bounds have a wide variety of applications in statistics and learning theory. This paper proves that for any real-valued random variable X the probability...
Inference Using Formal Logics (2007)
Logic is fundamental to a variety of disciplines. Logic provides insight into the nature of mathematics and human mathematical reasoning. Logic provides insight into the syntax and semantics of human...
Peter L. Bartlett, Michael Collins, David Mcallester, Ben Taskar
Large margin methods for structured classification:
The communication complexity of correlation (2007)
Prahladh Harsha, Rahul Jain, David Mcallester, Jaikumar Radhakrishnan
We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate...
Prahladh Harsha, Rahul Jain, David Mcallester, Jaikumar Radhakrishnan
We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate...
Case-Factor Diagrams for Structured Probabilistic Modeling (2004)
McAllester, David, Collins, Michael, Pereira, Fernando C.N.
We introduce a probabilistic formalism subsuming Markov random fields of bounded tree width and probabilistic context free grammars. Our models are based on a representation of Boolean formulas that...
Case-factor diagrams for structured probabilistic modeling (2004)
David Mcallester, Michael Collins, Fernando Pereira
We introduce a probabilistic formalism subsuming Markov random fields of bounded tree width and probabilistic context free grammars. Our models are based on a representation of Boolean formulas that...
Michael Collins, David Mcallester, Ben Taskar
Abstract. We consider the problem of structured classification, where the taskis to predict a label y from an input x, and y has meaningful internal structure.Our framework includes supervised...
Case-Factor Diagrams for Structured Probabilistic Modeling (2004)
David Mcallester, Michael Collins, Fernando Pereira
We introduce a probabilistic formalism subsuming Markov random fields of bounded tree width and probabilistic context free grammars. Our models are based on a representation of Boolean formulas that...
Exponentiated gradient algorithms for large-margin structured classification (2004)
Peter L. Bartlett, Ben Taskar, Michael Collins, David Mcallester
We consider the problem of structured classification, where the task is to predict a label y from an input x, and y has meaningful internal structure. Our framework includes supervised training of...
Simplified PAC-Bayesian margin bounds (2003)
Abstract. The theoretical understanding of support vector machines is largely based on margin bounds for linear classifiers with unit-norm weight vectors and unit-norm feature vectors. Unit-norm...
Concentration Inequalities for the Missing Mass and for Histogram Rule Error (2003)
David Mcallester, Luis Ortiz, Ralf Herbrich, Thore Graepel
This paper gives distribution-free concentration inequalities for the missing mass and the error rate of histogram rules. Negative association methods can be used to reduce these concentration...
Concentration inequalities for the missing mass and for histogram rule error (2003)
David Mcallester, Luis Ortiz, Ralf Herbrich, Thore Graepel
This paper gives distribution-free concentration inequalities for the missing mass and the error rate of histogram rules. Negative association methods can be used to reduce these concentration...
Ganzinger,Harald, McAllester,David
It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logic programming has been inappropriate for the study of the running time of...
Ganzinger, Harald, McAllester, David, Stuckey, Peter J.
It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logic programming has been inappropriate for the study of the running time of...
ATTac-2001: A learning, autonomous bidding agent (2002)
Peter Stone, Robert E. Schapire, János A. Csirik, Michael L. Littman, David Mcallester
Abstract. Auctions are becoming an increasingly popular method for transacting business, especially over the Internet. This paper presents a general approach to building autonomous bidding agents to...
Modeling auction price uncertainty using boosting-based conditional density estimation (2002)
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Harald Ganzinger, David Mcallester
Abstract. It is widely accepted that many algorithms can be concisely and clearly expressed as logical inference rules. However, logic programming has been inappropriate for the study of the running...
Modeling auction price uncertainty using boosting-based conditional density estimation (2002)
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman, János A. Csirik
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
Modeling auction price uncertainty using boosting-based conditional density estimation (2002)
Robert E. Schapire, Peter Stone, David Mcallester, Michael L. Littman, János A. Csirik
In complicated, interacting auctions, a fundamental problem is the prediction of prices of goods in the auctions, and more broadly, the modeling of uncertainty regarding these prices. In this paper,...
A new meta-complexity theorem for bottom-up logic programs (2001)
Ganzinger,Harald, McAllester,David
Nontrivial meta-complexity theorems, proved once for a programming language as a whole, facilitate the presentation and analysis of particular algorithms. This paper gives a new meta-complexity...
A new meta-complexity theorem for bottom-up logic programs (2001)
Ganzinger, Harald, McAllester, David, Goré, Rajeev, Leitsch, Alexander, Nipkow, Tobias
Nontrivial meta-complexity theorems, proved once for a programming language as a whole, facilitate the presentation and analysis of particular algorithms. This paper gives a new meta-complexity...
An indexed model of recursive types for foundational proof-carrying code (2001)
The proofs of "traditional " proof carrying code (PCC) are type-specialized in the sense that they require axioms about a specific type system. In contrast, the proofs of...
An architecture for action selection in robotic soccer (2001)
CMUnited-99 was the 1999 RoboCup robotic soccer simulator league champion. In the RoboCup-2000 competition, CMUnited-99 was entered again and despite being publicly available for the entire year, it...
Learning Theory and Language Modeling (2001)
David Mcallester, Robert E. Schapire
Here we consider some of our recent work on Good-Tuing estimators in the larger context of learning theory and language modeling. The Good-turing estimators have played a significant role in natural...
A new meta-complexity theorem for bottom-up logic programs (2001)
Harald Ganzinger, David Mcallester
Abstract. Nontrivial meta-complexity theorems, proved once for a programming language as a whole, facilitate the presentation and analysis of particular algorithms. This paper gives a new...
A new meta-complexity theorem for bottom-up logic programs (2001)
Harald Ganzinger, David Mcallester
Abstract. Nontrivial meta-complexity theorems, proved once for a programming language as a whole, facilitate the presentation and analysis of particular algorithms. This paper gives a new...
An architecture for action selection in robotic soccer (2001)
content areas: multi-agent teams, coordinating multiple agents,action selection and planning, real-time performance
An architecture for action selection in robotic soccer (2001)
ABSTRACT CMUnited-99 was the 1999 RoboCup robotic soccer simulator league champion. In the RoboCup-2000 competition, CMUnited-99 was entered again and despite being publicly available for the entire...
Keeping the ball from CMUnited-99 (2001)
Abstract. This paper presents preliminary results achieved during our current development of a team for simulated robotic soccer in the RoboCup soccer server [2]. We have constructed a team that...
Polynomial-time Computation via Local Inference Relations (2000)
Givan, Robert, McAllester, David
We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The...
Computable shell decomposition bounds (2000)
John Langford, David Mcallester, Pack Kaelbling, David Cohn
Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase...
Policy gradient methods for reinforcement learning with function approximation (2000)
Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...
Policy gradient methods for reinforcement learning with function approximation (2000)
Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...
D.: Boosting with multi-way branching in decision trees (2000)
Yishay Mansour, David Mcallester
It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to...
Computable Shell Decomposition Bounds (2000)
John Langford, David Mcallester
Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase...
Polynomial-time Computation via Local Inference Relations (2000)
Robert Givan, Robert Givan, David Mcallester, David Mcallester
We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The...
Policy Gradient Methods for Reinforcement Learning with Function Approximation (2000)
Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...
Boosting using Branching Programs (2000)
Yishay Mansour, David Mcallester
It is known that decision tree learning can be viewed as a form of boosting. Given a weak learning hypothesis one can show that the training error of a decision tree declines as jT j \Gammafi where...
On the Convergence Rate of Good-Turing Estimators (2000)
David Mcallester, Robert E. Schapire
Good-Turing adjustments of word frequencies are an important tool in natural language modeling. In particular, for any sample of words, there is a set of words not occuring in that sample. The total...
Hardening Soft Information Sources (2000)
William Cohen, Henry Kautz, David Mcallester
The web contains a large quantity of unstructured information. In many cases, it is possible to heuristically extract structured information, but the resulting databases are "soft": they...
Computable Shell Decomposition Bounds (2000)
John Langford, David Mcallester
Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase...
Generalization Bounds for Decision Trees (2000)
Yishay Mansour, David Mcallester
We derive a new bound on the error rate for decision trees. The bound depends both on the structure of the tree and the specific sample (not just the size of the sample). This bound is tighter than...
Boosting with Multi-Way Branching in Decision Trees (2000)
Yishay Mansour David, David Mcallester
It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to...
Bellman Equations for Stochastic Programs (2000)
. This paper gives a model-checking style algorithm for verifying the decision-theoretic utility of a hand-written robot controller. The paper presents a simple Turing-complete programming language...
Policy Gradient Methods for (2000)
Reinforcement Learning With, Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically intractable.
Policy gradient methods for reinforcement learning with function approximation (2000)
Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...
Computable shell decomposition bounds (2000)
John Langford, David Mcallester, Manfred Warmuth
Haussler, Kearns, Seung and Tishby introduced the notion of a shell decomposition of the union bound as a means of understanding certain empirical phenomena in learning curves such as phase...
Relating probabilistic grammars and automata (1999)
Steven Abney, David Mcallester, Fernando Pereira
Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic push-down automata (PPDAs) have been used for language modeling and maximum likelihood parsing. We investigate the...
On the Complexity Analysis of Static Analyses (1999)
dmac Abstract. This paper argues that for many algorithms, and static analysis algorithms in particular, bottom-up logic program presentations are clearer and simpler to analyze, for both correctness...
On the Complexity Analysis of Static Analyses (1999)
. This paper argues that for many algorithms, and static analysis algorithms in particular, bottom-up logic program presentations are clearer and simpler to analyze, for both correctness and...
Boosting with Multi-Way Branching in Decision Trees (1999)
Yishay Mansour, David Mcallester
It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to...
Generalization Bounds for Decision Trees (1999)
Yishay Mansour, David Mcallester
We derive a new bound on the error rate for decision trees. The bounds depends both on the structure of the tree and the specific sample (not just the size of the sample). This bound is tighter than...
Relating Probabilistic Grammars and Automata (1999)
Steven Abney, David Mcallester, Fernando Pereira
Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic pushdown automata (PPDAs) have been used for language modeling and maximum likelihood parsing. We investigate the...
Relating probabilistic grammars and automata (1999)
Steven Abney, David Mcallester, Fernando Pereira
Both probabilistic context-free grammars (PCFGs) and shift-reduce probabilistic pushdown automata (PPDAs) have been used for language modeling and maximum likelihood parsing. We investigate the...
Policy Gradient Methods for Reinforcement Learning with Function Approximation (1999)
Richard S. Sutton, David Mcallester, Satinder Singh, Yishay Mansour
Function approximation is essential to reinforcement learning, but the standard approach of approximating a value function and determining a policy from it has so far proven theoretically...
Object-oriented programming languages all involve the notions of class and object. The authors extend the notion of class so that any Boolean combination of classes is also a class. Boolean classes...
Taxonomic Syntax for First Order Inference. (1998)
Most knowledge representation languages are based on classes and taxonomic relationships between classes. Taxonomic hierarchies without defaults or exceptions are semantically equivalent to a...
Natural Language Syntax and First Order Inference. (1998)
McAllester, David, Givan, Robert
First order inference can be made more efficient by using non-standard syntax for first order logic. This paper shows how a fragment of English syntax under Montague semantics provides the foundation...
Automatic Recognition of Tractability in Inference Relations. (1998)
A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference...
Natural Language Based Inference Procedures Applied to Schubert's Steamroller. (1998)
Givan, Robert, McAllester, David, Shalaby, Sameer
We have previously argued that the syntactic structure of natural language can be exploited to construct powerful polynomial time inference procedures. This paper supports the earlier arguments by...
Systematic Nonlinear Planning. (1998)
McAllester, David, Rosenblitt, David
This paper presents a simple, sound, complete, and systematic algorithm for domain independent STRIPS planning. Simplicity is achieved by starting with a ground procedure and then applying a general,...
Lifting Transformations. (1998)
McAllester, David, Siskind, Jeffrey
Lifting is a well known technique in resolution theorem proving, logic programming, and term rewriting. In this paper we formulate lifting as an efficiency-motivated program transformation applicable...
Observations on Cognitive Judgments. (1998)
It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...
We present a term rewriting procedure based on congruence closure that can be used with arbitrary equational theories. This procedure is motivated by the pragmatic need to prove equations in...
Tractable Inference Relations. (1998)
Givan, Robert, McAllester, David
We consider the concept of local sets of inference rules. Locality is a syntactic condition on rule sets which guarantees that the inference relation defined by those rules is polynomial time...
Object Conversion is Type-Preserving (1998)
Closure conversion is a program transformation widely used in modern compilers. For a variety of reasons it is desirable that compilation preserve types. We consider a closure conversion mapping e to...
Evidence for Invariants in Local Search (1997)
David Mcallester, Bart Selman, Henry Kautz
Abstract It is well known that the performance of a stochastic local search proceduredepends upon the setting of its noise parameter, and that the optimal setting varies with the problem...
Exploiting Variable Dependency in Local Search (1997)
Henry Kautz, David Mcallester, Bart Selman
Stochastic search has recently been shown to be successful for solving large boolean satisfiability problems. However, systematic methods tend to be more effective in problem domains with a large...
Ten Challenges in Propositional Reasoning and Search (1997)
Bart Selman, Henry Kautz, David Mcallester
The past several years have seen much progress in the area of propositional reasoning and satisfiability testing. There is a growing consensus by researchers on the key technical challenges that need...
Computational Challenges in Propositional Reasoning and Search (1997)
Bart Selman Henry, Henry Kautz, David Mcallester
The past several years have seen much progress in the area of propositional reasoning and satisfiability testing. There is a growing consensus by researchers on the key technical challenges that need...
Evidence for Invariants in Local Search (1997)
David Mcallester, Bart Selman, Henry Kautz
It is well known that the performance of a stochastic local search procedure depends upon the setting of its noise parameter, and that the optimal setting varies with the problem distribution. It is...
Effective Bayesian Inference for Stochastic Programs (1997)
Daphne Koller, David Mcallester, Avi Pfeffer
In this paper, we propose a stochastic version of a general purpose functional programming language as a method of modeling stochastic processes. The language contains random choices, conditional...
New upper bounds for satisfiability in modal logics -- the case-study of modal K (1997)
Roberto Sebastiani, David Mcallester
Traditional results in modal logics state that, if a formula ' is satisfiable in K (K-satisfiable), then it has a Kripke model M s.t. jjM jj 2 j'j , jjM jj being the number of states of M...
Linear-time Subtransitive Control Flow Analysis (1997)
Nevin Heintze, David Mcallester
We present a linear-time algorithm for boundedtype programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) Control-Flow Analysis (CFA)...
On the Cubic Bottleneck in Subtyping and Flow Analysis (1997)
Nevin Heintze, David Mcallester
A variety of program analysis methods have worst case time complexity that grows cubicly in the length of the program being analyzed. Cubic complexity typically arises in control flow analyses and...
On the Complexity of Set-Based Analysis (1997)
David Mcallester, Nevin Heintze
: We formally define the set-based abstraction of any language whose operational semantics can be defined by environment evaluation. The Aiken-Wimmers soft type system precisely corresponds to this...
Effective Bayesian Inference for Stochastic Programs (1997)
Daphne Koller Stanford, Daphne Koller, David Mcallester, Avi Pfeffer
In this paper, we propose a stochastic version of a general purpose functional programming language as a method of modeling stochastic processes. The language contains random choices, conditional...
On the Complexity of Set-Based Analysis (1997)
Nevin Heintze, David Mcallester
: We define a general notion of set-based analysis --- any language whose operational semantics is defined by environment evaluation has a well defined set-based abstraction. This general definition...
On the Cubic Bottleneck in Subtyping and Flow Analysis (1997)
Nevin Heintze, David Mcallester
We prove that certain data-flow and control-flow problems are 2NPDA-complete. This means that these problems are in the class 2NPDA and that they are hard for that class. The fact that they are in...
Linear-time Subtransitive Control Flow Analysis (1997)
Nevin Heintze David, David Mcallester
We present a linear-time algorithm for boundedtype programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) Control-Flow Analysis (CFA)...
Solving Polynomial Systems Using a Branch and Prune Approach (1997)
Pascal Van Hentenryck, David Mcallester, Deepak Kapur
Abstract. This paper presents Newton, a branch and prune algorithm used to find all isolated solutions of a system of polynomial constraints. Newton can be characterized as a global search method...
Ten challenges in propositional reasoning and search (1997)
Bart Selman, Henry Kautz, David Mcallester
The past several years have seen much progress in the area of propositional reasoning and satisfiability testing. There is a growing consensus by researchers on the key technical challenges that need...
Tarskian set constraints (1996)
Robert Givan, Dexter Kozen, David Mcallester, Carl Witty
Abstract: We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the...
Encoding Plans in Propositional Logic (1996)
Henry Kautz, David Mcallester, Bart Selman
In recent work we showed that planning problems can be efficiently solved by general propositional satisfiability algorithms (Kautz and Selman 1996). A key issue in this approach is the development...
Variational Attribute Grammars for Computer Aided Design." ADAGE-MIT94 -01 (1996)
Abstract: This document describes a variational attribute grammar (VAG) design language and release 3.0 of the VAG implementation. VAG is a functional programming language specifically designed for...
Variational Attribute Grammars for Computer Aided Design." ADAGE-MIT94 -01 (1996)
Abstract: This document describes a variational attribute grammar (VAG) design language. VAG is a functional programming language specifically designed for the rapid implementation of domain specific...
Variational Attribute Grammars for Computer Aided Design." ADAGE-MIT94 -01 (1996)
Abstract: This document describes a variational attribute grammar (VAG) design language and release 3.0 of the VAG implementation. VAG is a functional programming language specifically designed for...
Encoding Plans in Propositional Logic (1996)
Henry Kautz David, David Mcallester, Bart Selman
In recent work we showed that planning problems can be efficiently solved by general propositional satisfiability algorithms (Kautz and Selman 1996). A key issue in this approach is the development...
Tarskian Set Constraints (1996)
Robert Givan, Robert Givan, David Mcallester, David Mcallester, Carl Witty, Carl Witty, ...
We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the meaning...
Control-Flow Analysis for ML in Linear Time (1996)
Nevin Heintze, David Mcallester
Standard control-flow analysis (often called 0-CFA) is thought to be a cubic time problem --- the standard algorithm for it is cubic time and the conventional wisdom is that this algorithm cannot be...
David Mcallester, Kostas Arkoudas
. Primitive recursion is a well known syntactic restriction on recursive definitions which guarantees termination. Unfortunately many natural definitions, such as the most common definition of...
Tarskian Set Constraints (1996)
Robert Givan, Dexter Kozen, David Mcallester, Carl Witty
: We investigate set constraints over set expressions with Tarskian functional and relational operations. Unlike the Herbrand constructor symbols used in recent set constraint formalisms, the meaning...
Proceedings of ECAI-96 Workshop: Empirical AI (1996)
Toby Walsh (ed.), Toby Walsh (editor, Paul Cohen, Ian Gent, David Mcallester, Steve Muggleton, ...
inference patterns reversed-engineered from previously successful expert systems are not a productivity tool [2]. These isolated MIP experiments must be explored. If they prove to be a general...
Natural Language Syntax and Semantics (1994)
David McAllester, Categorial Grammar
ere is a strong analogy between the notion of grammatical sentences in natural languages such as English and the notion of well typed expressions in computer programs. Consider a function SQUARE...
Automatic recognition of tractability in inference relations (1993)
Abstract: A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the...
Taxonomic syntax for first order inference (1993)
David Mcallester, Robert Givan
Most knowledge representation languages are based on classes and taxonomic relationships between classes. Taxonomic hierarchies without defaults or exceptions are semantically equivalent to a...
Introduction Common sense reasoning is usually uncertain. If you see someone walking into a lecture with wet hair you might conclude that it is raining outside. This conclusion could, of course, be...
We present a term rewriting procedure based on congruence closure that can be used with arbitrary equational theories. This procedure is motivated by the pragmatic need to prove equations in...
Natural language syntax and first order inference (1992)
David Mcallester, Robert Givan
Abstract: We have argued elsewhere that first order inference can be made more efficient by using non-standard syntax for first order logic. In this paper we define a syntax for first order logic...
Constraint Satisfaction Problems (1992)
at first generates a list of all the possible ways eight queens can be placed a chess board and then tests each possibility to see if it is a solution to the problem. Another example is the SAT...
Resolution Theorem Proving (1992)
ground procedure. The first step in constructing the ground procedure is to convert inference problems to a simple normal form. 1 Clausal Normal Form Resolution is a refutation technique. To show...
Natural Language Syntax and First Order Inference (1992)
David Mcallester, Robert Givan
: We have argued elsewhere that first order inference can be made more efficient by using non-standard syntax for first order logic. In this paper we define a syntax for first order logic based on...
New Results on Local Inference Relations (1992)
Robert Givan, David Mcallester
We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom up evaluation terminates in polynomial time. The local...
er logic can still be adequate programming languages. Mathematicians have used first order logic as a programming language in which to encode all the known acceptable principles of mathematical...
. We present a term rewriting procedure based on congruence closure that can be used with arbitrary equational theories. This procedure is motivated by the pragmatic need to handle equational...
Tractable Inference Relations (1991)
Givan, Robert, McAllester, David
We consider the concept of local sets of inference rules. Locality is a syntactic condition on rule sets which guarantees that the inference relation defined by those rules is polynomial time...
Lifting Transformations (1991)
McAllester, David, Siskind, Jeffrey
Lifting is a well known technique in resolution theorem proving, logic programming, and term rewriting. In this paper we formulate lifting as an efficiency-motivated program transformation applicable...
Natural Language Based Inference Procedures Applied to Schubert's Steamroller (1991)
Givan, Robert, McAllester, David, Shalaby, Sameer
We have previously argued that the syntactic structure of natural language can be exploited to construct powerful polynomial time inference procedures. This paper supports the earlier arguments by...
Observations on Cognitive Judgments (1991)
It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...
We present a term rewriting procedure based on congruence closure that can be used with arbitrary equational theories. This procedure is motivated by the pragmatic need to prove equations in...
Systematic Nonlinear Planning (1991)
McAllester, David, Rosenblatt, David
This paper presents a simple, sound, complete, and systematic algorithm for domain independent STRIPS planning. Simplicity is achieved by starting with a ground procedure and then applying a general...
Systematic Nonlinear Planning (1991)
McAllester, David, Rosenblatt, David
This paper presents a simple, sound, complete, and systematic algorithm for domain independent STRIPS planning. Simplicity is achieved by starting with a ground procedure and then applying a general...
We present a term rewriting procedure based on congruence closure that can be used with arbitrary equational theories. This procedure is motivated by the pragmatic need to prove equations in...
Observations on Cognitive Judgments (1991)
It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...
Natural Language Based Inference Procedures Applied to Schubert's Steamroller (1991)
Givan, Robert, McAllester, David, Shalaby, Sameer
We have previously argued that the syntactic structure of natural language can be exploited to construct powerful polynomial time inference procedures. This paper supports the earlier arguments by...
Lifting Transformations (1991)
McAllester, David, Siskind, Jeffrey
Lifting is a well known technique in resolution theorem proving, logic programming, and term rewriting. In this paper we formulate lifting as an efficiency-motivated program transformation applicable...
Tractable Inference Relations (1991)
Givan, Robert, McAllester, David
We consider the concept of local sets of inference rules. Locality is a syntactic condition on rule sets which guarantees that the inference relation defined by those rules is polynomial time...
Systematic nonlinear planning (1991)
David Mcallester, David Rosenblitt
This paper presents a simple, sound, complete, and systematic algorithm for domain independent STRIPS planning. Simplicity is achieved by starting with a ground procedure and then applying a general,...
Systematic nonlinear planning (1991)
David Mcallester, David Rosenblitt
This paper presents a simple, sound, complete, and systematic algo-rithm for domain independent STRIPS planning. Simplicity is chieved by staxting with a ground procedure and then applying a general,...
Some Observations on Cognitive Judgments (1991)
It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...
Some Observations on Cognitive Judgments (1991)
It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...
Natural Language Based Inference Procedures applied to Schubert's Steamroller (1991)
Robert Givan, David Mcallester, Sameer Shalaby
We have previously argued that the syntactic structure of natural language can be exploited to construct powerful polynomial time inference procedures. This paper supports the earlier arguments by...
Observations on Cognitive Judgments (1991)
It is obvious to anyone familiar with the rules of the game of chess that a king on an empty board can reach every square. It is true, but not obvious, that a knight can reach every square. Why is...
Principles of Metareasoning (1991)
Stuart Russell, Eric Wefald, Maurice Karnaugh, Richard Karp, David Mcallester, Devika Subramanian, ...
In this paper we outline a general approach to the study of metareasoning, not in the sense of explicating the semantics of explicitly specified meta-level control policies, but in the sense of...
Systematic Nonlinear Planning (1991)
David Mcallester, David Rosenblitt
This paper presents a simple, sound, complete, and systematic algorithm for domain independent STRIPS planning. Simplicity is achieved by starting with a ground procedure and then applying a general,...
DEPENDENCY DIRECTED BACKTRACKING IN GENERALIZED SATISFICING ASSIGNMENT PROBLEMS (1990)
Croker, Albert, Dhar, Vasant, McAllester, David
Many authors have described search techniques for the satisficing assignment problem: the problem of finding an interpretation for a set of discrete variables that satisfies a given set of...
DEPENDENCY DIRECTED BACKTRACKING IN GENERALIZED SATISFICING ASSIGNMENT PROBLEMS (1990)
Croker, Albert, Dhar, Vasant, McAllester, David
Many authors have described search techniques for the satisficing assignment problem: the problem of finding an interpretation for a set of discrete variables that satisfies a given set of...
DEPENDENCY DIRECTED BACKTRACKING IN GENERALIZED SATISFICING ASSIGNMENT PROBLEMS (1990)
Croker, Albert, Dhar, Vasant, McAllester, David
Many authors have described search techniques for the satisficing assignment problem: the problem of finding an interpretation for a set of discrete variables that satisfies a given set of...
DEPENDENCY DIRECTED BACKTRACKING IN GENERALIZED SATISFICING ASSIGNMENT PROBLEMS (1990)
Croker, Albert, Dhar, Vasant, McAllester, David
Many authors have described search techniques for the satisficing assignment problem: the problem of finding an interpretation for a set of discrete variables that satisfies a given set of...
Automatic Recognition of Tractability in Inference Relations (1990)
A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference...
Automatic Recognition of Tractability in Inference Relations (1990)
A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference...
Nonexpressibility of Fairness and Signaling (1990)
David Mcallester, Prakash Panangaden, Vasant Shanbhogue
In this paper we establish new expressiveness results for indeterminate dataflow primitives. We consider split primitives with three differing fairness assumptions and show that they are strictly...
General purpose truth maintenance systems have received considerable attention in the past few years. This paper discusses the functionality of truth maintenance systems and compares various existing...
Albert Croker, Leonard N. Stern, Vasant Dhar, David Mcallester
Many authors have described search techniques for the satisficing assignment problem: the problem of finding an interpretation for a set of discrete variables that satisfies a given set of...
Natural Language Syntax and First Order Preference (1989)
McAllester, David, Givan, Robert
We have argued elsewhere that first order inference can be made more efficient by using non-standard syntax for first order logic. In this paper we show how a fragment of English syntax under...
Natural Language Syntax and First Order Preference (1989)
McAllester, David, Givan, Robert
We have argued elsewhere that first order inference can be made more efficient by using non-standard syntax for first order logic. In this paper we show how a fragment of English syntax under...
Taxonomic Syntax for First-Order Inference (1989)
McAllester, David, Givan, Robert
Most knowledge representation languages are based on classes and taxonomic relationships between classes. Taxonomic hierarchies without defaults or exceptions are semantically equivalent to a...
Taxonomic Syntax for First-Order Inference (1989)
McAllester, David, Givan, Robert
Most knowledge representation languages are based on classes and taxonomic relationships between classes. Taxonomic hierarchies without defaults or exceptions are semantically equivalent to a...
Nonexpressibility of Fairness and Signaling (1989)
McAllester, David, Panangaden, Prakash
In this paper, we establish new expressiveness results for indeterminate dataflow primitives. We consider choice primitives with three differing fairness assumptions and show that they are strictly...
Nonexpressibility of Fairness and Signaling (1989)
McAllester, David, Panangaden, Prakash
In this paper, we establish new expressiveness results for indeterminate dataflow primitives. We consider choice primitives with three differing fairness assumptions and show that they are strictly...
A Rearrangement Search Strategy for Determining Propositional Satisfiability (1988)
We present a simple algorithm for determining the satisfiability of propositional formulas in Conjunctive Normal Form. As the procedure searches for a satisfying truth assignment it dynamically...
McAllester, David, Zabih, Ramin
Object-oriented programming languages all involve the notions of class and object. We extend the notion of class so that any Boolean combination of classes is also a class. Boolean classes allow...
McAllester, David, Zabih, Ramin
Object-oriented programming languages all involve the notions of class and object. We extend the notion of class so that any Boolean combination of classes is also a class. Boolean classes allow...
Abstract. Object-oriented programming languages all involve the notions of class and object. We extend the notion of class so that any Boolean combination of classes is also a class. Boolean classes...
Comparing Policy-Gradient Algorithms (1983)
Richard S. Sutton, Satinder Singh, David Mcallester
We present a series of formal and empirical results comparing the efficiency of various policy-gradient methods—methods for reinforcement learning that directly update a parameterized policy...
Inferring Recursive Data Types
. This paper contains five results on the problem of inferring types. The first is that type inference over recursive types with unions and data constructors can be done in cubic time using a flow...
Concentration Inequalities for the Missing Mass and for Histogram Rule Error
This paper gives distribution-free concentration inequalities for the missing mass and the error rate of histogram rules. Negative association methods can be used to reduce these concentration...