Speaker: Tanya Berger-Wolf, UIUC
Title: Bandwidth of Products of Cliques
Abstract
We consider the problem of bandwidth minimization for a k-dimensional Hamming graph (Cartesian product of cliques). We give a tight lower bound and an optimal algorithm for a product of any number of cliques of arbitrary sizes.
This is joint work with Mitch Harris, UIUC.
Speaker: Daniel Stefankovic, U. of Chicago
Title: Decidability of String Graphs
Abstract
We show that string graphs can be recognized in non-deterministic exponential time by giving an exponential upper bound on the number of intersections for a drawing realizing the string graph in the plane. This upper bound confirms a conjecture by Kratochvíl and Matoušek and settles the long-standing open problem of the decidability of string graph recognition. Finally we show how to apply the result to solve another old open problem: deciding the existence of Euler diagrams, a central problem of topological inference.
This is joint work with Marcus Schaefer, DePaul U.
Speaker: Judy Goldsmith, U. of Kentucky
Title: The Bayesian Advisor Project
Abstract
The Bayesian Advisor Project models academic advising processes as stochastic controlled systems: although we can choose courses for a student, we can only probabilistically predict the outcome (grades) of our choices, based on their previous record. If we model this system as a Bayes net, we can apply various planning algorithms to suggest next sets of courses to optimize the student's utility function, which presumably involves GPA and time to graduation, as well as the maximum number of courses from cool profs like Goldsmith and Dekhtyar. We will describe the underlying mathematical model (Bayes nets) and some of the privacy issues that this work raises. We will describe initial work on automatic data discovery tools and knowledge elicitation tools, and mention issues in the implementation of probabilistic data bases.
Complexity analysis will be mentioned in passing, but no theorems will be proved.
This is joint work with Alex Dekhtyar, Ryan Hunt, and Sean Hawkes.
Speaker: Pradyut Shah, U. of Chicago
Title: Lower Bounds for Parallel Algorithms
Abstract
We show that it is impossible to compute the maximum blocking flow in a graph within time o(n1/4) using polynomially many processors on a parallel RAM without bit operations.
The problem of computing the blocking flow is an important component in many network flow algorithms. It is of independent theoretical interest as well.
The talk will concentrate both on the result as well as the general technique which can be used to give strong lower bounds for combinatorial optimization problems on a PRAM without bit operations.
This is joint work with Ketan Mulmuley (U. of Chicago and Indian Institute of Technology, Bombay).
Speaker: Alex Dekhtyar, U. of Kentucky
Title: Possible world semantics
Abstract
Possible Worlds Semantics (with probability distribution over the set of possible worlds) has been a popular model for probabilistic logics for years. Therefore, it is reasonable to expect that Probabilistic Logic Programming paradigms should have Possible Worlds Semantics as model theory.
Possible Worlds Semantics assigns each formula a point probability. Some Logic Programming frameworks associate probability intervals with formulas (due to the fact that even if point probabilities of some events are known, it is not always possible to computer point probabilities of their combinations). Because of this difference in the type of probability assignments, the correspondence between Possible Worlds interpretations of Probabilistic Logic Programs and their fixpoint semantics is more complex.
In this work, we will consider the Probabilistic Logic Programs (PLPs) of Ng and Subrahmanian (1993). For years, it was thought that model theoretic/fixpoint semantics of PLPs as provided by Ng and Subrahmanian matches the Possible Worlds Semantics, i.e., the fixpoint of a probabilistic logic program correctly describes the set of Possible Worlds interpretations satisfying the program. This, however, turns out not to be so.
Our current goal is to develop new fixpoint semantics for Probabilistic Logic Programs of Ng and Subrahmanian, which would correspond to the Possible Worlds models of PLPs.
We will briefly look at PLPs and their model-theoretic and fixpoint semantics and then we will discuss what needs to be done to describe the set of Possible Worlds interpretations that satisfy a given PLP.
Speaker: Samuel Kutin, U. of Chicago
Title: Sensitivity, block sensitivity, and l-block sensitivity
Abstract
Many authors have discussed the relationship between the sensitivity and block sensitivity of a Boolean function. The main open question is whether or not a polynomial relationship exists between these quantities. We provide an improved (though still exponential) upper bound on block sensitivity in terms of sensitivity, as well as a number of useful lemmas which close off some possible techniques for constructing functions with a large gap between the two quantities. We prove our main result using the notion of l-block sensitivity, in which the block size is restricted, and slightly improve the known bounds relating this quantity to sensitivity.
Speaker: Bob Sloan, UIC
Title: Theory funding by the NSF
Abstract
This is not a research talk but a brief presentation by Bob on NSF theory funding, particularly ITR.