title: Average Coset Weight Distribution of Combined LDPC Matrix Ensemble

abstract: In this paper, the average coset weight distribution (ACWD) of structured ensembles of LDPC (Low-density Parity-Check) matrix, which is called combined ensembles, is discussed. A combined ensemble is composed of a set of simpler ensembles such as a regular bipartite ensemble. Two classes of combined ensembles have prime importance; a stacked ensemble and a concatenated ensemble, which consists of set of stacked matrices and concatenated matrices, respectively. The ACWD formulas of these ensembles is shown in this paper. Such formulas are key tools to evaluate the ACWD of a complex combined ensemble. From the ACWD of an ensemble, we can obtain some detailed properties of a code (e.g., weight of coset leaders) which is not available from an average weight distribution. Moreover, it is shown that the analysis based on the ACWD is indispensable to evaluate the average weight distribution of some classes of combined ensembles.


title: Improving Spam Detection Based on Structural Similarity

abstract: We propose a new detection algorithm that uses structural relationships between senders and recipients of email as the basis for the identification of spam messages. Users and receivers are represented as vectors in their reciprocal spaces. A measure of similarity between vectors is constructed and used to group users into clusters. Knowledge of their classification as past senders/receivers of spam or legitimate mail, comming from an auxiliary detection algorithm, is then used to label these clusters probabilistically. This knowledge comes from an auxiliary algorithm. The measure of similarity between the sender and receiver sets of a new message to the center vector of clusters is then used to asses the possibility of that message being legitimate or spam. We show that the proposed algorithm is able to correct part of the false positives (legitimate messages classified as spam) using a testbed of one week smtp log.


title: Pseudocodewords of Tanner graphs

abstract: This papers presents a detailed analysis of pseudocodewords of Tanner graphs. Pseudocodewords arising on the iterative decoder's computation tree are distinguished from pseudocodewords arising on finite degree lifts. Lower bounds on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN channel. Some structural properties of pseudocodewords are examined, and pseudocodewords and graph properties that are potentially problematic with min-sum iterative decoding are identified. An upper bound on the minimum degree lift needed to realize a particular irreducible lift-realizable pseudocodeword is given in terms of its maximal component, and it is shown that all irreducible lift-realizable pseudocodewords have components upper bounded by a finite value $t$ that is dependent on the graph structure. Examples and different Tanner graph representations of individual codes are examined and the resulting pseudocodeword distributions and iterative decoding performances are analyzed. The results obtained provide some insights in relating the structure of the Tanner graph to the pseudocodeword distribution and suggest ways of designing Tanner graphs with good minimum pseudocodeword weight.


title: Network Information Flow with Correlated Sources

abstract: In this paper, we consider a network communications problem in which multiple correlated sources must be delivered to a single data collector node, over a network of noisy independent point-to-point channels. We prove that perfect reconstruction of all the sources at the sink is possible if and only if, for all partitions of the network nodes into two subsets S and S^c such that the sink is always in S^c, we have that H(U_S|U_{S^c}) < \sum_{i\in S,j\in S^c} C_{ij}. Our main finding is that in this setup a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This ``information as flow'' view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.


title: Design of Block Transceivers with Decision Feedback Detection

abstract: This paper presents a method for jointly designing the transmitter-receiver pair in a block-by-block communication system that employs (intra-block) decision feedback detection. We provide closed-form expressions for transmitter-receiver pairs that simultaneously minimize the arithmetic mean squared error (MSE) at the decision point (assuming perfect feedback), the geometric MSE, and the bit error rate of a uniformly bit-loaded system at moderate-to-high signal-to-noise ratios. Separate expressions apply for the ``zero-forcing'' and ``minimum MSE'' (MMSE) decision feedback structures. In the MMSE case, the proposed design also maximizes the Gaussian mutual information and suggests that one can approach the capacity of the block transmission system using (independent instances of) the same (Gaussian) code for each element of the block. Our simulation studies indicate that the proposed transceivers perform significantly better than standard transceivers, and that they retain their performance advantages in the presence of error propagation.


title: Shortened Array Codes of Large Girth

abstract: One approach to designing structured low-density parity-check (LDPC) codes with large girth is to shorten codes with small girth in such a manner that the deleted columns of the parity-check matrix contain all the variables involved in short cycles. This approach is especially effective if the parity-check matrix of a code is a matrix composed of blocks of circulant permutation matrices, as is the case for the class of codes known as array codes. We show how to shorten array codes by deleting certain columns of their parity-check matrices so as to increase their girth. The shortening approach is based on the observation that for array codes, and in fact for a slightly more general class of LDPC codes, the cycles in the corresponding Tanner graph are governed by certain homogeneous linear equations with integer coefficients. Consequently, we can selectively eliminate cycles from an array code by only retaining those columns from the parity-check matrix of the original code that are indexed by integer sequences that do not contain solutions to the equations governing those cycles. We provide Ramsey-theoretic estimates for the maximum number of columns that can be retained from the original parity-check matrix with the property that the sequence of their indices avoid solutions to various types of cycle-governing equations. This translates to estimates of the rate penalty incurred in shortening a code to eliminate cycles. Simulation results show that for the codes considered, shortening them to increase the girth can lead to significant gains in signal-to-noise ratio in the case of communication over an additive white Gaussian noise channel.


title: A new SISO algorithm with application to turbo equalization

abstract: In this paper we propose a new soft-input soft-output equalization algorithm, offering very good performance/complexity tradeoffs. It follows the structure of the BCJR algorithm, but dynamically constructs a simplified trellis during the forward recursion. In each trellis section, only the M states with the strongest forward metric are preserved, similar to the M-BCJR algorithm. Unlike the M-BCJR, however, the remaining states are not deleted, but rather merged into the surviving states. The new algorithm compares favorably with the reduced-state BCJR algorithm, offering better performance and more flexibility, particularly for systems with higher order modulations.


title: A Rule-Based Logic for Quantum Information

abstract: In the present article, we explore a new approach for the study of orthomodular lattices, where we replace the problematic conjunction by a binary operator, called the Sasaki projection. We present a characterization of orthomodular lattices based on the use of an algebraic version of the Sasaki projection operator (together with orthocomplementation) rather than on the conjunction. We then define of a new logic, which we call Sasaki Orthologic, which is closely related to quantum logic, and provide a rule-based definition of this logic.


title: Efficient Authenticated Encryption Schemes with Public Verifiability

abstract: An authenticated encryption scheme allows messages to be encrypted and authenticated simultaneously. In 2003, Ma and Chen proposed such a scheme with public verifiability. That is, in their scheme the receiver can efficiently prove to a third party that a message is indeed originated from a specific sender. In this paper, we first identify two security weaknesses in the Ma-Chen authenticated encryption scheme. Then, based on the Schnorr signature, we proposed an efficient and secure improved scheme such that all the desired security requirements are satisfied.


title: The Viterbi Algorithm: A Personal History

abstract: The story of the Viterbi algorithm (VA) is told from a personal perspective. Applications both within and beyond communications are discussed. In brief summary, the VA has proved to be an extremely important algorithm in a surprising variety of fields.


title: Near Perfect Decoding of LDPC Codes

abstract: Cooperative optimization is a new way for finding global optima of complicated functions of many variables. It has some important properties not possessed by any conventional optimization methods. It has been successfully applied in solving many large scale optimization problems in image processing, computer vision, and computational chemistry. This paper shows the application of this optimization principle in decoding LDPC codes, which is another hard combinatorial optimization problem. In our experiments, it significantly out-performed the sum-product algorithm, the best known method for decoding LDPC codes. Compared to the sum-product algorithm, our algorithm reduced the error rate further by three fold, improved the speed by six times, and lowered error floors dramatically in the decoding.


title: A Matter of Opinion: Sentiment Analysis and Business Intelligence (position paper)

abstract: A general-audience introduction to the area of "sentiment analysis", the computational treatment of subjective, opinion-oriented language (an example application is determining whether a review is "thumbs up" or "thumbs down"). Some challenges, applications to business-intelligence tasks, and potential future directions are described.


title: Correlation Clustering with a Fixed Number of Clusters

abstract: We continue the investigation of problems concerning correlation clustering or clustering with qualitative information, which is a clustering formulation that has been studied recently. The basic setup here is that we are given as input a complete graph on n nodes (which correspond to nodes to be clustered) whose edges are labeled + (for similar pairs of items) and - (for dissimilar pairs of items). Thus we have only as input qualitative information on similarity and no quantitative distance measure between items. The quality of a clustering is measured in terms of its number of agreements, which is simply the number of edges it correctly classifies, that is the sum of number of - edges whose endpoints it places in different clusters plus the number of + edges both of whose endpoints it places within the same cluster. In this paper, we study the problem of finding clusterings that maximize the number of agreements, and the complementary minimization version where we seek clusterings that minimize the number of disagreements. We focus on the situation when the number of clusters is stipulated to be a small constant k. Our main result is that for every k, there is a polynomial time approximation scheme for both maximizing agreements and minimizing disagreements. (The problems are NP-hard for every k >= 2.) The main technical work is for the minimization version, as the PTAS for maximizing agreements follows along the lines of the property tester for Max k-CUT. In contrast, when the number of clusters is not specified, the problem of minimizing disagreements was shown to be APX-hard, even though the maximization version admits a PTAS.


title: Constraint-Based Qualitative Simulation

abstract: We consider qualitative simulation involving a finite set of qualitative relations in presence of complete knowledge about their interrelationship. We show how it can be naturally captured by means of constraints expressed in temporal logic and constraint satisfaction problems. The constraints relate at each stage the 'past' of a simulation with its 'future'. The benefit of this approach is that it readily leads to an implementation based on constraint technology that can be used to generate simulations and to answer queries about them.


title: Incorporating LINQ, State Diagrams Templating and Package Extension Into Java

abstract: This submission has been withdrawn at the request of the author.


title: Searching Monotone Multi-dimensional Arrays

abstract: In this paper we investigate the problem of searching monotone multi-dimensional arrays. We generalize Linial and Saks' search algorithm \cite{LS1} for monotone 3-dimensional arrays to $d$-dimensions with $d\geq 4$. Our new search algorithm is asymptotically optimal for $d=4$.


title: Linear Datalog and Bounded Path Duality of Relational Structures

abstract: In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs. We prove that, in the context of Constraint Satisfaction Problems, all these concepts correspond to different mathematical embodiments of a unique robust notion that we call bounded path duality. We also study the computational complexity implications of the notion of bounded path duality. We show that every constraint satisfaction problem $\csp(\best)$ with bounded path duality is solvable in NL and that this notion explains in a uniform way all families of CSPs known to be in NL. Finally, we use the results developed in the paper to identify new problems in NL.


title: On Extrinsic Information of Good Codes Operating Over Discrete Memoryless Channels

abstract: We show that the Extrinsic Information about the coded bits of any good (capacity achieving) code operating over a wide class of discrete memoryless channels (DMC) is zero when channel capacity is below the code rate and positive constant otherwise, that is, the Extrinsic Information Transfer (EXIT) chart is a step function of channel quality, for any capacity achieving code. It follows that, for a common class of iterative receivers where the error correcting decoder must operate at first iteration at rate above capacity (such as in turbo equalization, turbo channel estimation, parallel and serial concatenated coding and the like), classical good codes which achieve capacity over the DMC are not effective and should be replaced by different new ones. Another meaning of the results is that a good code operating at rate above channel capacity falls apart into its individual transmitted symbols in the sense that all the information about a coded transmitted symbol is contained in the corresponding received symbol and no information about it can be inferred from the other received symbols. The binary input additive white Gaussian noise channel is treated in part 1 of this report. Part 2 extends the results to the symmetric binary channel and to the binary erasure channel and provides an heuristic extension to wider class of channel models.


title: Fast Distributed Algorithms for Computing Separable Functions

abstract: The problem of computing functions of values at the nodes in a network in a totally distributed manner, where nodes do not have unique identities and make decisions based only on local information, has applications in sensor, peer-to-peer, and ad-hoc networks. The task of computing separable functions, which can be written as linear combinations of functions of individual variables, is studied in this context. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend in general to the computation of the actual values of separable functions. The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions. The running time of the algorithm is shown to depend on the running time of a minimum computation algorithm used as a subroutine. Using a randomized gossip mechanism for minimum computation as the subroutine yields a complete totally distributed algorithm for computing separable functions. For a class of graphs with small spectral gap, such as grid graphs, the time used by the algorithm to compute averages is of a smaller order than the time required by a known iterative averaging scheme.


title: Sufficient conditions for convergence of the Sum-Product Algorithm

abstract: We derive novel conditions that guarantee convergence of the Sum-Product algorithm (also known as Loopy Belief Propagation or simply Belief Propagation) to a unique fixed point, irrespective of the initial messages. The computational complexity of the conditions is polynomial in the number of variables. In contrast with previously existing conditions, our results are directly applicable to arbitrary factor graphs (with discrete variables) and are shown to be valid also in the case of factors containing zeros, under some additional conditions. We compare our bounds with existing ones, numerically and, if possible, analytically. For binary variables with pairwise interactions, we derive sufficient conditions that take into account local evidence (i.e., single variable factors) and the type of pair interactions (attractive or repulsive). It is shown empirically that this bound outperforms existing bounds.


title: Convexity Analysis of Snake Models Based on Hamiltonian Formulation

abstract: This paper presents a convexity analysis for the dynamic snake model based on the Potential Energy functional and the Hamiltonian formulation of the classical mechanics. First we see the snake model as a dynamical system whose singular points are the borders we seek. Next we show that a necessary condition for a singular point to be an attractor is that the energy functional is strictly convex in a neighborhood of it, that means, if the singular point is a local minimum of the potential energy. As a consequence of this analysis, a local expression relating the dynamic parameters and the rate of convergence arises. Such results link the convexity analysis of the potential energy and the dynamic snake model and point forward to the necessity of a physical quantity whose convexity analysis is related to the dynamic and which incorporate the velocity space. Such a quantity is exactly the (conservative) Hamiltonian of the system.


title: Critical Point for Maximum Likelihood Decoding of Linear Block Codes

abstract: In this letter, the SNR value at which the error performance curve of a soft decision maximum likelihood decoder reaches the slope corresponding to the code minimum distance is determined for a random code. Based on this value, referred to as the critical point, new insight about soft bounded distance decoding of random-like codes (and particularly Reed-Solomon codes) is provided.


title: Resource Management Services for a Grid Analysis Environment

abstract: Selecting optimal resources for submitting jobs on a computational Grid or accessing data from a data grid is one of the most important tasks of any Grid middleware. Most modern Grid software today satisfies this responsibility and gives a best-effort performance to solve this problem. Almost all decisions regarding scheduling and data access are made by the software automatically, giving users little or no control over the entire process. To solve this problem, a more interactive set of services and middleware is desired that provides users more information about Grid weather, and gives them more control over the decision making process. This paper presents a set of services that have been developed to provide more interactive resource management capabilities within the Grid Analysis Environment (GAE) being developed collaboratively by Caltech, NUST and several other institutes. These include a steering service, a job monitoring service and an estimator service that have been designed and written using a common Grid-enabled Web Services framework named Clarens. The paper also presents a performance analysis of the developed services to show that they have indeed resulted in a more interactive and powerful system for user-centric Grid-enabled physics analysis.


title: Heterogeneous Relational Databases for a Grid-enabled Analysis Environment

abstract: Grid based systems require a database access mechanism that can provide seamless homogeneous access to the requested data through a virtual data access system, i.e. a system which can take care of tracking the data that is stored in geographically distributed heterogeneous databases. This system should provide an integrated view of the data that is stored in the different repositories by using a virtual data access mechanism, i.e. a mechanism which can hide the heterogeneity of the backend databases from the client applications. This paper focuses on accessing data stored in disparate relational databases through a web service interface, and exploits the features of a Data Warehouse and Data Marts. We present a middleware that enables applications to access data stored in geographically distributed relational databases without being aware of their physical locations and underlying schema. A web service interface is provided to enable applications to access this middleware in a language and platform independent way. A prototype implementation was created based on Clarens [4], Unity [7] and POOL [8]. This ability to access the data stored in the distributed relational databases transparently is likely to be a very powerful one for Grid users, especially the scientific community wishing to collate and analyze data distributed over the Grid.


title: Fitness Uniform Deletion: A Simple Way to Preserve Diversity

abstract: A commonly experienced problem with population based optimisation methods is the gradual decline in population diversity that tends to occur over time. This can slow a system's progress or even halt it completely if the population converges on a local optimum from which it cannot escape. In this paper we present the Fitness Uniform Deletion Scheme (FUDS), a simple but somewhat unconventional approach to this problem. Under FUDS the deletion operation is modified to only delete those individuals which are "common" in the sense that there exist many other individuals of similar fitness in the population. This makes it impossible for the population to collapse to a collection of highly related individuals with similar fitness. Our experimental results on a range of optimisation problems confirm this, in particular for deceptive optimisation problems the performance is significantly more robust to variation in the selection intensity.


title: Scientific impact quantity and quality: Analysis of two sources of bibliographic data

abstract: Attempts to understand the consequence of any individual scientist's activity within the long-term trajectory of science is one of the most difficult questions within the philosophy of science. Because scientific publications play such as central role in the modern enterprise of science, bibliometric techniques which measure the ``impact'' of an individual publication as a function of the number of citations it receives from subsequent authors have provided some of the most useful empirical data on this question. Until recently, Thompson/ISI has provided the only source of large-scale ``inverted'' bibliographic data of the sort required for impact analysis. In the end of 2004, Google introduced a new service, GoogleScholar, making much of this same data available. Here we analyze 203 publications, collectively cited by more than 4000 other publications. We show surprisingly good agreement between data citation counts provided by the two services. Data quality across the systems is analyzed, and potentially useful complementarities between are considered. The additional robustness offered by multiple sources of such data promises to increase the utility of these measurements as open citation protocols and open access increase their impact on electronic scientific publication practices.


title: Bayesian Restoration of Digital Images Employing Markov Chain Monte Carlo a Review

abstract: A review of Bayesian restoration of digital images based on Monte Carlo techniques is presented. The topics covered include Likelihood, Prior and Posterior distributions, Poisson, Binay symmetric channel, and Gaussian channel models of Likelihood distribution,Ising and Potts spin models of Prior distribution, restoration of an image through Posterior maximization, statistical estimation of a true image from Posterior ensembles, Markov Chain Monte Carlo methods and cluster algorithms.


title: On Approximating Restricted Cycle Covers

abstract: A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is APX-hard and NP-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated within a factor of 2 for undirected graphs and within a factor of 8/3 in the case of directed graphs. This holds for arbitrary sets L.


title: TeXmacs-maxima interface

abstract: This tutorial presents features of the new and improved TeXmacs-maxima interface. It is designed for running maxima-5.9.2 from TeXmacs-1.0.5 (or later).


title: DTN Routing in a Mobility Pattern Space

abstract: Routing in Delay Tolerant Networks (DTNs) benefits considerably if one can take advantage of knowledge concerning node mobility. The main contribution of this paper is the definition of a generic routing scheme for DTNs using a high-dimensional Euclidean space constructed upon nodes' mobility patterns. For example, nodes are represented as points having as coordinates their probability of being found in each possible location. We present simulation results indicating that such a scheme can be beneficial in a scenario inspired by studies done on real mobility traces. This work should open the way to further use of the virtual space formalism in DTN routing.


title: Learning Polynomial Networks for Classification of Clinical Electroencephalograms

abstract: We describe a polynomial network technique developed for learning to classify clinical electroencephalograms (EEGs) presented by noisy features. Using an evolutionary strategy implemented within Group Method of Data Handling, we learn classification models which are comprehensively described by sets of short-term polynomials. The polynomial models were learnt to classify the EEGs recorded from Alzheimer and healthy patients and recognize the EEG artifacts. Comparing the performances of our technique and some machine learning methods we conclude that our technique can learn well-suited polynomial models which experts can find easy-to-understand.


title: The Bayesian Decision Tree Technique with a Sweeping Strategy

abstract: The uncertainty of classification outcomes is of crucial importance for many safety critical applications including, for example, medical diagnostics. In such applications the uncertainty of classification can be reliably estimated within a Bayesian model averaging technique that allows the use of prior information. Decision Tree (DT) classification models used within such a technique gives experts additional information by making this classification scheme observable. The use of the Markov Chain Monte Carlo (MCMC) methodology of stochastic sampling makes the Bayesian DT technique feasible to perform. However, in practice, the MCMC technique may become stuck in a particular DT which is far away from a region with a maximal posterior. Sampling such DTs causes bias in the posterior estimates, and as a result the evaluation of classification uncertainty may be incorrect. In a particular case, the negative effect of such sampling may be reduced by giving additional prior information on the shape of DTs. In this paper we describe a new approach based on sweeping the DTs without additional priors on the favorite shape of DTs. The performances of Bayesian DT techniques with the standard and sweeping strategies are compared on a synthetic data as well as on real datasets. Quantitatively evaluating the uncertainty in terms of entropy of class posterior probabilities, we found that the sweeping strategy is superior to the standard strategy.


title: Experimental Comparison of Classification Uncertainty for Randomised and Bayesian Decision Tree Ensembles

abstract: In this paper we experimentally compare the classification uncertainty of the randomised Decision Tree (DT) ensemble technique and the Bayesian DT technique with a restarting strategy on a synthetic dataset as well as on some datasets commonly used in the machine learning community. For quantitative evaluation of classification uncertainty, we use an Uncertainty Envelope dealing with the class posterior distribution and a given confidence probability. Counting the classifier outcomes, this technique produces feasible evaluations of the classification uncertainty. Using this technique in our experiments, we found that the Bayesian DT technique is superior to the randomised DT ensemble technique.


title: JClarens: A Java Framework for Developing and Deploying Web Services for Grid Computing

abstract: High Energy Physics (HEP) and other scientific communities have adopted Service Oriented Architectures (SOA) as part of a larger Grid computing effort. This effort involves the integration of many legacy applications and programming libraries into a SOA framework. The Grid Analysis Environment (GAE) is such a service oriented architecture based on the Clarens Grid Services Framework and is being developed as part of the Compact Muon Solenoid (CMS) experiment at the Large Hadron Collider (LHC) at European Laboratory for Particle Physics (CERN). Clarens provides a set of authorization, access control, and discovery services, as well as XMLRPC and SOAP access to all deployed services. Two implementations of the Clarens Web Services Framework (Python and Java) offer integration possibilities for a wide range of programming languages. This paper describes the Java implementation of the Clarens Web Services Framework called JClarens. and several web services of interest to the scientific and Grid community that have been deployed using JClarens.


title: Analyzing Worms and Network Traffic using Compression

abstract: Internet worms have become a widespread threat to system and network operations. In order to fight them more efficiently, it is necessary to analyze newly discovered worms and attack patterns. This paper shows how techniques based on Kolmogorov Complexity can help in the analysis of internet worms and network traffic. Using compression, different species of worms can be clustered by type. This allows us to determine whether an unknown worm binary could in fact be a later version of an existing worm in an extremely simple, automated, manner. This may become a useful tool in the initial analysis of malicious binaries. Furthermore, compression can also be useful to distinguish different types of network traffic and can thus help to detect traffic anomalies: Certain anomalies may be detected by looking at the compressibility of a network session alone. We furthermore show how to use compression to detect malicious network sessions that are very similar to known intrusion attempts. This technique could become a useful tool to detect new variations of an attack and thus help to prevent IDS evasion. We provide two new plugins for Snort which demonstrate both approaches.


title: On the Entropy Rate of Pattern Processes

abstract: We study the entropy rate of pattern sequences of stochastic processes, and its relationship to the entropy rate of the original process. We give a complete characterization of this relationship for i.i.d. processes over arbitrary alphabets, stationary ergodic processes over discrete alphabets, and a broad family of stationary ergodic processes over uncountable alphabets. For cases where the entropy rate of the pattern process is infinite, we characterize the possible growth rate of the block entropy.


title: Pushdown dimension

abstract: This paper develops the theory of pushdown dimension and explores its relationship with finite-state dimension. Pushdown dimension is trivially bounded above by finite-state dimension for all sequences, since a pushdown gambler can simulate any finite-state gambler. We show that for every rational 0 < d < 1, there exists a sequence with finite-state dimension d whose pushdown dimension is at most d/2. This establishes a quantitative analogue of the well-known fact that pushdown automata decide strictly more languages than finite automata.


title: Oracles Are Subtle But Not Malicious

abstract: Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper illustrates both that oracles can give us nontrivial insights about the barrier problems in circuit complexity, and that they need not prevent us from trying to solve those problems. First, we give an oracle relative to which PP has linear-sized circuits, by proving a new lower bound for perceptrons and low- degree threshold polynomials. This oracle settles a longstanding open question, and generalizes earlier results due to Beigel and to Buhrman, Fortnow, and Thierauf. More importantly, it implies the first nonrelativizing separation of "traditional" complexity classes, as opposed to interactive proof classes such as MIP and MA-EXP. For Vinodchandran showed, by a nonrelativizing argument, that PP does not have circuits of size n^k for any fixed k. We present an alternative proof of this fact, which shows that PP does not even have quantum circuits of size n^k with quantum advice. To our knowledge, this is the first nontrivial lower bound on quantum circuit size. Second, we study a beautiful algorithm of Bshouty et al. for learning Boolean circuits in ZPP^NP. We show that the NP queries in this algorithm cannot be parallelized by any relativizing technique, by giving an oracle relative to which ZPP^||NP and even BPP^||NP have linear-size circuits. On the other hand, we also show that the NP queries could be parallelized if P=NP. Thus, classes such as ZPP^||NP inhabit a "twilight zone," where we need to distinguish between relativizing and black-box techniques. Our results on this subject have implications for computational learning theory as well as for the circuit minimization problem.


title: Bounds on the Entropy of Patterns of I.I.D. Sequences

abstract: Bounds on the entropy of patterns of sequences generated by independently identically distributed (i.i.d.) sources are derived. A pattern is a sequence of indices that contains all consecutive integer indices in increasing order of first occurrence. If the alphabet of a source that generated a sequence is unknown, the inevitable cost of coding the unknown alphabet symbols can be exploited to create the pattern of the sequence. This pattern can in turn be compressed by itself. The bounds derived here are functions of the i.i.d. source entropy, alphabet size, and letter probabilities. It is shown that for large alphabets, the pattern entropy must decrease from the i.i.d. one. The decrease is in many cases more significant than the universal coding redundancy bounds derived in prior works. The pattern entropy is confined between two bounds that depend on the arrangement of the letter probabilities in the probability space. For very large alphabets whose size may be greater than the coded pattern length, all low probability letters are packed into one symbol. The pattern entropy is upper and lower bounded in terms of the i.i.d. entropy of the new packed alphabet. Correction terms, which are usually negligible, are provided for both upper and lower bounds.


title: Mapping Fusion and Synchronized Hyperedge Replacement into Logic Programming

abstract: In this paper we compare three different formalisms that can be used in the area of models for distributed, concurrent and mobile systems. In particular we analyze the relationships between a process calculus, the Fusion Calculus, graph transformations in the Synchronized Hyperedge Replacement with Hoare synchronization (HSHR) approach and logic programming. We present a translation from Fusion Calculus into HSHR (whereas Fusion Calculus uses Milner synchronization) and prove a correspondence between the reduction semantics of Fusion Calculus and HSHR transitions. We also present a mapping from HSHR into a transactional version of logic programming and prove that there is a full correspondence between the two formalisms. The resulting mapping from Fusion Calculus to logic programming is interesting since it shows the tight analogies between the two formalisms, in particular for handling name generation and mobility. The intermediate step in terms of HSHR is convenient since graph transformations allow for multiple, remote synchronizations, as required by Fusion Calculus semantics.


title: A Scalable Stream-Oriented Framework for Cluster Applications

abstract: This paper presents a stream-oriented architecture for structuring cluster applications. Clusters that run applications based on this architecture can scale to tenths of thousands of nodes with significantly less performance loss or reliability problems. Our architecture exploits the stream nature of the data flow and reduces congestion through load balancing, hides latency behind data pushes and transparently handles node failures. In our ongoing work, we are developing an implementation for this architecture and we are able to run simple data mining applications on a cluster simulator.


title: Learning Multi-Class Neural-Network Models from Electroencephalograms

abstract: We describe a new algorithm for learning multi-class neural-network models from large-scale clinical electroencephalograms (EEGs). This algorithm trains hidden neurons separately to classify all the pairs of classes. To find best pairwise classifiers, our algorithm searches for input variables which are relevant to the classification problem. Despite patient variability and heavily overlapping classes, a 16-class model learnt from EEGs of 65 sleeping newborns correctly classified 80.8% of the training and 80.1% of the testing examples. Additionally, the neural-network model provides a probabilistic interpretation of decisions.


title: A Neural-Network Technique for Recognition of Filaments in Solar Images

abstract: We describe a new neural-network technique developed for an automated recognition of solar filaments visible in the hydrogen H-alpha line full disk spectroheliograms. This technique allows neural networks learn from a few image fragments labelled manually to recognize the single filaments depicted on a local background. The trained network is able to recognize filaments depicted on the backgrounds with variations in brightness caused by atmospherics distortions. Despite the difference in backgrounds in our experiments the neural network has properly recognized filaments in the testing image fragments. Using a parabolic activation function we extend this technique to recognize multiple solar filaments which may appear in one fragment.


title: Learning from Web: Review of Approaches

abstract: Knowledge discovery is defined as non-trivial extraction of implicit, previously unknown and potentially useful information from given data. Knowledge extraction from web documents deals with unstructured, free-format documents whose number is enormous and rapidly growing. The artificial neural networks are well suitable to solve a problem of knowledge discovery from web documents because trained networks are able more accurately and easily to classify the learning and testing examples those represent the text mining domain. However, the neural networks that consist of large number of weighted connections and activation units often generate the incomprehensible and hard-to-understand models of text classification. This problem may be also addressed to most powerful recurrent neural networks that employ the feedback links from hidden or output units to their input units. Due to feedback links, recurrent neural networks are able take into account of a context in document. To be useful for data mining, self-organizing neural network techniques of knowledge extraction have been explored and developed. Self-organization principles were used to create an adequate neural-network structure and reduce a dimensionality of features used to describe text documents. The use of these principles seems interesting because ones are able to reduce a neural-network redundancy and considerably facilitate the knowledge representation.


title: A Learning Algorithm for Evolving Cascade Neural Networks

abstract: A new learning algorithm for Evolving Cascade Neural Networks (ECNNs) is described. An ECNN starts to learn with one input node and then adding new inputs as well as new hidden neurons evolves it. The trained ECNN has a nearly minimal number of input and hidden neurons as well as connections. The algorithm was successfully applied to classify artifacts and normal segments in clinical electroencephalograms (EEGs). The EEG segments were visually labeled by EEG-viewer. The trained ECNN has correctly classified 96.69% of the testing segments. It is slightly better than a standard fully connected neural network.


title: Self-Organizing Multilayered Neural Networks of Optimal Complexity

abstract: The principles of self-organizing the neural networks of optimal complexity is considered under the unrepresentative learning set. The method of self-organizing the multi-layered neural networks is offered and used to train the logical neural networks which were applied to the medical diagnostics.


title: Diagnostic Rule Extraction Using Neural Networks

abstract: The neural networks have trained on incomplete sets that a doctor could collect. Trained neural networks have correctly classified all the presented instances. The number of intervals entered for encoding the quantitative variables is equal two. The number of features as well as the number of neurons and layers in trained neural networks was minimal. Trained neural networks are adequately represented as a set of logical formulas that more comprehensible and easy-to-understand. These formulas are as the syndrome-complexes, which may be easily tabulated and represented as a diagnostic table that the doctors usually use. Decision rules provide the evaluations of their confidence in which interested a doctor. Conducted clinical researches have shown that iagnostic decisions produced by symbolic rules have coincided with the doctor's conclusions.


title: Polynomial Neural Networks Learnt to Classify EEG Signals

abstract: A neural network based technique is presented, which is able to successfully extract polynomial classification rules from labeled electroencephalogram (EEG) signals. To represent the classification rules in an analytical form, we use the polynomial neural networks trained by a modified Group Method of Data Handling (GMDH). The classification rules were extracted from clinical EEG data that were recorded from an Alzheimer patient and the sudden death risk patients. The third data is EEG recordings that include the normal and artifact segments. These EEG data were visually identified by medical experts. The extracted polynomial rules verified on the testing EEG data allow to correctly classify 72% of the risk group patients and 96.5% of the segments. These rules performs slightly better than standard feedforward neural networks.


title: A Neural Network Decision Tree for Learning Concepts from EEG Data

abstract: To learn the multi-class conceptions from the electroencephalogram (EEG) data we developed a neural network decision tree (DT), that performs the linear tests, and a new training algorithm. We found that the known methods fail inducting the classification models when the data are presented by the features some of them are irrelevant, and the classes are heavily overlapped. To train the DT, our algorithm exploits a bottom up search of the features that provide the best classification accuracy of the linear tests. We applied the developed algorithm to induce the DT from the large EEG dataset consisted of 65 patients belonging to 16 age groups. In these recordings each EEG segment was represented by 72 calculated features. The DT correctly classified 80.8% of the training and 80.1% of the testing examples. Correspondingly it correctly classified 89.2% and 87.7% of the EEG recordings.


title: Universal Minimax Discrete Denoising under Channel Uncertainty

abstract: The goal of a denoising algorithm is to recover a signal from its noise-corrupted observations. Perfect recovery is seldom possible and performance is measured under a given single-letter fidelity criterion. For discrete signals corrupted by a known discrete memoryless channel, the DUDE was recently shown to perform this task asymptotically optimally, without knowledge of the statistical properties of the source. In the present work we address the scenario where, in addition to the lack of knowledge of the source statistics, there is also uncertainty in the channel characteristics. We propose a family of discrete denoisers and establish their asymptotic optimality under a minimax performance criterion which we argue is appropriate for this setting. As we show elsewhere, the proposed schemes can also be implemented computationally efficiently.


title: Summarization from Medical Documents: A Survey

abstract: Objective: The aim of this paper is to survey the recent work in medical documents summarization. Background: During the last decade, documents summarization got increasing attention by the AI research community. More recently it also attracted the interest of the medical research community as well, due to the enormous growth of information that is available to the physicians and researchers in medicine, through the large and growing number of published journals, conference proceedings, medical sites and portals on the World Wide Web, electronic medical records, etc. Methodology: This survey gives first a general background on documents summarization, presenting the factors that summarization depends upon, discussing evaluation issues and describing briefly the various types of summarization techniques. It then examines the characteristics of the medical domain through the different types of medical documents. Finally, it presents and discusses the summarization techniques used so far in the medical domain, referring to the corresponding systems and their characteristics. Discussion and conclusions: The paper discusses thoroughly the promising paths for future research in medical documents summarization. It mainly focuses on the issue of scaling to large collections of documents in various languages and from different media, on personalization issues, on portability to new sub-domains, and on the integration of summarization technology in practical applications


title: Conditional Hardness for Approximate Coloring

abstract: We study the coloring problem: Given a graph G, decide whether $c(G) \leq q$ or $c(G) \ge Q$, where c(G) is the chromatic number of G. We derive conditional hardness for this problem for any constant $3 \le q < Q$. For $q\ge 4$, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For $q=3$, we base our hardness result on a certain `fish shaped' variant of his conjecture. We also prove that the problem almost coloring is hard for any constant $\eps>0$, assuming Khot's Unique Games conjecture. This is the problem of deciding for a given graph, between the case where one can 3-color all but a $\eps$ fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least $\eps$. Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].


title: Selection in Scale-Free Small World

abstract: In this paper we compare the performance characteristics of our selection based learning algorithm for Web crawlers with the characteristics of the reinforcement learning algorithm. The task of the crawlers is to find new information on the Web. The selection algorithm, called weblog update, modifies the starting URL lists of our crawlers based on the found URLs containing new information. The reinforcement learning algorithm modifies the URL orderings of the crawlers based on the received reinforcements for submitted documents. We performed simulations based on data collected from the Web. The collected portion of the Web is typical and exhibits scale-free small world (SFSW) structure. We have found that on this SFSW, the weblog update algorithm performs better than the reinforcement learning algorithm. It finds the new information faster than the reinforcement learning algorithm and has better new information/all submitted documents ratio. We believe that the advantages of the selection algorithm over reinforcement learning algorithm is due to the small world property of the Web.


title: Neural-Network Techniques for Visual Mining Clinical Electroencephalograms

abstract: In this chapter we describe new neural-network techniques developed for visual mining clinical electroencephalograms (EEGs), the weak electrical potentials invoked by brain activity. These techniques exploit fruitful ideas of Group Method of Data Handling (GMDH). Section 2 briefly describes the standard neural-network techniques which are able to learn well-suited classification modes from data presented by relevant features. Section 3 introduces an evolving cascade neural network technique which adds new input nodes as well as new neurons to the network while the training error decreases. This algorithm is applied to recognize artifacts in the clinical EEGs. Section 4 presents the GMDH-type polynomial networks learnt from data. We applied this technique to distinguish the EEGs recorded from an Alzheimer and a healthy patient as well as recognize EEG artifacts. Section 5 describes the new neural-network technique developed to induce multi-class concepts from data. We used this technique for inducing a 16-class concept from the large-scale clinical EEG data. Finally we discuss perspectives of applying the neural-network techniques to clinical EEGs.


title: Estimating Classification Uncertainty of Bayesian Decision Tree Technique on Financial Data

abstract: Bayesian averaging over classification models allows the uncertainty of classification outcomes to be evaluated, which is of crucial importance for making reliable decisions in applications such as financial in which risks have to be estimated. The uncertainty of classification is determined by a trade-off between the amount of data available for training, the diversity of a classifier ensemble and the required performance. The interpretability of classification models can also give useful information for experts responsible for making reliable classifications. For this reason Decision Trees (DTs) seem to be attractive classification models. The required diversity of the DT ensemble can be achieved by using the Bayesian model averaging all possible DTs. In practice, the Bayesian approach can be implemented on the base of a Markov Chain Monte Carlo (MCMC) technique of random sampling from the posterior distribution. For sampling large DTs, the MCMC method is extended by Reversible Jump technique which allows inducing DTs under given priors. For the case when the prior information on the DT size is unavailable, the sweeping technique defining the prior implicitly reveals a better performance. Within this Chapter we explore the classification uncertainty of the Bayesian MCMC techniques on some datasets from the StatLog Repository and real financial data. The classification uncertainty is compared within an Uncertainty Envelope technique dealing with the class posterior distribution and a given confidence probability. This technique provides realistic estimates of the classification uncertainty which can be easily interpreted in statistical terms with the aim of risk evaluation.


title: Comparison of the Bayesian and Randomised Decision Tree Ensembles within an Uncertainty Envelope Technique

abstract: Multiple Classifier Systems (MCSs) allow evaluation of the uncertainty of classification outcomes that is of crucial importance for safety critical applications. The uncertainty of classification is determined by a trade-off between the amount of data available for training, the classifier diversity and the required performance. The interpretability of MCSs can also give useful information for experts responsible for making reliable classifications. For this reason Decision Trees (DTs) seem to be attractive classification models for experts. The required diversity of MCSs exploiting such classification models can be achieved by using two techniques, the Bayesian model averaging and the randomised DT ensemble. Both techniques have revealed promising results when applied to real-world problems. In this paper we experimentally compare the classification uncertainty of the Bayesian model averaging with a restarting strategy and the randomised DT ensemble on a synthetic dataset and some domain problems commonly used in the machine learning community. To make the Bayesian DT averaging feasible, we use a Markov Chain Monte Carlo technique. The classification uncertainty is evaluated within an Uncertainty Envelope technique dealing with the class posterior distribution and a given confidence probability. Exploring a full posterior distribution, this technique produces realistic estimates which can be easily interpreted in statistical terms. In our experiments we found out that the Bayesian DTs are superior to the randomised DT ensembles within the Uncertainty Envelope technique.


title: An Evolving Cascade Neural Network Technique for Cleaning Sleep Electroencephalograms

abstract: Evolving Cascade Neural Networks (ECNNs) and a new training algorithm capable of selecting informative features are described. The ECNN initially learns with one input node and then evolves by adding new inputs as well as new hidden neurons. The resultant ECNN has a near minimal number of hidden neurons and inputs. The algorithm is successfully used for training ECNN to recognise artefacts in sleep electroencephalograms (EEGs) which were visually labelled by EEG-viewers. In our experiments, the ECNN outperforms the standard neural-network as well as evolutionary techniques.


title: Self-Organization of the Neuron Collective of Optimal Complexity

abstract: The optimal complexity of neural networks is achieved when the self-organization principles is used to eliminate the contradictions existing in accordance with the K. Godel theorem about incompleteness of the systems based on axiomatics. The principle of S. Beer exterior addition the Heuristic Group Method of Data Handling by A. Ivakhnenko realized is used.


title: A Neural-Network Technique to Learn Concepts from Electroencephalograms

abstract: A new technique is presented developed to learn multi-class concepts from clinical electroencephalograms. A desired concept is represented as a neuronal computational model consisting of the input, hidden, and output neurons. In this model the hidden neurons learn independently to classify the electroencephalogram segments presented by spectral and statistical features. This technique has been applied to the electroencephalogram data recorded from 65 sleeping healthy newborns in order to learn a brain maturation concept of newborns aged between 35 and 51 weeks. The 39399 and 19670 segments from these data have been used for learning and testing the concept, respectively. As a result, the concept has correctly classified 80.1% of the testing segments or 87.7% of the 65 records.


title: The Combined Technique for Detection of Artifacts in Clinical Electroencephalograms of Sleeping Newborns

abstract: In this paper we describe a new method combining the polynomial neural network and decision tree techniques in order to derive comprehensible classification rules from clinical electroencephalograms (EEGs) recorded from sleeping newborns. These EEGs are heavily corrupted by cardiac, eye movement, muscle and noise artifacts and as a consequence some EEG features are irrelevant to classification problems. Combining the polynomial network and decision tree techniques, we discover comprehensible classification rules whilst also attempting to keep their classification error down. This technique is shown to outperform a number of commonly used machine learning technique applied to automatically recognize artifacts in the sleep EEGs.


title: Proceedings of the Pacific Knowledge Acquisition Workshop 2004

abstract: Artificial intelligence (AI) research has evolved over the last few decades and knowledge acquisition research is at the core of AI research. PKAW-04 is one of three international knowledge acquisition workshops held in the Pacific-Rim, Canada and Europe over the last two decades. PKAW-04 has a strong emphasis on incremental knowledge acquisition, machine learning, neural nets and active mining. The proceedings contain 19 papers that were selected by the program committee among 24 submitted papers. All papers were peer reviewed by at least two reviewers. The papers in these proceedings cover the methods and tools as well as the applications related to develop expert systems or knowledge based systems.


title: Knowledge Representation Issues in Semantic Graphs for Relationship Detection

abstract: An important task for Homeland Security is the prediction of threat vulnerabilities, such as through the detection of relationships between seemingly disjoint entities. A structure used for this task is a "semantic graph", also known as a "relational data graph" or an "attributed relational graph". These graphs encode relationships as "typed" links between a pair of "typed" nodes. Indeed, semantic graphs are very similar to semantic networks used in AI. The node and link types are related through an ontology graph (also known as a schema). Furthermore, each node has a set of attributes associated with it (e.g., "age" may be an attribute of a node of type "person"). Unfortunately, the selection of types and attributes for both nodes and links depends on human expertise and is somewhat subjective and even arbitrary. This subjectiveness introduces biases into any algorithm that operates on semantic graphs. Here, we raise some knowledge representation issues for semantic graphs and provide some possible solutions using recently developed ideas in the field of complex networks. In particular, we use the concept of transitivity to evaluate the relevance of individual links in the semantic graph for detecting relationships. We also propose new statistical measures for semantic graphs and illustrate these semantic measures on graphs constructed from movies and terrorism data.


title: Rendezvous Regions: A Scalable Architecture for Resource Discovery and Service Location in Large-Scale Mobile Networks

abstract: In large-scale wireless networks such as mobile ad hoc and sensor networks, efficient and robust service discovery and data-access mechanisms are both essential and challenging. Rendezvous-based mechanisms provide a valuable solution for provisioning a wide range of services. In this paper, we describe Rendezvous Regions (RRs) - a novel scalable rendezvous-based architecture for wireless networks. RR is a general architecture proposed for service location and bootstrapping in ad hoc networks, in addition to data-centric storage, configuration, and task assignment in sensor networks. In RR the network topology is divided into geographical regions, where each region is responsible for a set of keys representing the services or data of interest. Each key is mapped to a region based on a hash-table-like mapping scheme. A few elected nodes inside each region are responsible for maintaining the mapped information. The service or data provider stores the information in the corresponding region and the seekers retrieve it from there. We run extensive detailed simulations, and high-level simulations and analysis, to investigate the design space, and study the architecture in various environments including node mobility and failures. We evaluate it against other approaches to identify its merits and limitations. The results show high success rate and low overhead even with dynamics. RR scales to large number of nodes and is highly robust and efficient to node failures. It is also robust to node mobility and location inaccuracy with a significant advantage over point-based rendezvous mechanisms.


title: Metalinguistic Information Extraction for Terminology

abstract: This paper describes and evaluates the Metalinguistic Operation Processor (MOP) system for automatic compilation of metalinguistic information from technical and scientific documents. This system is designed to extract non-standard terminological resources that we have called Metalinguistic Information Databases (or MIDs), in order to help update changing glossaries, knowledge bases and ontologies, as well as to reflect the metastable dynamics of special-domain knowledge.


title: Dichotomy for Voting Systems

abstract: Scoring protocols are a broad class of voting systems. Each is defined by a vector $(\alpha_1,\alpha_2,...,\alpha_m)$, $\alpha_1 \geq \alpha_2 \geq >... \geq \alpha_m$, of integers such that each voter contributes $\alpha_1$ points to his/her first choice, $\alpha_2$ points to his/her second choice, and so on, and any candidate receiving the most points is a winner. What is it about scoring-protocol election systems that makes some have the desirable property of being NP-complete to manipulate, while others can be manipulated in polynomial time? We find the complete, dichotomizing answer: Diversity of dislike. Every scoring-protocol election system having two or more point values assigned to candidates other than the favorite--i.e., having $||\{\alpha_i \condition 2 \leq i \leq m\}||\geq 2$--is NP-complete to manipulate. Every other scoring-protocol election system can be manipulated in polynomial time. In effect, we show that--other than trivial systems (where all candidates alway tie), plurality voting, and plurality voting's transparently disguised translations--\emph{every} scoring-protocol election system is NP-complete to manipulate.


title: An Improved Remote User Authentication Scheme Using Smart Cards

abstract: In 2000, Hwang and Li proposed a new remote user authentication scheme using smart cards. In the same year, Chan and Cheng pointed out that Hwang and Li’s scheme is not secure against the masquerade attack. Further, in 2003, Shen, Lin and Hwang pointed out a different type of attack on Hwang and Li’s scheme and presented a modified scheme to remove its security pitfalls. This paper presents an improved scheme which is secure against Chan-Cheng and all the extended attacks.


title: The Modified Scheme is still vulnerable to the parallel Session Attack

abstract: In 2002, Chien–Jan–Tseng introduced an efficient remote user authentication scheme using smart cards. Further, in 2004, W. C. Ku and S. M. Chen proposed an efficient remote user authentication scheme using smart cards to solve the security problems of Chien et al.’s scheme. Recently, Hsu and Yoon et al. pointed out the security weakness of the Ku and Chen’s scheme Furthermore, Yoon et al. modified the password change phase of Ku and Chen’s scheme and they also proposed a new efficient remote user authentication scheme using smart cards. This paper analyzes that the modified scheme of Yoon et al. still vulnerable to parallel session attack.


title: Adaptive Online Prediction by Following the Perturbed Leader

abstract: When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of sqrt(complexity/current loss) renders the analysis of Weighted Majority derivatives quite complicated. In particular, for arbitrary weights there have been no results proven so far. The analysis of the alternative "Follow the Perturbed Leader" (FPL) algorithm from Kalai & Vempala (2003) (based on Hannan's algorithm) is easier. We derive loss bounds for adaptive learning rate and both finite expert classes with uniform weights and countable expert classes with arbitrary weights. For the former setup, our loss bounds match the best known results so far, while for the latter our results are new.


title: Prediction of Large Alphabet Processes and Its Application to Adaptive Source Coding

abstract: The problem of predicting a sequence $x_1,x_2,...$ generated by a discrete source with unknown statistics is considered. Each letter $x_{t+1}$ is predicted using information on the word $x_1x_2... x_t$ only. In fact, this problem is a classical problem which has received much attention. Its history can be traced back to Laplace. We address the problem where each $x_i$ belongs to some large (or even infinite) alphabet. A method is presented for which the precision is greater than for known algorithms, where precision is estimated by the Kullback-Leibler divergence. The results can readily be translated to results about adaptive coding.


title: Performance of Gaussian Signalling in Non Coherent Rayleigh Fading Channels

abstract: The mutual information of a discrete time memoryless Rayleigh fading channel is considered, where neither the transmitter nor the receiver has the knowledge of the channel state information except the fading statistics. We present the mutual information of this channel in closed form when the input distribution is complex Gaussian, and derive a lower bound in terms of the capacity of the corresponding non fading channel and the capacity when the perfect channel state information is known at the receiver.


title: A Decomposition Approach to Multi-Vehicle Cooperative Control

abstract: We present methods that generate cooperative strategies for multi-vehicle control problems using a decomposition approach. By introducing a set of tasks to be completed by the team of vehicles and a task execution method for each vehicle, we decomposed the problem into a combinatorial component and a continuous component. The continuous component of the problem is captured by task execution, and the combinatorial component is captured by task assignment. In this paper, we present a solver for task assignment that generates near-optimal assignments quickly and can be used in real-time applications. To motivate our methods, we apply them to an adversarial game between two teams of vehicles. One team is governed by simple rules and the other by our algorithms. In our study of this game we found phase transitions, showing that the task assignment problem is most difficult to solve when the capabilities of the adversaries are comparable. Finally, we implement our algorithms in a multi-level architecture with a variable replanning rate at each level to provide feedback on a dynamically changing and uncertain environment.


title: Coloring Artemis graphs

abstract: We consider the class A of graphs that contain no odd hole, no antihole, and no ``prism'' (a graph consisting of two disjoint triangles with three disjoint paths between them). We show that the coloring algorithm found by the second and fourth author can be implemented in time O(n^2m) for any graph in A with n vertices and m edges, thereby improving on the complexity proposed in the original paper.


title: On the Unicity Distance of Stego Key

abstract: Steganography is about how to send secret message covertly. And the purpose of steganalysis is to not only detect the existence of the hidden message but also extract it. So far there have been many reliable detecting methods on various steganographic algorithms, while there are few approaches that can extract the hidden information. In this paper, the difficulty of extracting hidden information, which is essentially a kind of privacy, is analyzed with information-theoretic method in the terms of unicity distance of steganographic key (abbreviated stego key). A lower bound for the unicity distance is obtained, which shows the relations between key rate, message rate, hiding capacity and difficulty of extraction. Furthermore the extracting attack to steganography is viewed as a special kind of cryptanalysis, and an effective method on recovering the stego key of popular LSB replacing steganography in spatial images is presented by combining the detecting technique of steganalysis and correlation attack of cryptanalysis together. The analysis for this method and experimental results on steganographic software ``Hide and Seek 4.1" are both accordant with the information-theoretic conclusion.


title: The Convergence of Digital-Libraries and the Peer-Review Process

abstract: Pre-print repositories have seen a significant increase in use over the past fifteen years across multiple research domains. Researchers are beginning to develop applications capable of using these repositories to assist the scientific community above and beyond the pure dissemination of information. The contribution set forth by this paper emphasizes a deconstructed publication model in which the peer-review process is mediated by an OAI-PMH peer-review service. This peer-review service uses a social-network algorithm to determine potential reviewers for a submitted manuscript and for weighting the relative influence of each participating reviewer's evaluations. This paper also suggests a set of peer-review specific metadata tags that can accompany a pre-print's existing metadata record. The combinations of these contributions provide a unique repository-centric peer-review model that fits within the widely deployed OAI-PMH framework.


title: Capacity per Unit Energy of Fading Channels with a Peak Constraint

abstract: A discrete-time single-user scalar channel with temporally correlated Rayleigh fading is analyzed. There is no side information at the transmitter or the receiver. A simple expression is given for the capacity per unit energy, in the presence of a peak constraint. The simple formula of Verdu for capacity per unit cost is adapted to a channel with memory, and is used in the proof. In addition to bounding the capacity of a channel with correlated fading, the result gives some insight into the relationship between the correlation in the fading process and the channel capacity. The results are extended to a channel with side information, showing that the capacity per unit energy is one nat per Joule, independently of the peak power constraint. A continuous-time version of the model is also considered. The capacity per unit energy subject to a peak constraint (but no bandwidth constraint) is given by an expression similar to that for discrete time, and is evaluated for Gauss-Markov and Clarke fading channels.


title: Componentwise Least Squares Support Vector Machines

abstract: This chapter describes componentwise Least Squares Support Vector Machines (LS-SVMs) for the estimation of additive models consisting of a sum of nonlinear components. The primal-dual derivations characterizing LS-SVMs for the estimation of the additive model result in a single set of linear equations with size growing in the number of data-points. The derivation is elaborated for the classification as well as the regression case. Furthermore, different techniques are proposed to discover structure in the data by looking for sparse components in the model based on dedicated regularization schemes on the one hand and fusion of the componentwise LS-SVMs training with a validation criterion on the other hand. (keywords: LS-SVMs, additive models, regularization, structure detection)


title: Improved direct sum theorem in classical communication complexity

abstract: Withdrawn due to critical error.


title: Time, Space, and Energy in Reversible Computing

abstract: We survey results of a quarter century of work on computation by reversible general-purpose computers (in this setting Turing machines), and general reversible simulation of irreversible computations, with respect to energy-, time- and space requirements.


title: Universal Similarity

abstract: We survey a new area of 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.


title: Discrete Morse Theory for free chain complexes

abstract: We extend the combinatorial Morse complex construction to the arbitrary free chain complexes, and give a short, self-contained, and elementary proof of the quasi-isomorphism between the original chain complex and its Morse complex. Even stronger, the main result states that, if $C_*$ is a free chain complex, and $\cm$ an acyclic matching, then $C_*=C_*^\cm\oplus T_*$, where $C_*^\cm$ is the Morse complex generated by the critical elements, and $T_*$ is an acyclic complex.


title: A Probabilistic Upper Bound on Differential Entropy

abstract: A novel, non-trivial, probabilistic upper bound on the entropy of an unknown one-dimensional distribution, given the support of the distribution and a sample from that distribution, is presented. No knowledge beyond the support of the unknown distribution is required, nor is the distribution required to have a density. Previous distribution-free bounds on the cumulative distribution function of a random variable given a sample of that variable are used to construct the bound. A simple, fast, and intuitive algorithm for computing the entropy bound from a sample is provided.


title: On Optimality Condition of Complex Systems: Computational Evidence

abstract: A general condition determining the optimal performance of a complex system has not yet been found and the possibility of its existence is unknown. To contribute in this direction, an optimization algorithm as a complex system is presented. The performance of the algorithm for any problem is controlled as a convex function with a single optimum. To characterize the performance optimums, certain quantities of the algorithm and the problem are suggested and interpreted as their complexities. An optimality condition of the algorithm is computationally found: if the algorithm shows its best performance for a problem, then the complexity of the algorithm is in a linear relationship with the complexity of the problem. The optimality condition provides a new perspective to the subject by recognizing that the relationship between certain quantities of the complex system and the problem may determine the optimal performance.


title: A Multi-proxy Signature Scheme for Partial delegation with Warrant

abstract: In some cases, the original signer may delegate its signing power to a specified proxy group while ensuring individual accountability of each participantsigner. The proxy signature scheme that achieves such purpose is called the multi-proxy signature scheme and the signature generated by the specified proxy group is called multi-proxy signature for the original signer. Recently such scheme has been discussed by Lin et al. Lins scheme is based on partial delegation by Mambo et al. In present chapter we introduce a new multi-proxy signature scheme, which requires less computational overhead in comparison to Lin et al, and also fulfill the requirement of partial delegation with warrant simultaneously.


title: A New Remote User Authentication Scheme Using Smart Cards with Check Digits

abstract: Since 1981, when Lamport introduced the remote user authentication scheme using table, a plenty of schemes had been proposed with table and without table using. In 1993, Chang and Wu [5] introduced Remote password authentication scheme with smart cards. A number of remote authentication schemes with smart cards have been proposed since then. These schemes allow a valid user to login a remote server and access the services provided by the remote server. But still there is no scheme to authenticate the remote proxy user. In this paper we propose firstly, a protocol to authenticate a proxy user remotely using smartcards.


title: An Efficient Scheme for Sensitive Message Transmission using Blind Signcryption

abstract: Blind signature schemes enable a useful protocol that guarantee the anonymity of the participants while Signcryption offers authentication of message and confidentiality of messages at the same time and more efficiently. In this paper, we present a blind signcryption scheme that combines the functionality of blind signature and signcryption. This blind Signcryption is useful for applications that are based on anonymity untracebility and unlinkability.


title: P-Selectivity, Immunity, and the Power of One Bit

abstract: We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset, but we also prove that every infinite P-selective set has some infinite subset in EXP/1. Informally put, the immunity of P-sel is so fragile that it is pierced by a single bit of information. The above claims follow from broader results that we obtain about the immunity of the P-selective sets. In particular, we prove that for every recursive function f, P-sel is DTIME(f)-immune. Yet we also prove that P-sel is not \Pi_2^p/1-immune.


title: ID-based Ring Signature and Proxy Ring Signature Schemes from Bilinear Pairings

abstract: In 2001, Rivest et al. firstly introduced the concept of ring signatures. A ring signature is a simplified group signature without any manager. It protects the anonymity of a signer. The first scheme proposed by Rivest et al. was based on RSA cryptosystem and certificate based public key setting. The first ring signature scheme based on DLP was proposed by Abe, Ohkubo, and Suzuki. Their scheme is also based on the general certificate-based public key setting too. In 2002, Zhang and Kim proposed a new ID-based ring signature scheme using pairings. Later Lin and Wu proposed a more efficient ID-based ring signature scheme. Both these schemes have some inconsistency in computational aspect. In this paper we propose a new ID-based ring signature scheme and a proxy ring signature scheme. Both the schemes are more efficient than existing one. These schemes also take care of the inconsistencies in above two schemes.


title: The Capacity of Random Ad hoc Networks under a Realistic Link Layer Model

abstract: The problem of determining asymptotic bounds on the capacity of a random ad hoc network is considered. Previous approaches assumed a threshold-based link layer model in which a packet transmission is successful if the SINR at the receiver is greater than a fixed threshold. In reality, the mapping from SINR to packet success probability is continuous. Hence, over each hop, for every finite SINR, there is a non-zero probability of packet loss. With this more realistic link model, it is shown that for a broad class of routing and scheduling schemes, a fixed fraction of hops on each route have a fixed non-zero packet loss probability. In a large network, a packet travels an asymptotically large number of hops from source to destination. Consequently, it is shown that the cumulative effect of per-hop packet loss results in a per-node throughput of only O(1/n) (instead of Theta(1/sqrt{n log{n}})) as shown previously for the threshold-based link model). A scheduling scheme is then proposed to counter this effect. The proposed scheme improves the link SINR by using conservative spatial reuse, and improves the per-node throughput to O(1/(K_n sqrt{n log{n}})), where each cell gets a transmission opportunity at least once every K_n slots, and K_n tends to infinity as n tends to infinity.


title: A DNA Sequence Compression Algorithm Based on LUT and LZ77

abstract: This article introduces a new DNA sequence compression algorithm which is based on LUT and LZ77 algorithm. Combined a LUT-based pre-coding routine and LZ77 compression routine,this algorithm can approach a compression ratio of 1.9bits \slash base and even lower.The biggest advantage of this algorithm is fast execution, small memory occupation and easy implementation.


title: Single-solution Random 3-SAT Instances

abstract: We study a class of random 3-SAT instances having exactly one solution. The properties of this ensemble considerably differ from those of a random 3-SAT ensemble. It is numerically shown that the running time of several complete and stochastic local search algorithms monotonically increases as the clause density is decreased. Therefore, there is no easy-hard-easy pattern of hardness as for standard random 3-SAT ensemble. Furthermore, the running time for short single-solution formulas increases with the problem size much faster than for random 3-SAT formulas from the phase transition region.


title: Spectral Orbits and Peak-to-Average Power Ratio of Boolean Functions with respect to the {I,H,N}^n Transform

abstract: We enumerate the inequivalent self-dual additive codes over GF(4) of blocklength n, thereby extending the sequence A090899 in The On-Line Encyclopedia of Integer Sequences from n = 9 to n = 12. These codes have a well-known interpretation as quantum codes. They can also be represented by graphs, where a simple graph operation generates the orbits of equivalent codes. We highlight the regularity and structure of some graphs that correspond to codes with high distance. The codes can also be interpreted as quadratic Boolean functions, where inequivalence takes on a spectral meaning. In this context we define PAR_IHN, peak-to-average power ratio with respect to the {I,H,N}^n transform set. We prove that PAR_IHN of a Boolean function is equivalent to the the size of the maximum independent set over the associated orbit of graphs. Finally we propose a construction technique to generate Boolean functions with low PAR_IHN and algebraic degree higher than 2.


title: Incremental Medians via Online Bidding

abstract: In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following Mettu and Plaxton, we study the incremental medians problem, where k is not known in advance, and the algorithm produces a nested sequence of facility sets where the kth set has size k. The algorithm is c-cost-competitive if the cost of each set is at most c times the cost of the optimum set of size k. We give improved incremental algorithms for the metric version: an 8-cost-competitive deterministic algorithm, a 2e ~ 5.44-cost-competitive randomized algorithm, a (24+epsilon)-cost-competitive, poly-time deterministic algorithm, and a (6e+epsilon ~ .31)-cost-competitive, poly-time randomized algorithm. The algorithm is s-size-competitive if the cost of the kth set is at most the minimum cost of any set of size k, and has size at most s k. The optimal size-competitive ratios for this problem are 4 (deterministic) and e (randomized). We present the first poly-time O(log m)-size-approximation algorithm for the offline problem and first poly-time O(log m)-size-competitive algorithm for the incremental problem. Our proofs reduce incremental medians to the following online bidding problem: faced with an unknown threshold T, an algorithm submits "bids" until it submits a bid that is at least the threshold. It pays the sum of all its bids. We prove that folklore algorithms for online bidding are optimally competitive.


title: The reverse greedy algorithm for the metric k-median problem

abstract: The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the resulting total distance from the customers to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between ?(log n/ log log n) and O(log n).


title: Wikis in Tuple Spaces

abstract: We consider storing the pages of a wiki in a tuple space and the effects this might have on the wiki experience. In particular, wiki pages are stored in tuples with a few identifying values such as title, author, revision date, content, etc. and pages are retrieved by sending the tuple space templates, such as one that gives the title but nothing else, leaving the tuple space to resolve to a single tuple. We use a tuple space wiki to avoid deadlocks, infinite loops, and wasted efforts when page edit contention arises and examine how a tuple space wiki changes the wiki experience.


title: A Distributed Multimedia Communication System and its Applications to E-Learning

abstract: In this paper we report on a multimedia communication system including a VCoIP (Video Conferencing over IP) software with a distributed architecture and its applications for teaching scenarios. It is a simple, ready-to-use scheme for distributed presenting, recording and streaming multimedia content. We also introduce and investigate concepts and experiments to IPv6 user and session mobility, with the special focus on real-time video group communication.


title: k-core decomposition: a tool for the visualization of large scale networks

abstract: We use the k-core decomposition to visualize large scale complex networks in two dimensions. This decomposition, based on a recursive pruning of the least connected vertices, allows to disentangle the hierarchical structure of networks by progressively focusing on their central cores. By using this strategy we develop a general visualization algorithm that can be used to compare the structural properties of various networks and highlight their hierarchical structure. The low computational complexity of the algorithm, O(n+e), where 'n' is the size of the network, and 'e' is the number of edges, makes it suitable for the visualization of very large sparse networks. We apply the proposed visualization tool to several real and synthetic graphs, showing its utility in finding specific structural fingerprints of computer generated and real world networks.


title: Cooperative Game Theory within Multi-Agent Systems for Systems Scheduling

abstract: Research concerning organization and coordination within multi-agent systems continues to draw from a variety of architectures and methodologies. The work presented in this paper combines techniques from game theory and multi-agent systems to produce self-organizing, polymorphic, lightweight, embedded agents for systems scheduling within a large-scale real-time systems environment. Results show how this approach is used to experimentally produce optimum real-time scheduling through the emergent behavior of thousands of agents. These results are obtained using a SWARM simulation of systems scheduling within a High Energy Physics experiment consisting of 2500 digital signal processors.


title: Prototype of Fault Adaptive Embedded Software for Large-Scale Real-Time Systems

abstract: This paper describes a comprehensive prototype of large-scale fault adaptive embedded software developed for the proposed Fermilab BTeV high energy physics experiment. Lightweight self-optimizing agents embedded within Level 1 of the prototype are responsible for proactive and reactive monitoring and mitigation based on specified layers of competence. The agents are self-protecting, detecting cascading failures using a distributed approach. Adaptive, reconfigurable, and mobile objects for reliablility are designed to be self-configuring to adapt automatically to dynamically changing environments. These objects provide a self-healing layer with the ability to discover, diagnose, and react to discontinuities in real-time processing. A generic modeling environment was developed to facilitate design and implementation of hardware resource specifications, application data flow, and failure mitigation strategies. Level 1 of the planned BTeV trigger system alone will consist of 2500 DSPs, so the number of components and intractable fault scenarios involved make it impossible to design an `expert system' that applies traditional centralized mitigative strategies based on rules capturing every possible system state. Instead, a distributed reactive approach is implemented using the tools and methodologies developed by the Real-Time Embedded Systems group.


title: Computing finite-dimensional bipartite quantum separability

abstract: Ever since entanglement was identified as a computational and cryptographic resource, effort has been made to find an efficient way to tell whether a given density matrix represents an unentangled, or separable, state. Essentially, this is the quantum separability problem. Chapters 1 to 3 motivate a new interior-point algorithm which, given the expected values of a subset of an orthogonal basis of observables of an otherwise unknown quantum state, searches for an entanglement witness in the span of the subset of observables. When all the expected values are known, the algorithm solves the separability problem. In Chapter 4, I give the motivation for the algorithm and show how it can be used in a particular physical scenario to detect entanglement (or decide separability) of an unknown quantum state using as few quantum resources as possible. I then explain the intuitive idea behind the algorithm and relate it to the standard algorithms of its kind. I end the chapter with a comparison of the complexities of the algorithms surveyed in Chapter 3. Finally, in Chapter 5, I present the details of the algorithm and discuss its performance relative to standard methods.


title: Efficient and Robust Geocasting Protocols for Sensor Networks

abstract: Geocasting is the delivery of packets to nodes within a certain geographic area. For many applications in wireless ad hoc and sensor networks, geocasting is an important and frequent communication service. The challenging problem in geocasting is distributing the packets to all the nodes within the geocast region with high probability but with low overhead. According to our study we notice a clear tradeoff between the proportion of nodes in the geocast region that receive the packet and the overhead incurred by the geocast packet especially at low densities and irregular distributions. We present two novel protocols for geocasting that achieve high delivery rate and low overhead by utilizing the local location information of nodes to combine geographic routing mechanisms with region flooding. We show that the first protocol Geographic-Forwarding-Geocast (GFG) has close-to-minimum overhead in dense networks and that the second protocol Geographic-Forwarding-Perimeter-Geocast (GFPG) provides guaranteed delivery without global flooding or global network information even at low densities and with the existence of region gaps or obstacles. An adaptive version of the second protocol (GFPG*) has the desirable property of perfect delivery at all densities and close-to-minimum overhead at high densities. We evaluate our mechanisms and compare them using simulation to other proposed geocasting mechanisms. The results show the significant improvement in delivery rate (up to 63% higher delivery percentage in low density networks) and reduction in overhead (up to 80% reduction) achieved by our mechanisms. We hope for our protocols to become building block mechanisms for dependable sensor network architectures that require robust efficient geocast services.


title: Modelling investment in artificial stock markets: Analytical and Numerical Results

abstract: In this article we study the behavior of a group of economic agents in the context of cooperative game theory, interacting according to rules based on the Potts Model with suitable modifications. Each agent can be thought of as belonging to a chain, where agents can only interact with their nearest neighbors (periodic boundary conditions are imposed). Each agent can invest an amount σ_{i}=0,...,q-1. Using the transfer matrix method we study analytically, among other things, the behavior of the investment as a function of a control parameter (denoted β) for the cases q=2 and 3. For q>3 numerical evaluation of eigenvalues and high precision numerical derivatives are used in order to assess this information.


title: Tight Lower Bounds for Query Processing on Streaming and External Memory Data

abstract: We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is sufficiently small, e.g., polylogarithmic in the size of the input). We also show that neither joins nor sorting are feasible if the product of the number $r(n)$ of scans of the external memory and the size $s(n)$ of the internal memory buffers is sufficiently small, e.g., of size $o(\sqrt[5]{n})$. We also establish tight bounds for the complexity of XPath evaluation and filtering.


title: A New Kind of Hopfield Networks for Finding Global Optimum

abstract: The Hopfield network has been applied to solve optimization problems over decades. However, it still has many limitations in accomplishing this task. Most of them are inherited from the optimization algorithms it implements. The computation of a Hopfield network, defined by a set of difference equations, can easily be trapped into one local optimum or another, sensitive to initial conditions, perturbations, and neuron update orders. It doesn't know how long it will take to converge, as well as if the final solution is a global optimum, or not. In this paper, we present a Hopfield network with a new set of difference equations to fix those problems. The difference equations directly implement a new powerful optimization algorithm.


title: Pluggable AOP: Designing Aspect Mechanisms for Third-party Composition

abstract: Studies of Aspect-Oriented Programming (AOP) usually focus on a language in which a specific aspect extension is integrated with a base language. Languages specified in this manner have a fixed, non-extensible AOP functionality. In this paper we consider the more general case of integrating a base language with a set of domain specific third-party aspect extensions for that language. We present a general mixin-based method for implementing aspect extensions in such a way that multiple, independently developed, dynamic aspect extensions can be subject to third-party composition and work collaboratively.


title: Defragmenting the Module Layout of a Partially Reconfigurable Device

abstract: Modern generations of field-programmable gate arrays (FPGAs) allow for partial reconfiguration. In an online context, where the sequence of modules to be loaded on the FPGA is unknown beforehand, repeated insertion and deletion of modules leads to progressive fragmentation of the available space, making defragmentation an important issue. We address this problem by propose an online and an offline component for the defragmentation of the available space. We consider defragmenting the module layout on a reconfigurable device. This corresponds to solving a two-dimensional strip packing problem. Problems of this type are NP-hard in the strong sense, and previous algorithmic results are rather limited. Based on a graph-theoretic characterization of feasible packings, we develop a method that can solve two-dimensional defragmentation instances of practical size to optimality. Our approach is validated for a set of benchmark instances.