justin

Today I read a paper titled “Approximate Graph Coloring by Semidefinite Programming”

The abstract is:
We consider the problem of coloring k-colorable graphs with the fewest possible colors.

We present a randomized polynomial time algorithm that colors a 3-colorable graph on $n$ vertices with min O(Delta^{1/3} log^{1/2} Delta log n), O(n^{1/4} log^{1/2} n) colors where Delta is the maximum degree of any vertex.

Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree Delta.

This result can be generalized to k-colorable graphs to obtain a coloring using min O(Delta^{1-2/k} log^{1/2} Delta log n), O(n^{1-3/(k+1)} log^{1/2} n) colors.

Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems.

An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz theta-function.

We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the theta-function.

Today I read a paper titled “Synthesizing Customized Planners from Specifications”

The abstract is:
Existing plan synthesis approaches in artificial intelligence fall into two categories — domain independent and domain dependent.

The domain independent approaches are applicable across a variety of domains, but may not be very efficient in any one given domain.

The domain dependent approaches need to be (re)designed for each domain separately, but can be very efficient in the domain for which they are designed.

One enticing alternative to these approaches is to automatically synthesize domain independent planners given the knowledge about the domain and the theory of planning.

In this paper, we investigate the feasibility of using existing automated software synthesis tools to support such synthesis.

Specifically, we describe an architecture called CLAY in which the Kestrel Interactive Development System (KIDS) is used to derive a domain-customized planner through a semi-automatic combination of a declarative theory of planning, and the declarative control knowledge specific to a given domain, to semi-automatically combine them to derive domain-customized planners.

We discuss what it means to write a declarative theory of planning and control knowledge for KIDS, and illustrate our approach by generating a class of domain-specific planners using state space refinements.

Our experiments show that the synthesized planners can outperform classical refinement planners (implemented as instantiations of UCP, Kambhampati & Srivastava, 1995), using the same control knowledge.

We will contrast the costs and benefits of the synthesis approach with conventional methods for customizing domain independent planners..

Today I read a paper titled “A Quantum Algorithm for Finding the Minimum”

The abstract is:
We give a quantum algorithm to find the index y in a table T of size N such that in time O(c sqrt N), T[y] is minimum with probability at least 1-1/2^c.

Today I read a paper titled “Learning the Past Tense of English Verbs: The Symbolic Pattern Associator vs. Connectionist Models”

The abstract is:
Learning the past tense of English verbs – a seemingly minor aspect of language acquisition – has generated heated debates since 1986, and has become a landmark task for testing the adequacy of cognitive modeling.

Several artificial neural networks (ANNs) have been implemented, and a challenge for better symbolic models has been posed.

In this paper, we present a general-purpose Symbolic Pattern Associator (SPA) based upon the decision-tree learning algorithm ID3.

We conduct extensive head-to-head comparisons on the generalization ability between ANN models and the SPA under different representations.

We conclude that the SPA generalizes the past tense of unseen verbs better than ANN models by a wide margin, and we offer insights as to why this should be the case.

We also discuss a new default strategy for decision-tree learning algorithms..