Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Plenary Lectures

On-Line Algorithms, Real Time, the Virtue of Laziness, and the Power of Clairvoyance

In several practical circumstances we have to solve a problem whose instance is not a priori completely known. Situations of this kind occur in computer systems and networks management, in financial decision making, in robotics etc. Problems that have to be solved without a complete knowledge of the instance are called

on

 − 

line

problems

. The analysis of properties of on-line problems and the design of algorithmic techniques for their solution (

on

 − 

line

algorithms

) have been the subject of intense study since the 70-ies, when classical algorithms for scheduling tasks in an on-line fashion [22] and for handling paging in virtual storage systems [11] have been first devised. In the 80-ies formal concepts for analyzing and measuring the quality of on-line algorithms have been introduced [40] and the notion of

competitive

analysis

has been defined as the ratio between the value of the solution that is obtained by an on-line algorithm and the value of the best solution that can be achieved by an optimum off-line algorithm that has full knowledge of the problem instance. Since then a very broad variety of on-line problems have been addressed in the literature [14, 19]: memory allocation and paging, bin packing, load balancing in multiprocessor systems, updating and searching a data structure (e.g. a list), scheduling, financial investment, etc.

Giorgio Ausiello, Luca Allulli, Vincenzo Bonifaci, Luigi Laura

Similarity of Objects and the Meaning of Words

We survey the emerging area of compression-based, parameter-free, similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like “red” or “christianity.” For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular features between pairs of literal objects. For the second type we consider similarity distances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches.

Rudi Cilibrasi, Paul Vitanyi

Totally < ω ω Computably Enumerable and m-topped Degrees

In this paper we will discuss recent work of the authors (Downey, Greenberg and Weber [8] and Downey and Greenberg [6, 7]) devoted to understanding some new naturally definable degree classes which capture the dynamics of various natural constructions arising from disparate areas of classical computability theory.

It is quite rare in computability theory to find a single class of degrees which capture precisely the underlying dynamics of a wide class of apparently similar constructions, demonstrating that they all give the same class of degrees. A good example of this phenomenon is work pioneered by Martin [22] who identified the high c.e. degrees as the ones arising from dense simple, maximal, hh-simple and other similar kinds of c.e. sets constructions. Another example would be the example of the promptly simple degrees by Ambos-Spies, Jockusch, Shore and Soare [2]. Another more recent example of current great interest is the class of K-trivial reals of Downey, Hirscheldt, Nies and Stephan [5], and Nies [23, 24].

Rod Downey, Noam Greenberg

Mitosis in Computational Complexity

This expository paper describes some of the results of two recent research papers [GOP+05, GPSZ05]. The first of these papers proves that every NP-complete set is many-one autoreducible. The second paper proves that every many-one autoreducible set is many-one mitotic. It follows immediately that every NP-complete set is many-one mitotic. Hence, we have the compelling result that every NP-complete set

A

splits into two NP-complete sets

A

1

and

A

2

.

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

Models of Intuitionistic Set Theories over Partial Combinatory Algebras

This paper presents two types of realizability models for intuitionistic set theories. The point of departure for every notion of realizability will be a domain of computation, called a

partial combinatory algebra

,

PCA

. To put it roughly, the role of a

PCA

in the first type of realizability is to furnish a concrete instantiation of the Brouwer-Heyting-Kolmogorov interpretation of the logical connectives. In a sense, partial combinatory algebras can lay claim to be of equal importance to models of intuitionistic set theory as partial orderings are to forcing models of classical set theory.

Among other things, these models can be used to extract computational information from proofs. Their main employment here, however, will be to provide consistency, equiconsistency, and independence results. Relinquishing classical logic can bring forth considerable profits. It allows for axiomatic freedom in that one can adopt new axioms that are true in realizability models but utterly false classically.

Michael Rathjen

Width Versus Size in Resolution Proofs

The complexity of resolution refutations of contradictory sets of clauses in propositional logic has been investigated deeply over the last forty years, beginning with the groundbreaking paper of Tseitin [16], based on a talk given in a Leningrad seminar of 1966.

A general theme that emerged gradually in the course of the intensive investigations of the last few decades has been that of basing

size

lower bounds on lower bounds on the

width

of refutations. Roughly speaking, it turns out that in many cases, the minimum size of a refutation is exponential in the minimum width.

Alasdair Urquhart

Recent Progress in Quantum Computational Complexity

With rapid advances in technology, it appears that computing and communication devices based on quantum principles may become available in the not too distant future. A central question addressed by the emerging research field

quantum computational complexity

is: how much can quantum devices speed up computation and communication over classical devices? In this talk we discuss recent developments in quantum computational complexity regarding communication complexity, query complexity and interactive proofs. We also examine directions for future research.

Andrew C. Yao

Algorithm

On Several Scheduling Problems with Rejection or Discretely Compressible Processing Times

In the traditional scheduling problems, it is always assumed that any job has to be processed and the processing time is pre-given and fixed. In this paper, we address the scheduling problems with rejection or with discretely compressible processing times in which we can choose a subset of jobs to process or discretely compress the original processing times. Of course, choosing not to process any job or to process it with a compressed processing time incurs a corresponding penalty or cost. We consider the following problems for the first time: scheduling with discretely compressible processing times to minimize makespan with the constraint of total compression cost, scheduling with rejection to minimize the total weighted completion time with the constraint of total penalties and scheduling with discretely compressible processing times to minimize the sum of total weighted completion time plus total compression cost. We show that they are all NP-hard and design pseudo-polynomial time algorithms through dynamic programming and FPTASs for the first two problems. For the third problem, we present a greedy heuristic. Theoretical analysis shows that it has a bounded worst case performance ratio for a special case and large numbers of simulations tell us that it works very well for the general problem.

Zhigang Cao, Zhen Wang, Yuzhong Zhang, Shoupeng Liu

LS-SVM Based on Chaotic Particle Swarm Optimization with Simulated Annealing

The generalization performance of LS-SVM depends on a good setting of its parameters. Chaotic particle swarm optimization (CPSO) with simulated annealing algorithm (SACPSO) is proposed to choose the parameters of LS-SVM automatically. CPSO adopts chaotic mapping with certainty, ergodicity and the stochastic property, possessing high search efficiency. SA algorithm employs certain probability to improve the ability of PSO to escape from a local optimum. The results show that the proposed approach has a better generalization performance and is more effective than LS-SVM based on particle swarm optimization.

Ai-ling Chen, Zhi-ming Wu, Gen-ke Yang

A Bounded Item Bin Packing Problem over Discrete Distribution

In this paper we formulate a bounded item bin packing problem over discrete distribution (BIBPPOD) in computer and communication networks, and consider the average performance ratio for next fit algorithm. An efficient average-case analysis procedure for finding the average performance ratio and problem solution is demonstrated. We give the closed-form expression for some special range to which the bounded item belongs. Our result is useful for designing the length in fixed-size format or evaluating the performance impacted by the protocol header in computer and communication network.

Jianxin Chen, Yuhang Yang, Hong Zhu, Peng Zeng

Scheduling Jobs on a Flexible Batching Machine: Model, Complexity and Algorithms

Normal batching machine scheduling problems are assumed that the capacity of the machine, the maximum number of jobs that the machine can handle up to simultaneously, is fixed. However, in some realistic situations, the capacity of a machine is not constant. We call it a flexible batching machine. In this paper, we address the problem of scheduling jobs on a flexible batching machine to minimize the makespan. We prove that the problem is strong NP-hard, and its two agreeable cases are NP-hard. Then two pseudo-polynomial algorithms for the two cases are presented respectively.

Baoqiang Fan, Guochun Tang

Faster Algorithms for Sorting by Transpositions and Sorting by Block-Interchanges

In this paper, we present a new data structure–permutation tree to improve the running time of sorting permutation by transpositions and sorting permutation by block-interchanges. The 1.5-approximation algorithm for sorting permutation by transpositions has time complexity

$O(n^{\frac{3}{2}} \sqrt{log n})$

. By the permutation tree, we can improve this algorithm to achieve time complexity

O

(

nlogn

). We can also improve the algorithm for sorting permutation by block interchanges to make its time complexity from

O

(

n

2

) down to

O

(

nlogn

).

Jianxing Feng, Daming Zhu

An ACO-Based Approach for Task Assignment and Scheduling of Multiprocessor Control Systems

In order to solve whether a set of periodic tasks can be assigned to a set of identical processors in such a way that all timing constraints can be met, the model of travelling salesman problem is used to describe the task assignment and scheduling in real-time multiprocessor control systems. Combined with the scheduling characteristics of multiprocessor systems, a new feasible algorithm based on ant colony optimization metaheuristic is presented for solving this problem. Both the scheduling performance index and the control performance index are proposed and used as fitness functions of optimization. Simulation results show that the proposed approach can solve the task assignment and scheduling problem in multiprocessor control systems.

Hong Jin, Hui Wang, Hongan Wang, Guozhong Dai

Adversary Immune Size Approximation of Single-Hop Radio Networks

We design a time and energy efficient algorithm concerning size approximation for single-hop radio networks. The most important feature of the algorithm is that it is immune against an adversary that may scramble a certain number of communication steps. The previous algorithms presented in the literature provide false estimations if an adversary causes certain communication collisions.

J̧edrzej Kabarowski, Mirosław Kutyłowski, Wojciech Rutkowski

On Load-Balanced Semi-matchings for Weighted Bipartite Graphs

A

semi-matching

on a bipartite graph

G

=(

U

V

,

E

) is a set of edges

X

 ⊆ 

E

such that each vertex in

U

is incident to exactly one edge in

X

. The sum of the weights of the vertices from

U

that are assigned (semi-matched) to some vertex

v

V

is referred to as the

load

of vertex

v

. In this paper, we consider the problem to finding a semi-matching that minimizes the maximum load among all vertices in

V

. This problem has been shown to be solvable in polynomial time by Harvey et. al [3] and Fakcharoenphol et. al [5] for unweighted graphs. However, the computational complexity for the weighted version of the problem was left as an open problem. In this paper, we prove that the problem of finding a semi-matching that minimizes the maximum load among all vertices in a weighted bipartite graph is NP-complete. A

$\frac{3}{2}$

-approximation algorithm is proposed for this problem.

Chor Ping Low

Analyzing Chain Programs over Difference Constraints

Chain Programming is a restricted form of Linear Programming; in a Chain Program, there exists a total ordering on the program variables. In other words, the constraints

x

1

x

2

...

x

n

are either implicitly or explicitly part of the constraint system. At the present juncture, it is not clear whether an arbitrary linear program augmented with a chain is easier to solve than linear programs in general, either asymptotically or computationally. However, if the linear program is constituted entirely of difference constraints, then the total ordering results in a number of interesting properties, which are not true of constraint systems in general. Inasmuch as difference constraint logic is an integral part of a number of verification problems in both model-checking and real-time scheduling, our results are of particular importance to these communities.

K. Subramani, John Argentieri

Linear-Time 2-Approximation Algorithm for the Watchman Route Problem

Given a simple polygon

P

of

n

vertices, the

watchman route problem

asks for a shortest (closed) route inside

P

such that each point in the interior of

P

can be seen from at least one point along the route. We present a simple, linear-time algorithm for computing a watchman route of length at most 2 times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes

O

(

n

4

log

n

) time, which is too complicated to be suitable in practice.

This paper also involves an optimal

O

(

n

) time algorithm for computing the set of so-called

essential cuts

, which are the line segments inside the polygon

P

such that any route visiting them is a watchman route. It solves an intriguing open problem by improving the previous

O

(

n

log

n

) time result, and is thus of interest in its own right.

Xuehou Tan

Further Properties of Cayley Digraphs and Their Applications to Interconnection Networks

In this short communication, we extend the known relationships between Cayley digraphs and their subgraphs and coset graphs with respect to subgroups and obtain some general results on homomorphism and distance between them. Intuitively, our results correspond to synthesizing alternative, more economical, interconnection networks by reducing the number of dimensions and/or link density of existing networks via mapping and pruning. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes.

Wenjun Xiao, Behrooz Parhami

Real Time Critical Edge of the Shortest Path in Transportation Networks

In transportation networks, a vehicle always travels longer than the shortest path due to sudden edge failure caused by unexpected events such as accident. In this situation, which edge failure results in the maximum of the travel distance between the source node and the destination node? If we know the edge, we can reduce the transportation cost and improve the networks structure. Regarding this problem, the most vital edge (MVE) problem considers in a global view and from the perspective of static decision-making based on complete information, while the longest detour (LD) problem solves in a local view and in terms of real time. This paper reconsiders this problem in a global view and in terms of real time. We propose the real time critical edge (RTCE) problem of the shortest path, and present an

O

(

n

2

) time algorithm by constructing the shortest path tree. Then, by giving a numerical example of urban transportation networks, we compare the results of MVE, LD and RTCE, and conclude that the RTCE problem has more practical significance.

Yinfeng Xu, Huahai Yan

Finding Min-Sum Disjoint Shortest Paths from a Single Source to All Pairs of Destinations

Given a graph

G

= (

V

,

E

) with |

V

| =

n

, |

E

| =

m

, and a source node

s

, we consider the problem of finding two disjoint paths from

s

to two destination nodes

t

1

and

t

2

with minimum total length, for every pair nodes

t

1

,

t

2

V

–{

s

}. One efficient solution is to transform this problem into the problem of finding shortest pairs of disjoint paths, and use the Suurablle-Tarjan algorithm to solve the new problem in

O

(

n

2

log

n

) time and

O

(

n

2

) space. We present an algorithm that solves this problem in

O

(

n

2

) time and

O

(

n

2

) space, with the solution paths are implicitly represented. Given such a representation, the time necessary to explicitly construct all the solution paths is

O

(1) for each edge on the paths. Based on this algorithm, we present another algorithm that solves this problem in

O

(

m

log

1 + 

m

/

n

)

n

time and

O

(

m

) space, with the compromise of longer searching time on solution paths.

Bing Yang, S. Q. Zheng

A New Approximation Algorithm for the k-Facility Location Problem

The

k

-facility location problem is a common generalization of the facility location and the

k

-median problems. For the metric uncapacitated

k

-facility location problem, we propose a polynomial-time 2 +

$\sqrt{3} + \epsilon$

-approximation algorithm using the local search approach, which significantly improves the previously known approximation ratio 4, given by Jain et al. using the greedy method (J. ACM 50 (2003) 795–824).

Peng Zhang

Computational Complexity

Alternative Measures of Computational Complexity with Applications to Agnostic Learning

We address a fundamental problem of complexity theory – the inadequacy of worst-case complexity for the task of evaluating the computational resources required for real life problems. While being the best known measure and enjoying the support of a rich and elegant theory, worst-case complexity seems gives rise to over-pessimistic complexity values. Many standard task, that are being carried out routinely in machine learning applications, are NP-hard, that is, infeasible from the worst-case-complexity perspective. In this work we offer an alternative measure of complexity for approximations-optimization tasks. Our approach is to define a hierarchy on the set of inputs to a learning task, so that natural (’real data’) inputs occupy only bounded levels of this hierarchy and that there are algorithms that handle in polynomial time each such bounded level.

Shai Ben-David

Disjoint NP-Pairs from Propositional Proof Systems

For a proof system

P

we introduce the complexity class

DNPP

(

P

) of all disjoint

NP

-pairs for which the disjointness of the pair is efficiently provable in the proof system

P

. We exhibit structural properties of proof systems which make the previously defined canonical

NP

-pairs of these proof systems hard or complete for

DNPP

(

P

). Moreover we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for

DNPP

(

P

) and the reductions between the canonical pairs exist.

Olaf Beyersdorff

Valiant’s Holant Theorem and Matchgate Tensors

We propose

matchgate tensors

as a natural and proper language to develop Valiant’s new theory of Holographic Algorithms. We give a treatment of the central theorem in this theory—the Holant Theorem—in terms of matchgate tensors. Some generalizations are presented.

Jin-Yi Cai, Vinay Choudhary

Variable Minimal Unsatisfiability

In this paper, we present variable minimal unsatisfiability (VMU), which is a generalization of minimal unsatisfiability (MU). A characterization of a VMU formula

F

is that every variable of

F

is used in every resolution refutation of

F

. We show that the class of VMU formulas is

D

P

-complete. For fixed deficiency (the difference of the number of clauses and the number of variables), the VMU formulas can be solved in polynomial time. Furthermore, we investigate more subclasses of VMU formulas. Although the theoretic results on VMU and MU are similar, some observations are shown that the extraction of VMU may be more practical than MU in some cases.

Zhenyu Chen, Decheng Ding

A New Lower Bound of Critical Function for (k,s)-SAT

(

k

,

s

)–SAT is the propositional satisfiable problem restricted to the instance where each clause has exactly

k

distinct literals and every variable occurs at most

s

times. It is known that there exits a critical function

f

such that for

s

f

(

k

), all (

k

,

s

)–SAT instances are satisfiable, but (

k

,

f

(

k

)+1)–SAT is already NP–complete(

k

≥ 3). It’s open whether

f

is computable. In this paper, analogous to the randomized algorithm for finding a two-coloring for given uniform

k

–hypergraph, the similar one for outputting an assignment for a given formula is presented. Based on it and the probabilistic method, we prove, for every integer

k

≥ 2, each formula

F

in (

k

, *)–CNF with less than 0.58

$\times \sqrt{\frac{k}{{\rm ln} k}}2^k$

clauses is satisfiable. In addition, by the Lovász Local Lemma, we improve the previous result about the lower bound of

f

(

k

).

Ping Gong, Daoyun Xu

Cluster Computing and the Power of Edge Recognition

Although complexity theory already extensively studies path-cardinality-based restrictions on the power of nondeterminism, this paper is motivated by a more recent goal: To gain insight into how much of a restriction it is of nondeterminism to limit machines to have just one contiguous (with respect to some simple order) interval of accepting paths. In particular, we study the robustness—the invariance under definition changes—of the cluster class CL#P [8]. This class contains each #P function that is computed by a balanced Turing machine whose accepting paths always form a cluster with respect to some length-respecting total order with efficient adjacency checks. The definition of CL#P is heavily influenced by the defining paper’s focus on (global) orders. In contrast, we define a cluster class, CLU#P, to capture what seems to us a more natural model of cluster computing. We prove that the naturalness is costless: CL#P = CLU#P. Then we exploit the more natural, flexible features of CLU#P to prove new robustness results for CL#P and to expand what is known about the closure properties of CL#P.

The complexity of recognizing edges—of an ordered collection of computation paths or of a cluster of accepting computation paths—is central to this study. Most particularly, our proofs exploit the power of unique discovery of edges—the ability of nondeterministic functions to, in certain settings, discover on exactly one (in some cases, on at most one) computation path a critical piece of information regarding edges of orderings or clusters.

Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub

Quadratic Lower Bounds on Matrix Rigidity

The rigidity of a matrix

A

with respect to the rank bound

r

is the minimum number of entries of

A

that must be changed to reduce the rank of

A

to or below

r

. It is a major unsolved problem (Valiant, 1977) to construct “explicit” families of

n

×

n

matrices of rigidity

n

1 + δ

for

r

=

εn

, where

ε

and

δ

are positive constants. In fact, no superlinear lower bounds are known for explicit families of matrices for rank bound

r

=Ω(

n

).

In this paper we give the first optimal, Ω(

n

2

), lower bound on the rigidity of two “somewhat explicit” families of matrices with respect to the rank bound

r

=

cn

, where

c

is an absolute positive constant. The entries of these matrix families are (i) square roots of

n

2

distinct primes and (ii) primitive roots of unity of prime orders for the first

n

2

primes. Our proofs use an algebraic dimension concept introduced by Shoup and Smolensky (1997) and a generalization of that concept.

Satyanarayana V. Lokam

Non-reducible Descriptions for Conditional Kolmogorov Complexity

Let a program

p

on input

a

outputs

b

. We are looking for a shorter program

p

′ having the same property (

p

′(

a

)=

b

). In addition, we want

p

′ to be simple conditional to

p

(this means that the conditional Kolmogorov complexity

K

(

p

|

p

) is negligible). In the present paper, we prove that sometimes there is no such program

p

′, even in the case when the complexity of

p

is much bigger than

K

(

b

|

a

). We give three different constructions that use the game approach, probabilistic arguments and algebraic (combinatorial) arguments, respectively.

Andrej Muchnik, Alexander Shen, Nikolai Vereshchagin, Michael Vyugin

Generalized Counters and Reversal Complexity

We generalize the definition of a counter and counter reversal complexity and investigate the power of generalized deterministic counter automata in terms of language recognition.

M. V. Panduranga Rao

Multisource Algorithmic Information Theory

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.

Alexander Shen

Block Sensitivity of Weakly Symmetric Functions

Block sensitivity, which was introduced by Nisan [5], is one of the most useful measures of boolean functions. In this paper we investigate the block sensitivity of weakly symmetric functions (functions invariant under some transitive group action). We prove a Ω(

N

1/3

) lower bound for the block sensitivity of weakly symmetric functions. We also construct a weakly symmetric function which has block sensitivity Õ(

N

3/7

).

Xiaoming Sun

Optimization Problems in the Polynomial-Time Hierarchy

This talk surveys work on classifying the complexity and approximability of problems residing in the Polynomial-Time Hierarchy, above the first level. Along the way, we highlight some prominent natural problems that are believed – but not yet known – to be

$\Sigma^p_2$

-complete. We describe how strong inapproximability results for certain

$\Sigma^p_2$

optimization problems can be obtained using

dispersers

to build error-correcting codes. Finally we adapt a learning algorithm to produce approximation algorithms for these problems.

Christopher Umans

#3-Regular Bipartite Planar Vertex Cover is #P-Complete

We generalize the polynomial interpolation method by giving a sufficient condition, which guarantees that the coefficients of a polynomial are uniquely determined by its values on a recurrence sequence. Using this method, we show that #3-Regular Bipartite Planar Vertex Cover is #P-complete. The result is unexpected, since the same question for 2-regular graph is in FP.

Mingji Xia, Wenbo Zhao

Group Theory Based Synthesis of Binary Reversible Circuits

This paper presents an important result addressing a fundamental question in synthesizing binary reversible logic circuits for quantum computation. We show that any even-reversible-circuit of

n

(

n

>3) qubits can be realized using NOT gate and Toffoli gate (‘2’-Controlled-Not gate), where the numbers of Toffoli and NOT gates required in the realization are bounded by

$(n + \lfloor \frac{n}{3} \rfloor)(3 \times 2^{2n-3}-2^{n+2})$

and

$4n(n + \lfloor \frac{n}{3} \rfloor)2^n$

, respectively. A provable constructive synthesis algorithm is derived. The time complexity of the algorithm is

$\frac{10}{3}n^2 \cdot 2^n$

. Our algorithm is exponentially lower than breadth-first search based synthesis algorithms with respect to space and time complexities.

Guowu Yang, Xiaoyu Song, William N. N. Hung, Fei Xie, Marek A. Perkowski

On Some Complexity Issues of NC Analytic Functions

This paper studies the complexity of derivatives and integration of

NC

real functions (not necessarily analytic) and

NC

analytic functions. We show that for

NC

real functions, derivatives and integration are infeasible, but analyticity helps to reduce the complexity. For example, the integration of a log-space computable real function

f

is as hard as #

P

, but if

f

is an analytic function, then the integration is log-space computable. As an application, we study the problem of finding all zeros of an

NC

analytic function inside a Jordan curve and show that, under a uniformity condition on the function values of the Jordan curve, the zeros are all

NC

computable.

Fuxiang Yu

Learning Theory

Learning Juntas in the Presence of Noise

The combination of two major challenges in algorithmic learning is investigated: dealing with huge amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that only depend on a small fraction of their variables—so-called

juntas

—can be learned efficiently from uniformly distributed examples that are corrupted by random attribute and classification noise. We present solutions to cope with the manifold problems that inhibit a straightforward generalization of the noise-free case. Additionally, we extend our methods to non-uniformly distributed examples and derive new results for monotone juntas in this setting. We assume that the attribute noise is generated by a product distribution. Otherwise fault-tolerant learning is in general impossible which follows from the construction of a noise distribution

P

and a concept class

$\mathcal{C}$

such that it is impossible to learn

$\mathcal{C}$

under

P

-noise.

Jan Arpe, Rüdiger Reischuk

Grey Reinforcement Learning for Incomplete Information Processing

New representation and computation mechanisms are key approaches for learning problems with incomplete information or in large probabilistic environments. In this paper, traditional reinforcement learning (RL) methods are combined with grey theory and a novel grey reinforcement learning (GRL) framework is proposed to solve complex problems with incomplete information. Typical example of mobile robot navigation is given out to evaluate the performance and practicability of GRL. Related issues are also briefly discussed.

Chunlin Chen, Daoyi Dong, Zonghai Chen

On the Foundations of Universal Sequence Prediction

Solomonoff completed the Bayesian framework by providing a rigorous, unique, formal, and universal choice for the model class and the prior. We discuss in breadth how and in which sense universal (non-i.i.d.) sequence prediction solves various (philosophical) problems of traditional Bayesian sequence prediction. We show that Solomonoff’s model possesses many desirable properties: Fast convergence and strong bounds, and in contrast to most classical continuous prior densities has no zero p(oste)rior problem, i.e. can confirm universal hypotheses, is reparametrization and regrouping invariant, and avoids the old-evidence and updating problem. It even performs well (actually better) in non-computable environments.

Marcus Hutter

Some Recent Results in U-Shaped Learning

U-shaped learning deals with a learner first having the correct hypothesis, then changing it to an incorrect hypothesis and then relearning the correct hypothesis. This phenomenon has been observed by psychologists in various studies of children development. In this survey talk, we will discuss some recent results regarding U-shaped learning and related criteria.

Sanjay Jain, Frank Stephan

Learning Overcomplete Representations with a Generalized Gaussian Prior

Overcomplete representations have been advocated because they allow a basis to better approximate the underlying statistical density of the data which can lead to representations that better capture the underlying structure in the data. The prior distributions for the coefficients of these models, however, are assumed to be fixed, not adaptive to the data, and hereby inaccurate. Here we describe a method for learning overcomplete representations with a generalized Gaussian prior, which can fit a broader range of statistical distributions by varying the value of the steepness parameter

β

. Using this distribution in overcomplete representations, empirical results were obtained for the blind source separation of more sources than mixtures, which show that the accuracy of the density estimation is improved.

Ling-Zhi Liao, Si-Wei Luo, Mei Tian, Lian-Wei Zhao

On PAC Learning Algorithms for Rich Boolean Function Classes

We survey the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model.

Rocco A. Servedio

On-Line Regression Competitive with Reproducing Kernel Hilbert Spaces

We consider the problem of on-line prediction of real-valued labels, assumed bounded in absolute value by a known constant, of new objects from known labeled objects. The prediction algorithm’s performance is measured by the squared deviation of the predictions from the actual labels. No stochastic assumptions are made about the way the labels and objects are generated. Instead, we are given a benchmark class of prediction rules some of which are hoped to produce good predictions. We show that for a wide range of infinite-dimensional benchmark classes one can construct a prediction algorithm whose cumulative loss over the first

N

examples does not exceed the cumulative loss of any prediction rule in the class plus

$O(\sqrt{N})$

; the main differences from the known results are that we do not impose any upper bound on the norm of the considered prediction rules and that we achieve an optimal leading term in the excess loss of our algorithm. If the benchmark class is “universal” (dense in the class of continuous functions on each compact set), this provides an on-line non-stochastic analogue for universally consistent prediction in non-parametric statistics. We use two proof techniques: one is based on the Aggregating Algorithm and the other on the recently developed method of defensive forecasting.

Vladimir Vovk

Inductive Inference and Language Learning

The present paper is a short reflection concerning the role which inductive inference played and can play in language learning. We shortly recall some major insights obtained and outline some new directions based on own work and results recently presented in the literature.

Thomas Zeugmann

Time Series Predictions Using Multi-scale Support Vector Regressions

Support vector regressions (SVR) have been applied to time series prediction recently and perform better than RBF networks. However, only one kernel scale is used in SVR. We implemented a multi scale support vector regression (MS-SVR), which has several different kernel scales, and tested it on two time series benchmarks: Mackey-Glass time series and Laser generated data. In both cases, MS-SVR improves the performance of SVR greatly: fewer support vectors and less prediction error.

Danian Zheng, Jiaxin Wang, Yannan Zhao

Bioinformatics

Identification and Comparison of Motifs in Brain-Specific and Muscle-Specific Alternative Splicing

Regulatory elements are important to the regulation of tissue-specific alternative splicing. Here we report a genome-wide analysis of motifs involved in human brain-specific or muscle-specific alternative splicing. Comparing relative abundance of alternative splice forms based on Bayesian statistics, we identified many tissue-specific exon skipping events in normal or tumor samples from brain or muscle. Motifs possibly function in these events were subsequently distinguished using EM algorithm. Analyses of these motifs suggest that some exons are tissue-specifically skipped through a loop out mechanism and motif locations are sometimes important. Furthermore, comparison of motifs in normal and tumor samples suggests that there may exist different tumorigenesis mechanisms between brain and muscle. These results provide some insights into the regulation mechanism of alternative splicing and may throw light on cancer therapy.

Jianning Bi, Yanda Li

On Probe Permutation Graphs

Given a class of graphs

$\mathcal{G}$

, a graph

G

is a

probe graph of

$\mathcal{G}$

if its vertices can be partitioned into two sets ℙ, the

probes

, and ℕ, the

nonprobes

, where ℕ is an independent set, such that

G

can be embedded into a graph of

$\mathcal{G}$

by adding edges between certain vertices of ℕ. If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a

partitioned probe graph of

$\mathcal{G}$

. In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity

O

(

n

2

) where

n

is the number of vertices in the input graph. We show that there are at most

O

(

n

4

) minimal separators for a probe permutation graph. As a consequence, there exist polynomial-time algorithms solving

treewidth

and

minimum fill-in

problems for probe permutation graphs.

David B. Chandler, Maw-Shang Chang, Antonius J. J. Kloks, Jiping Liu, Sheng-Lung Peng

Automatic Classification of Protein Structures Based on Convex Hull Representation by Integrated Neural Network

The large scale deposited data and existing manual classification scheme make it possible to study the automatic classification of protein structures in machine learning framework. In this paper the classification system is constructed by an integrated feedforward neural network through incorporating the expert judgements and existing classification schemes into the learning procedure. Since different aspects of a protein structure may be relevant to various biological problems, the protein structure is represented by the convex hull of its backbone and geometric features are extracted. The training and prediction tests for different training sets in the class level of CATH indicate that the new automatic classification scheme is effective and efficient. Also the neural network model outperforms hidden markov model and support vector machine in the comparison experiment.

Yong Wang, Ling-Yun Wu, Xiang-Sun Zhang, Luonan Chen

Protein Structure Comparison Based on a Measure of Information Discrepancy

Protein structure comparison is an important tool to explore and understand the different aspects of protein 3D structures. In this paper, a novel representation of protein structure (complete information set of

C

α

C

α

distances, CISD) is formulated at first. Then an FDOD score scheme is developed to measure the similarity between two representations. Numerical experiments of the new method are conducted in four different protein datasets and clustering analyses are given to verify the effectiveness of this new similarity measure. Furthermore, preliminary results of detecting homologous protein pairs of an existing non-redundant subset of CATH v2.5.1 based on the new similarity are given as a pilot study. All the results show that this new approach to measure the similarities between protein structures is simple to implement, computationally efficient and fast.

Zi-Kai Wu, Yong Wang, En-Min Feng, Jin-Cheng Zhao

Succinct Text Indexes on Large Alphabet

In this paper, we first consider some properties of strings who have the same suffix array. Next, we design a data structure to support

rank

and

select

operations on an alphabet Σ using

n

log|Σ| + (

n

log

|Σ|) bits in

O

(log|Σ|) time for a text of length

n

. It also supports an extended

rank

, namely

rank

 ≤ 

, such that

rank

$^{\rm \leq}_{\alpha}$

(

T

,

i

) returns the number of letters which are smaller than

α

in string

T

, plus the number of

α

s up to position

i

. Also, it runs in

O

(log|Σ|) time. By this structure, we implement the DAWG succinctly. The main structure only takes

n

log|Σ| +

o

(

nlog

|Σ|) bits and supports basic operations of DAWG efficiently.

Meng Zhang, Jijun Tang, Dong Guo, Liang Hu, Qiang Li

Security

Identity-Based Threshold Proxy Signature Scheme with Known Signers

Threshold proxy signature is a variant of the proxy signature scheme in which only some subgroup of proxy signers with efficient size can sign messages on behalf of the original signer. Some threshold proxy signature schemes have been proposed up to data. But nearly all of them are under the certificate-based (CA-based) public key systems. In this paper, we put forward an identity-based (ID-based) threshold proxy signature scheme with known signers from bilinear pairings for the first time. Most of our constructions would be simpler but still with high security due to the properties of bilinear map built from Weil pairing or Tate pairing.

Haiyong Bao, Zhenfu Cao, Shengbao Wang

Secure Computations in a Minimal Model Using Multiple-Valued ESOP Expressions

This paper deals with secure computations in a minimal model, and gives a protocol which securely computes every function by means of the techniques of exclusive-or sum-of-products (ESOP) expressions. The communication complexity of our protocol is proportional to the size of an obtained multiple-valued-input ESOP expression. Since the historical research on minimizing ESOP expressions is now still active, our protocol will turn to an efficient one as this research progresses. Thus, this paper gives an application of ESOP expressions to designing cryptographic protocols, and we hope that it would motivate further research on minimizing ESOP expressions.

Takaaki Mizuki, Taro Otagiri, Hideaki Sone

Formal Method

Towards Practical Computable Functions on Context-Free Languages

Many structures used in computer science and software can be represented by context-free languages. This paper discusses computable functions on such languages, which give a useful model for studies of computability and algorithms involving complex data structures. This paper further tackles some practical issues for using the functions. Some practical schemes of the functions are presented. A subclass of functions is provided, which can be implemented efficiently.

Haiming Chen, Yunmei Dong

The Extended Probabilistic Powerdomain Monad over Stably Compact Spaces

For the semantics of probabilistic features in programming mainly two approaches are used for building models. One is the Giry monad of Borel probability measures over metric spaces, and the other is Jones’ probabilistic powerdomain monad [6] over dcpos (directed complete partial orders). This paper places itself in the second domain theoretical tradition. The probabilistic powerdomain monad is well understood over continuous domains. In this case the algebras of the monad can be described by an equational theory [6, 9,5]. It is the aim of this work to obtain similar results for the (extended) probabilistic powerdomain monad over stably compact spaces. We mainly want to determine the algebras of this powerdomain monad and the algebra homomorphisms.

Ben Cohen, Martin Escardo, Klaus Keimel

Analysis of Properties of Petri Synthesis Net

Petri net synthesis can avoid the state exploration problem, which is of exponential complexity, by guaranteeing the correctness in the Petri net while incrementally expanding the net. The conventional Petri net synthesis approaches, in general, suffer the drawback of only being able to synthesize a few classes of nets, such as state machines, marked graphs or asymmetric choice(AC) nets. However, the synthesis technique of Petri nets shared PP-type subnets can synthesize Petri nets beyond AC nets. One major advantage of the synthesis technique is that the resultant Petri net is guaranteed to be live, bounded and reversible. Most current synthesis techniques cannot handle systems with shared subsystems. To solve resource-sharing problem, Jiao L. presented the conditions for an AC net satisfying siphon-trap-property (ST-property) to be live, bounded and reversible[3]. The major motivation of this work is to generalize the results in [3] and to extend the resource-sharing technique to subsystem-sharing technique on AC nets or Petri nets beyond AC nets.

Chuanliang Xia

A Tree Construction of the Preferable Answer Sets for Prioritized Basic Disjunctive Logic Programs

One of the most important works in the investigation of logic programming is to define the semantics of the logic programs and to find the preferable answer set of them. There are so far three methods can be used to establish the semantics of the logic programs, i.e., the means of model, fixpoint and proof theory. According to the form of the rules contained in a logic program, different logic program classes can be defined. Although well-defined semantics exist for some restricted classes of programs like Horn and stratified Programs, the declarative semantics of the more general program classes are still the subject of research. In this paper, the properties of the basic disjunctive logic programming are studied, and the notion of double prioritization is introduced, that is, the prioritization on both literals and clauses, by which the most preferable answer set of a basic disjunctive logic program is defined. In order to obtain the most preferable answer set of a basic disjunctive logic program explicitly, a recursion-theoretic construction called tree method is given.

Zaiyue Zhang, Yuefei Sui, Cungen Cao

Object-Oriented Specification Composition and Refinement Via Category Theoretic Computations

Most of the existing formal object-oriented methods use classes or objects as the basic unit of design, and therefore lack a precise semantics for specifying high-granularity components. The paper presents a framework of categorical models that focus concern on the interactive relationships between objects, and that explicitly support specification composition and refinement at different levels of abstraction and granularity in object-oriented design. A case study of implementing templated design patterns demonstrates the ability of category theoretic computations to mechanize software development.

Yujun Zheng, Jinyun Xue, Weibo Liu

Improved SAT Based Bounded Model Checking

The usefulness of Bounded Model Checking(BMC) based on propositional satisfiability methods has recently proven its efficacy for bug hunting. The basic idea is to search for a counterexample in executions whose length is bounded by some integer

k

. In fact, for some properties some bounded paths are equivalent. In the original Bounded Model Checking equivalent bounded paths may be searched repeatedly. Therefore some searches are redundant. In this paper with respect to some properties we exploit new encoding for Bounded Model Checking such that we can avoid searching for redundant bounded paths.

Conghua Zhou, Decheng Ding

Models of Computation

Encodings and Arithmetic Operations in Membrane Computing

Membrane systems represent a new abstract model inspired by cell biology. This new model works with multisets. In this paper we deal with various number encodings over multisets. We present the natural encoding and a most compact encoding, and study their properties using elements of combinatorics over multisets. We construct the membrane systems implementing the arithmetic operations using these encodings. For each encoding and operation we present its complexity. With respect to their complexity, we compare the encodings and we remark a transfer from the usual encoding lengths and time complexities of order

log

b

n

to lengths and complexities of order

$^b\sqrt{n}$

.

Cosmin Bonchiş, Gabriel Ciobanu, Cornel Izbaşa

The General Purpose Analog Computer and Computable Analysis are Two Equivalent Paradigms of Analog Computation

In this paper we revisit one of the first models of analog computation, Shannon’s General Purpose Analog Computer (GPAC). The GPAC has often been argued to be weaker than computable analysis. As main contribution, we show that if we change the notion of GPAC-computability in a natural way, we compute exactly all real computable functions (in the sense of computable analysis). Moreover, since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions can be defined by such models.

Olivier Bournez, Manuel L. Campagnolo, Daniel S. Graça, Emmanuel Hainry

Forecasting Black Holes in Abstract Geometrical Computation is Highly Unpredictable

In

Abstract geometrical computation for black hole computation (MCU ’04, LNCS 3354)

, the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability: any recursively enumerable set can be decided in finite time. To achieve this, a Zeno-like construction is used to provide an accumulation similar in effect to the black holes of the black hole model.

We prove here that forecasting an accumulation is Σ

$_{\rm 2}^{\rm 0}$

-complete (in the arithmetical hierarchy) even if only energy conserving signal machines are addressed (as in the cited paper). The Σ

$_{\rm 2}^{\rm 0}$

-hardness is achieved by reducing the problem of deciding whether a recursive function (represented by a 2-counter automaton) is strictly partial. The Σ

$_{\rm 2}^{\rm 0}$

-membership is proved with a logical characterization.

Jérôme Durand-Lose

The Trade-Off Theorem and Fragments of Gödel’s T

In [3, 4] we study the functionals, functions and predicates of the system

T

− −

. Roughly speaking,

T

− −

is a version of Gödel’s

T

(see, for instance [1]) where the successor function cannot be used to define functionals, and a functional

F

is definable in

T

− −

iff

F

is definable in Gödel’s

T

by a term

t

where no succesors occur in

t

(the numerical constant 1 might occur in

t

).

Lars Kristiansen, Paul J. Voda

On Non-binary Quantum BCH Codes

Two sufficient and necessary conditions for the self orthogonality of classical non-primitive BCH codes over

$\mathbb{F}_q$

and

$\mathbb{F}_{q^2}$

are given, respectively. And series of non-binary quantum BCH codes are obtained by using these two conditions and some construction methods.

Zhi Ma, Xin Lu, Keqin Feng, Dengguo Feng

Maximal Models of Assertion Graph in GSTE

Generalized symbolic trajectory evaluation (GSTE) is an extension of symbolic trajectory evaluation (STE). In GSTE, assertion graphs are used to specify properties in a special form of regular automata with antecedent and consequent pairs. This paper presents a new model characterization, called maximal models, for an assertion graph with important properties. Besides their own theoretical significance, maximal models are used to show the implication of two assertion graphs in GSTE. We show that, contrary to the general belief, an assertion graph may have more than one maximal model. We present a provable algorithm to find all maximal models of a linear assertion graph. We devise an algorithm for finding a maximal model for an arbitrary assertion graph.

Guowu Yang, Jin Yang, Xiaoyu Song, Fei Xie

Computatability

Immunity Properties and the n-C.E. Hierarchy

We extend Post’s programme to finite levels of the Ershov hierarchy of Δ

2

sets, and characterise, in the spirit of Post [9], the degrees of the immune and hyperimmune d.c.e. sets. We also show that no properly d.c.e. set can be hh-immune, and indicate how to generalise these results to

n

-c.e. sets,

n

> 2.

Bahareh Afshari, George Barmpalias, S. Barry Cooper

On Rogers Semilattices

Rogers semilattices of computable numberings for the families in the hierarchy of Ershov are compared with those for the families in the arithmetical hierarchy.

Serikzhan Badaev

Invertible Classes

This paper considers when one can invert general recursive operators which map a class of functions

$\mathcal{F}$

to

$\mathcal{F}$

. In this regard, we study four different notions of inversion. We additionally consider enumeration of operators which

cover

all general recursive operators which map

$\mathcal{F}$

to

$\mathcal{F}$

in the sense that for every general recursive operator Ψ mapping

$\mathcal{F}$

to

$\mathcal{F}$

, there is a general recursive operator in the enumerated sequence which behaves the same way as Ψ on

$\mathcal{F}$

. Three different possible types of enumeration are studied.

Sanjay Jain, Jochen Nessel, Frank Stephan

Universal Cupping Degrees

Cupping nonzero computably enumerable (c.e. for short) degrees to

0

′ in various structures has been one of the most important topics in the development of classical computability theory. An incomplete c.e. degree

a

is

cuppable

if there is an incomplete c.e. degree

b

such that

a

b

=

0

′, and

noncuppable

if there is no such degree

b

. Sacks splitting theorem shows the existence of cuppable degrees. However, Yates(unpublished) and Cooper [3] proved that there are noncomputable noncuppable degrees. After that, Harrington and Shelah were able to employ the cupping/noncupping properties to show that the theory of the c.e. degrees under relation ≤ is undecidable. Cuppable and noncuppable degrees were further studied later. See Harrington [7], Miller [10], Fejer and Soare [6], Ambos-Spies, Lachlan and Soare [1], etc..

Angsheng Li, Yan Song, Guohua Wu

On the Quotient Structure of Computably Enumerable Degrees Modulo the Noncuppable Ideal

We show that minimal pairs exist in the quotient structure of

$\mathcal{R}$

modulo the ideal of noncuppable degrees.

Angsheng Li, Guohua Wu, Yue Yang

Enumeration Degrees of the Bounded Total Sets

Let

f

:

ω

ω

be a total function and f̂= {〈

x

,

y

〉:

x

 ∈ 

ω

&

y

 ≤ 

f

(

x

)}. A set

A

 ⊆ 

ω

is called

bounded total

if

A

= f̂ for some total function

f

. In this paper we study enumeration degrees of the bounded total sets.

Boris Solon, Sergey Rozhkov

A Generic Set That Does Not Bound a Minimal Pair

The structure of the semi lattice of enumeration degrees has been investigated from many aspects. One aspect is the bounding and nonbounding properties of generic degrees. Copestake proved that every 2-generic enumeration degree bounds a minimal pair and conjectured that there exists a 1-generic set that does not bound a minimal pair. In this paper we verify this longstanding conjecture by constructing such a set using an infinite injury priority argument. The construction is explained in detail. It makes use of a priority tree of strategies.

Mariya Ivanova Soskova

Lowness for Weakly 1-generic and Kurtz-Random

It is shown that a set is low for weakly 1-generic iff it has neither dnr nor hyperimmune Turing degree. As this notion is more general than being recursively traceable, this answers negatively a recent question on the characterization of these sets. Furthermore, it is shown that every set which is low for weakly 1-generic is also low for Kurtz-random.

Frank Stephan, Liang Yu

On Differences Among Elementary Theories of Finite Levels of Ershov Hierarchies

We study the differences among elementary theories of finite levels of Ershov hierarchies. We also give a brief survey on the current state of this area. Some questions are raised.

Yue Yang, Liang Yu

Computable Mathematics

On Mass Problems of Presentability

We consider the notion of mass problem of presentability for countable structures, and study the relationship between Medvedev and Muchnik reducibilities on such problems and possible ways of syntactically characterizing these reducibilities. Also, we consider the notions of strong and weak presentability dimension and characterize classes of structures with presentability dimensions 1.

Alexey Stukachev

Beyond the First Main Theorem – When Is the Solution of a Linear Cauchy Problem Computable?

We study computabilty of the abstract linear Cauchy problem

du

(

t

)/

dt

 = 

Au

(

t

),

t

 > 0,

u

(0) = 

x

 ∈ 

X

where

A

is a linear operator on a Banach space

X

. We give necessary and sufficient conditions for

A

such that the operator

K

:

x

u

is computable. We consider continuous operators and more generally closed operators

A

. For studying computability we use the representation approach to Computable Analysis (TTE) [7, 1] which is consistent with the model used in [6].

Klaus Weihrauch, Ning Zhong

Backmatter

Weitere Informationen