title: Menzerath-Altmann Law for Syntactic Structures in Ukrainian

abstract: In the paper, the definition of clause suitable for an automated processing of a Ukrainian text is proposed. The Menzerath-Altmann law is verified on the sentence level and the parameters for the dependences of the clause length counted in words and syllables on the sentence length counted in clauses are calculated for "Perekhresni Stezhky" ("The Cross-Paths"), a novel by Ivan Franko.


title: An Abstract Monte-Carlo Method for the Analysis of Probabilistic Programs

abstract: We introduce a new method, combination of random testing and abstract interpretation, for the analysis of programs featuring both probabilistic and non-probabilistic nondeterminism. After introducing "ordinary" testing, we show how to combine testing and abstract interpretation and give formulas linking the precision of the results to the number of iterations. We then discuss complexity and optimization issues and end with some experimental results.


title: One-bit Distributed Sensing and Coding for Field Estimation in Sensor Networks

abstract: This paper formulates and studies a general distributed field reconstruction problem using a dense network of noisy one-bit randomized scalar quantizers in the presence of additive observation noise of unknown distribution. A constructive quantization, coding, and field reconstruction scheme is developed and an upper-bound to the associated mean squared error (MSE) at any point and any snapshot is derived in terms of the local spatio-temporal smoothness properties of the underlying field. It is shown that when the noise, sensor placement pattern, and the sensor schedule satisfy certain weak technical requirements, it is possible to drive the MSE to zero with increasing sensor density at points of field continuity while ensuring that the per-sensor bitrate and sensing-related network overhead rate simultaneously go to zero. The proposed scheme achieves the order-optimal MSE versus sensor density scaling behavior for the class of spatially constant spatio-temporal fields.


title: On Delayed Sequential Coding of Correlated Sources

abstract: Motivated by video coding applications, the problem of sequential coding of correlated sources with encoding and/or decoding frame-delays is studied. The fundamental tradeoffs between individual frame rates, individual frame distortions, and encoding/decoding frame-delays are derived in terms of a single-letter information-theoretic characterization of the rate-distortion region for general inter-frame source correlations and certain types of potentially frame specific and coupled single-letter fidelity criteria. The sum-rate-distortion region is characterized in terms of generalized directed information measures highlighting their role in delayed sequential source coding problems. For video sources which are spatially stationary memoryless and temporally Gauss-Markov, MSE frame distortions, and a sum-rate constraint, our results expose the optimality of idealized differential predictive coding among all causal sequential coders, when the encoder uses a positive rate to describe each frame. Somewhat surprisingly, causal sequential encoding with one-frame-delayed noncausal sequential decoding can exactly match the sum-rate-MSE performance of joint coding for all nontrivial MSE-tuples satisfying certain positive semi-definiteness conditions. Thus, even a single frame-delay holds potential for yielding significant performance improvements. Generalizations to higher order Markov sources are also presented and discussed. A rate-distortion performance equivalence between, causal sequential encoding with delayed noncausal sequential decoding, and, delayed noncausal sequential encoding with causal sequential decoding, is also established.


title: Fitting the WHOIS Internet data

abstract: We consider the RIPE WHOIS Internet data as characterized by the Cooperative Association for Internet Data Analysis (CAIDA), and show that the Tempered Preferential Attachment model [1] provides an excellent fit to this data. [1] D'Souza, Borgs, Chayes, Berger and Kleinberg, to appear PNAS USA, 2007.


title: A Virtual Logo Keyboard for People with Motor Disabilities

abstract: In our society, people with motor impairments are oftentimes socially excluded from their environment. This is unfortunate because every human being should have the possibility to obtain the necessary conditions to live a normal life. Although there is technology to assist people with motor impairments, few systems are targeted for programming environments. We have created a system, called Logo Keyboard, to assist people with motor disabilities to program with the Logo programming language. With this special keyboard we can help more people to get involved into computer programming and to develop projects in different areas.


title: Reasoning from a schema and from an analog in software code reuse

abstract: The activity of design involves the decomposition of problems into subproblems and the development and evaluation of solutions. In many cases, solution development is not done from scratch. Designers often evoke and adapt solutions developed in the past. These solutions may come from an internal source, i.e. the memory of the designers, and/or from an external source. The goal of this paper is to analyse the characteristics of the cognitive mechanisms, the knowledge and the representations involved in the code reuse activity performed by experienced programmers. More generally, the focus is the control structure of the reuse activity. Data collected in an experiment in which programmers had to design programs are analyzed. Two code reuse situations are distinguished depending on whether or not the processes involved in reuse start before the elaboration of what acts as a source-solution. Our analysis highlights the use of reasoning from a schema and from an analog in the code reuse activity.


title: Measuring Cognitive Activities in Software Engineering

abstract: This paper presents an approach to the study of cognitive activities in collaborative software development. This approach has been developed by a multidisciplinary team made up of software engineers and cognitive psychologists. The basis of this approach is to improve our understanding of software development by observing professionals at work. The goal is to derive lines of conduct or good practices based on observations and analyses of the processes that are naturally used by software engineers. The strategy involved is derived from a standard approach in cognitive science. It is based on the videotaping of the activities of software engineers, transcription of the videos, coding of the transcription, defining categories from the coded episodes and defining cognitive behaviors or dialogs from the categories. This project presents two original contributions that make this approach generic in software engineering. The first contribution is the introduction of a formal hierarchical coding scheme, which will enable comparison of various types of observations. The second is the merging of psychological and statistical analysis approaches to build a cognitive model. The details of this new approach are illustrated with the initial data obtained from the analysis of technical review meetings.


title: The Effect of Object-Oriented Programming Expertise in Several Dimensions of Comprehension Strategies

abstract: This study analyzes object-oriented (OO) program comprehension by experts and novices. We examine the effect of expertise in three dimensions of comprehension strategies: the scope of the comprehension, the top-down versus bottom-up direction of the processes, and the guidance of the comprehension activity. Overall, subjects were similar in the scope of their comprehension, although the experts tended to consult more files. We found strong evidence of top-down, inference-driven behaviors, as well as multiple guidance in expert comprehension. We also found evidence of execution-based guidance and less use of top-down processes in novice comprehension. Guidance by inheritance and composition relationships in the OO program was not dominant, but nevertheless played a substantial role in expert program comprehension. However, these static relationships more closely tied to the OO nature of the program were exploited poorly by novices. To conclude, these results are discussed with respect to the literature on procedural program comprehension.


title: Expert Programming Knowledge: a Schema-Based Approach

abstract: The topic of this chapter is the role of expert programming knowledge in the understanding activity. In the "schema-based approach", the role of semantic structures is emphasized whereas, in the "control-flow approach", the role of syntactic structures is emphasized. Data which support schema-based models of understanding are presented. Data which are more consistent with the "control-flow approach" allow to discuss the limits of the former kind of models.


title: What model(s) for program understanding?

abstract: The first objective of this paper is to present and discuss various types of models of program understanding. They are discussed in relation to models of text understanding. The second objective of this paper is to assess the effect of purpose for reading, or more specifically programming task, on the cognitive processes involved and representations constructed in program understanding. This is done in the theoretical framework of van Dijk and Kintsch's model of text understanding (1983).


title: An empirical study of software reuse by experts in object-oriented design

abstract: This paper presents an empirical study of the software reuse activity by expert designers in the context of object-oriented design. Our study focuses on the three following aspects of reuse : (1) the interaction between some design processes, e.g. constructing a problem representation, searching for and evaluating solutions, and reuse processes, i.e. retrieving and using previous solutions, (2) the mental processes involved in reuse, e.g. example-based retrieval or bottom-up versus top-down expanding of the solution, and (3) the mental representations constructed throughout the reuse activity, e.g. dynamic versus static representations. Some implications of these results for the specification of software reuse support environments are discussed.


title: Negotiation in collaborative assessment of design solutions: an empirical study on a Concurrent Engineering process

abstract: In Concurrent engineering, design solutions are not only produced by individuals specialized in a given field. Due to the team nature of the design activity, solutions are negotiated. Our objective is to analyse the argumentation processes leading to these negotiated solutions. These processes take place in the meetings which group together specialists with a co-design aim. We conducted cognitive ergonomics research work during the definition phase of an aeronautical design project in which the participants work in Concurrent Engineering. We recorded, retranscribed and analysed 7 multi-speciality meetings. These meetings were organised, as needed, to assess the integration of the solutions of each speciality into a global solution. We found that there are three main design proposal assessment modes which can be combined in these meetings: (a) analytical assessment mode, (b) comparative assessment mode (c) analogical assessment mode. Within these assessment modes, different types of arguments are used. Furthermore we found a typical temporal negotiation process.


title: Power Optimal Scheduling for Guaranteed Throughput in Multi-access Fading Channels

abstract: A power optimal scheduling algorithm that guarantees desired throughput and bounded delay to each user is developed for fading multi-access multi-band systems. The optimization is over the joint space of all rate allocation and coding strategies. The proposed scheduling assigns rates on each band based only on the current system state, and subsequently uses optimal multi-user signaling to achieve these rates. The scheduling is computationally simple, and hence scalable. Due to uplink-downlink duality, all the results extend in straightforward fashion to the broadcast channels.


title: MMSE Optimal Algebraic Space-Time Codes

abstract: Design of Space-Time Block Codes (STBCs) for Maximum Likelihood (ML) reception has been predominantly the main focus of researchers. However, the ML decoding complexity of STBCs becomes prohibitive large as the number of transmit and receive antennas increase. Hence it is natural to resort to a suboptimal reception technique like linear Minimum Mean Squared Error (MMSE) receiver. Barbarossa et al and Liu et al have independently derived necessary and sufficient conditions for a full rate linear STBC to be MMSE optimal, i.e achieve least Symbol Error Rate (SER). Motivated by this problem, certain existing high rate STBC constructions from crossed product algebras are identified to be MMSE optimal. Also, it is shown that a certain class of codes from cyclic division algebras which are special cases of crossed product algebras are MMSE optimal. Hence, these STBCs achieve least SER when MMSE reception is employed and are fully diverse when ML reception is employed.


title: On Evaluating the Rate-Distortion Function of Sources with Feed-Forward and the Capacity of Channels with Feedback

abstract: We study the problem of computing the rate-distortion function for sources with feed-forward and the capacity for channels with feedback. The formulas (involving directed information) for the optimal rate-distortion function with feed-forward and channel capacity with feedback are multi-letter expressions and cannot be computed easily in general. In this work, we derive conditions under which these can be computed for a large class of sources/channels with memory and distortion/cost measures. Illustrative examples are also provided.


title: A canonical form for some piecewise defined functions

abstract: We define a canonical form for piecewise defined functions. We show that this has a wider range of application as well as better complexity properties than previous work.


title: Dealing With Logical Omniscience: Expressiveness and Pragmatics

abstract: We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest (especially with probability in the picture), we show that they are not equi-expressive. We then consider the pragmatics of dealing with logical omniscience-- how to choose an approach and construct an appropriate model.


title: Plagiarism Detection in arXiv

abstract: We describe a large-scale application of methods for finding plagiarism in research document collections. The methods are applied to a collection of 284,834 documents collected by arXiv.org over a 14 year period, covering a few different research disciplines. The methodology efficiently detects a variety of problematic author behaviors, and heuristics are developed to reduce the number of false positives. The methods are also efficient enough to implement as a real-time submission screen for a collection many times larger.


title: A polynomial time algorithm to approximate the mixed volume within a simply exponential factor

abstract: Let ${\bf K} = (K_1, ..., K_n)$ be an $n$-tuple of convex compact subsets in the Euclidean space $\R^n$, and let $V(\cdot)$ be the Euclidean volume in $\R^n$. The Minkowski polynomial $V_{{\bf K}}$ is defined as $V_{{\bf K}}(\lambda_1, ... ,\lambda_n) = V(\lambda_1 K_1 +, ..., + \lambda_n K_n)$ and the mixed volume $V(K_1, ..., K_n)$ as $$ V(K_1, ..., K_n) = \frac{\partial^n}{\partial \lambda_1...\partial \lambda_n} V_{{\bf K}}(\lambda_1 K_1 +, ..., + \lambda_n K_n). $$ Our main result is a poly-time algorithm which approximates $V(K_1, ..., K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small. Our approach is based on a particular approximation of $\log(V(K_1, ..., K_n))$ by a solution of some convex minimization problem. We prove the mixed volume analogues of the Van der Waerden and Schrijver-Valiant conjectures on the permanent. These results, interesting on their own, allow us to justify the abovementioned approximation by a convex minimization, which is solved using the ellipsoid method and a randomized poly-time time algorithm for the approximation of the volume of a convex set.


title: Probabilistic Analysis of Linear Programming Decoding

abstract: We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses previous non-asymptotic results for LDPC codes, and in particular exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a generalized matching. An interesting by-product of our analysis is to establish the existence of ``probabilistic expansion'' in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst-case setting.


title: Network Coding for Distributed Storage Systems

abstract: Peer-to-peer distributed storage systems provide reliable access to data through redundancy spread over nodes across the Internet. A key goal is to minimize the amount of bandwidth used to maintain that redundancy. Storing a file using an erasure code, in fragments spread across nodes, promises to require less redundancy and hence less maintenance bandwidth than simple replication to provide the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new fragment in a distributed way while transferring as little data as possible across the network. In this paper, we introduce a general technique to analyze storage architectures that combine any form of coding and replication, as well as presenting two new schemes for maintaining redundancy using erasure codes. First, we show how to optimally generate MDS fragments directly from existing fragments in the system. Second, we introduce a new scheme called Regenerating Codes which use slightly larger fragments than MDS but have lower overall bandwidth use. We also show through simulation that in realistic environments, Regenerating Codes can reduce maintenance bandwidth use by 25 percent or more compared with the best previous design--a hybrid of replication and erasure codes--while simplifying system architecture.


title: A multivariate interlace polynomial

abstract: We define a multivariate polynomial that generalizes several interlace polynomials defined by Arratia, Bollobas and Sorkin on the one hand, and Aigner and van der Holst on the other. We follow the route traced by Sokal, who defined a multivariate generalization of Tutte's polynomial. We also show that bounded portions of our interlace polynomial can be evaluated in polynomial time for graphs of bounded clique-width. Its full evaluation is necessarly exponential just because of the size of the result.


title: Comment on Improved Analysis of List Decoding and Its Application to Convolutional Codes and Turbo Codes

abstract: In a recent paper [1] an improved analysis concerning the analysis of List Decoding was presented. The event that the correct codeword is excluded from the list is central. For the additive white Gaussian noise (AWGN) channel an important quantity is the in [1] called effective Euclidean distance. This was earlier considered in [2] under the name Vector Euclidean Distance, where also a simple mathematical expression for this quantity was easily derived for any list size. In [1], a geometrical analysis gives this when the list size is 1, 2 or 3.


title: Estimation of the Rate-Distortion Function

abstract: Motivated by questions in lossy data compression and by theoretical considerations, we examine the problem of estimating the rate-distortion function of an unknown (not necessarily discrete-valued) source from empirical data. Our focus is the behavior of the so-called "plug-in" estimator, which is simply the rate-distortion function of the empirical distribution of the observed data. Sufficient conditions are given for its consistency, and examples are provided to demonstrate that in certain cases it fails to converge to the true rate-distortion function. The analysis of its performance is complicated by the fact that the rate-distortion function is not continuous in the source distribution; the underlying mathematical problem is closely related to the classical problem of establishing the consistency of maximum likelihood estimators. General consistency results are given for the plug-in estimator applied to a broad class of sources, including all stationary and ergodic ones. A more general class of estimation problems is also considered, arising in the context of lossy data compression when the allowed class of coding distributions is restricted; analogous results are developed for the plug-in estimator in that case. Finally, consistency theorems are formulated for modified (e.g., penalized) versions of the plug-in, and for estimating the optimal reproduction distribution.


title: A Dynamic I/O Model for TRACON Traffic Management

abstract: This work investigates the TRACON flow management around a major airport. Aircraft flows are analyzed through a study of TRACON trajectories records. Rerouting and queuing processes are highlighted and airport characteristics are shown as function of the number of planes in the TRACON. Then, a simple input-output TRACON queuing and landing model is proposed. This model is calibrated and validated using available TRACON data. It reproduces the same phenomenon as the real system. This model is used to show the impact of limiting the number of aircrafts in the TRACON. A limited number of aircraft does not increase delays but reduces the controller's workload and increases safety.


title: Construction of Minimal Tail-Biting Trellises for Codes over Finite Abelian Groups

abstract: A definition of atomic codeword for a group code is presented. Some properties of atomic codewords of group codes are investigated. Using these properties, it is shown that every minimal tail-biting trellis for a group code over a finite abelian group can be constructed from its characteristic generators, which extends the work of Koetter and Vardy who treated the case of a linear code over a field. We also present an efficient algorithm for constructing the minimal tail-biting trellis of a group code over a finite abelian group, given a generator matrix.


title: Probability Bracket Notation, Probability Vectors, Markov Chains and Stochastic Processes

abstract: Dirac notation has been widely used for vectors in Hilbert spaces of Quantum Theories and now also in Information Retrieval. In this paper, we propose to use Probability Bracket Notation (PBN) for probability modeling. The new symbols are defined similarly (but not identically) as in Dirac notation. By using PBN to represent fundamental definitions and theorems for discrete and continuous random variables, we show that PBN could play a similar role in probability sample space as Dirac notation in Hilbert space. We also find a close relation between our system state P-kets and probability vectors in Markov chains. In the end, we apply PBN to some important stochastic processes, present the master equation of time-continuous Markov chains in both Schrodinger and Heisenberg pictures. We identify our system state P-bra with Doi's state function and Peliti's standard bra. We summarize the similarities and differences between PBN and Dirac Notation in the two tables of Appendix A.


title: Gnutella: Topology Dynamics On Phase Space

abstract: In this paper, the topology dynamic of Gnutella is studied through phase space. The dynamic changes in peer degree are studied as a time series in two dimensional phase space which is defined as the number of connected leaves and the number of connected ultras. The reported degrees are concentrated in three special Software related regions that we named as Ultra Stable Region, Leaf Stable Region and Transition Belt. A method is proposed to classify degree traces in phase space into different classes. Connection churn then is studied along with the churn in degree. It shows that the topological structure of Gnutella is rather stable in its connection degree but not the topology itself. The connection drop rate is estimated and the live time of connections is inferred afterwards. M/M/m/m loss queue system is introduced to model the degree keeping process in Gnutella. This model revealed that the degree stable is ensured by large new connection efforts. In other words the stable in topological structure of Gnutella is a results of essential unstable in its topology. That opens a challenge to the basic design philosophy of this network.


title: High-rate, Multi-Symbol-Decodable STBCs from Clifford Algebras

abstract: It is well known that Space-Time Block Codes (STBCs) obtained from Orthogonal Designs (ODs) are single-symbol-decodable (SSD) and from Quasi-Orthogonal Designs (QODs) are double-symbol decodable. However, there are SSD codes that are not obtainable from ODs and DSD codes that are not obtainable from QODs. In this paper a method of constructing $g$-symbol decodable ($g$-SD) STBCs using representations of Clifford algebras are presented which when specialized to $g=1,2$ gives SSD and DSD codes respectively. For the number of transmit antennas $2^a$ the rate (in complex symbols per channel use) of the $g$-SD codes presented in this paper is $\frac{a+1-g}{2^{a-g}}$. The maximum rate of the DSD STBCs from QODs reported in the literature is $\frac{a}{2^{a-1}}$ which is smaller than the rate $\frac{a-1}{2^{a-2}}$ of the DSD codes of this paper, for $2^a$ transmit antennas. In particular, the reported DSD codes for 8 and 16 transmit antennas offer rates 1 and 3/4 respectively whereas the known STBCs from QODs offer only 3/4 and 1/2 respectively. The construction of this paper is applicable for any number of transmit antennas.


title: Searching for low weight pseudo-codewords

abstract: Belief Propagation (BP) and Linear Programming (LP) decodings of Low Density Parity Check (LDPC) codes are discussed. We summarize results of instanton/pseudo-codeword approach developed for analysis of the error-floor domain of the codes. Instantons are special, code and decoding specific, configurations of the channel noise contributing most to the Frame-Error-Rate (FER). Instantons are decoded into pseudo-codewords. Instanton/pseudo-codeword with the lowest weight describes the largest Signal-to-Noise-Ratio (SNR) asymptotic of FER, while the whole spectra of the low weight instantons is descriptive of the FER vs SNR profile in the extended error-floor domain. First, we describe a general optimization method that allows to find the instantons for any coding/decoding. Second, we introduce LP-specific pseudo-codeword search algorithm that allows efficient calculations of the pseudo-codeword spectra. Finally, we discuss results of combined BP/LP error-floor exploration experiments for two model codes.


title: Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs

abstract: This paper presents a systematic methodology based on the algebraic theory of signal processing to classify and derive fast algorithms for linear transforms. Instead of manipulating the entries of transform matrices, our approach derives the algorithms by stepwise decomposition of the associated signal models, or polynomial algebras. This decomposition is based on two generic methods or algebraic principles that generalize the well-known Cooley-Tukey FFT and make the algorithms' derivations concise and transparent. Application to the 16 discrete cosine and sine transforms yields a large class of fast algorithms, many of which have not been found before.


title: Shape preservation behavior of spline curves

abstract: Shape preservation behavior of a spline consists of criterial conditions for preserving convexity, inflection, collinearity, torsion and coplanarity shapes of data polgonal arc. We present our results which acts as an improvement in the definitions of and provide geometrical insight into each of the above shape preservation criteria. We also investigate the effect of various results from the literature on various shape preservation criteria. These results have not been earlier refered in the context of shape preservation behaviour of splines. We point out that each curve segment need to satisfy more than one shape preservation criteria. We investigate the conflict between different shape preservation criteria 1)on each curve segment and 2)of adjacent curve segments. We derive simplified formula for shape preservation criteria for cubic curve segments. We study the shape preservation behavior of cubic Catmull-Rom splines and see that, though being very simple spline curve, it indeed satisfy all the shape preservation criteria.


title: The Suspension Calculus and its Relationship to Other Explicit Treatments of Substitution in Lambda Calculi

abstract: The intrinsic treatment of binding in the lambda calculus makes it an ideal data structure for representing syntactic objects with binding such as formulas, proofs, types, and programs. Supporting such a data structure in an implementation is made difficult by the complexity of the substitution operation relative to lambda terms. In this paper we present the suspension calculus, an explicit treatment of meta level binding in the lambda calculus. We prove properties of this calculus which make it a suitable replacement for the lambda calculus in implementation. Finally, we compare the suspension calculus with other explicit treatments of substitution.


title: Uniform and Partially Uniform Redistribution Rules

abstract: This short paper introduces two new fusion rules for combining quantitative basic belief assignments. These rules although very simple have not been proposed in literature so far and could serve as useful alternatives because of their low computation cost with respect to the recent advanced Proportional Conflict Redistribution rules developed in the DSmT framework.


title: On the variance of subset sum estimation

abstract: For high volume data streams and large data warehouses, sampling is used for efficient approximate answers to aggregate queries over selected subsets. Mathematically, we are dealing with a set of weighted items and want to support queries to arbitrary subset sums. With unit weights, we can compute subset sizes which together with the previous sums provide the subset averages. The question addressed here is which sampling scheme we should use to get the most accurate subset sum estimates. We present a simple theorem on the variance of subset sum estimation and use it to prove variance optimality and near-optimality of subset sum estimation with different known sampling schemes. This variance is measured as the average over all subsets of any given size. By optimal we mean there is no set of input weights for which any sampling scheme can have a better average variance. Such powerful results can never be established experimentally. The results of this paper are derived mathematically. For example, we show that appropriately weighted systematic sampling is simultaneously optimal for all subset sizes. More standard schemes such as uniform sampling and probability-proportional-to-size sampling with replacement can be arbitrarily bad. Knowing the variance optimality of different sampling schemes can help deciding which sampling scheme to apply in a given context.


title: Optimizing the SINR operating point of spatial networks

abstract: This paper addresses the following question, which is of interest in the design and deployment of a multiuser decentralized network. Given a total system bandwidth of W Hz and a fixed data rate constraint of R bps for each transmission, how many frequency slots N of size W/N should the band be partitioned into to maximize the number of simultaneous transmissions in the network? In an interference-limited ad-hoc network, dividing the available spectrum results in two competing effects: on the positive side, it reduces the number of users on each band and therefore decreases the interference level which leads to an increased SINR, while on the negative side the SINR requirement for each transmission is increased because the same information rate must be achieved over a smaller bandwidth. Exploring this tradeoff between bandwidth and SINR and determining the optimum value of N in terms of the system parameters is the focus of the paper. Using stochastic geometry, we analytically derive the optimal SINR threshold (which directly corresponds to the optimal spectral efficiency) on this tradeoff curve and show that it is a function of only the path loss exponent. Furthermore, the optimal SINR point lies between the low-SINR (power-limited) and high-SINR (bandwidth-limited) regimes. In order to operate at this optimal point, the number of frequency bands (i.e., the reuse factor) should be increased until the threshold SINR, which is an increasing function of the reuse factor, is equal to the optimal value.


title: Quantized vs. Analog Feedback for the MIMO Downlink: A Comparison between Zero-Forcing Based Achievable Rates

abstract: We consider a MIMO fading broadcast channel and compare the achievable ergodic rates when the channel state information at the transmitter is provided by analog noisy feedback or by quantized (digital) feedback. The superiority of digital feedback is shown, with perfect or imperfect CSIR, whenever the number of feedback channel uses per channel coefficient is larger than 1. Also, we show that by proper design of the digital feedback link, errors in the feedback have a minor effect even by using very simple uncoded modulation. Finally, we show that analog feedback achieves a fraction 1 - 2F of the optimal multiplexing gain even in the presence of a feedback delay, when the fading belongs to the class of Doppler processes with normalized maximum Doppler frequency shift 0 <= F <= 1/2.


title: Finding large and small dense subgraphs

abstract: We consider two optimization problems related to finding dense subgraphs. The densest at-least-k-subgraph problem (DalkS) is to find an induced subgraph of highest average degree among all subgraphs with at least k vertices, and the densest at-most-k-subgraph problem (DamkS) is defined similarly. These problems are related to the well-known densest k-subgraph problem (DkS), which is to find the densest subgraph on exactly k vertices. We show that DalkS can be approximated efficiently, while DamkS is nearly as hard to approximate as the densest k-subgraph problem.


title: Bounds on ordered codes and orthogonal arrays

abstract: We derive new estimates of the size of codes and orthogonal arrays in the ordered Hamming space (the Niederreiter-Rosenbloom-Tsfasman space). We also show that the eigenvalues of the ordered Hamming scheme, the association scheme that describes the combinatorics of the space, are given by the multivariable Krawtchouk polynomials, and establish some of their properties.


title: Graph Splicing System

abstract: The string splicing was introduced by Tom Head which stands as an abstract model for the DNA recombination under the influence of restriction enzymes. The complex chemical process of three dimensional molecules in three dimensional space can be modeled using graphs. The graph splicing systems which were studied so far, can only be applied to a particular type of graphs which could be interpreted as linear or circular graphs. In this paper, we take a different and a novel approach to splice two graphs and introduce a splicing system for graphs that can be applied to all types of graphs. Splicing two graphs can be thought of as a new operation, among the graphs, that generates many new graphs from the given two graphs. Taking a different line of thinking, some of the graph theoretical results of the splicing are studied.


title: New Models for the Correlation in Sensor Data

abstract: In this paper, we propose two new models of spatial correlations in sensor data in a data-gathering sensor network. A particular property of these models is that if a sensor node knows in \textit{how many} bits it needs to transmit its data, then it also knows \textit{which} bits of its data it needs to transmit.


title: Efficient First-Order Temporal Logic for Infinite-State Systems

abstract: In this paper we consider the specification and verification of infinite-state systems using temporal logic. In particular, we describe parameterised systems using a new variety of first-order temporal logic that is both powerful enough for this form of specification and tractable enough for practical deductive verification. Importantly, the power of the temporal language allows us to describe (and verify) asynchronous systems, communication delays and more complex properties such as liveness and fairness properties. These aspects appear difficult for many other approaches to infinite-state verification.


title: Evolutionary Approaches to Minimizing Network Coding Resources

abstract: We wish to minimize the resources used for network coding while achieving the desired throughput in a multicast scenario. We employ evolutionary approaches, based on a genetic algorithm, that avoid the computational complexity that makes the problem NP-hard. Our experiments show great improvements over the sub-optimal solutions of prior methods. Our new algorithms improve over our previously proposed algorithm in three ways. First, whereas the previous algorithm can be applied only to acyclic networks, our new method works also with networks with cycles. Second, we enrich the set of components used in the genetic algorithm, which improves the performance. Third, we develop a novel distributed framework. Combining distributed random network coding with our distributed optimization yields a network coding protocol where the resources used for coding are optimized in the setup phase by running our evolutionary algorithm at each node of the network. We demonstrate the effectiveness of our approach by carrying out simulations on a number of different sets of network topologies.


title: Genetic Representations for Evolutionary Minimization of Network Coding Resources

abstract: We demonstrate how a genetic algorithm solves the problem of minimizing the resources used for network coding, subject to a throughput constraint, in a multicast scenario. A genetic algorithm avoids the computational complexity that makes the problem NP-hard and, for our experiments, greatly improves on sub-optimal solutions of established methods. We compare two different genotype encodings, which tradeoff search space size with fitness landscape, as well as the associated genetic operators. Our finding favors a smaller encoding despite its fewer intermediate solutions and demonstrates the impact of the modularity enforced by genetic operators on the performance of the algorithm.


title: Hadwiger and Helly-type theorems for disjoint unit spheres

abstract: We prove Helly-type theorems for line transversals to disjoint unit balls in $\R^{d}$. In particular, we show that a family of $n \geq 2d$ disjoint unit balls in $\R^d$ has a line transversal if, for some ordering $\prec$ of the balls, any subfamily of 2d balls admits a line transversal consistent with $\prec$. We also prove that a family of $n \geq 4d-1$ disjoint unit balls in $\R^d$ admits a line transversal if any subfamily of size $4d-1$ admits a transversal.


title: Polygraphs for termination of left-linear term rewriting systems

abstract: We present a methodology for proving termination of left-linear term rewriting systems (TRSs) by using Albert Burroni's polygraphs, a kind of rewriting systems on algebraic circuits. We translate the considered TRS into a polygraph of minimal size whose termination is proven with a polygraphic interpretation, then we get back the property on the TRS. We recall Yves Lafont's general translation of TRSs into polygraphs and known links between their termination properties. We give several conditions on the original TRS, including being a first-order functional program, that ensure that we can reduce the size of the polygraphic translation. We also prove sufficient conditions on the polygraphic interpretations of a minimal translation to imply termination of the original TRS. Examples are given to compare this method with usual polynomial interpretations.


title: The Fibers and Range of Reduction Graphs in Ciliates

abstract: The biological process of gene assembly has been modeled based on three types of string rewriting rules, called string pointer rules, defined on so-called legal strings. It has been shown that reduction graphs, graphs that are based on the notion of breakpoint graph in the theory of sorting by reversal, for legal strings provide valuable insights into the gene assembly process. We characterize which legal strings obtain the same reduction graph (up to isomorphism), and moreover we characterize which graphs are (isomorphic to) reduction graphs.


title: A Formal Model for Programming Wireless Sensor Networks

abstract: In this paper we present new developments in the expressiveness and in the theory of a Calculus for Sensor Networks (CSN). We combine a network layer of sensor devices with a local object model to describe sensor devices with state. The resulting calculus is quite small and yet very expressive. We also present a type system and a type invariance result for the calculus. These results provide the fundamental framework for the development of programming languages and run-time environments.


title: Deciding k-colourability of $P_5$-free graphs in polynomial time

abstract: The problem of computing the chromatic number of a $P_5$-free graph is known to be NP-hard. In contrast to this negative result, we show that determining whether or not a $P_5$-free graph admits a $k$-colouring, for each fixed number of colours $k$, can be done in polynomial time. If such a colouring exists, our algorithm produces it.


title: Transmission Capacity of Ad Hoc Networks with Spatial Diversity

abstract: This paper derives the outage probability and transmission capacity of ad hoc wireless networks with nodes employing multiple antenna diversity techniques, for a general class of signal distributions. This analysis allows system performance to be quantified for fading or non-fading environments. The transmission capacity is given for interference-limited uniformly random networks on the entire plane with path loss exponent $\alpha>2$ in which nodes use: (1) static beamforming through $M$ sectorized antennas, for which the increase in transmission capacity is shown to be $\Theta(M^2)$ if the antennas are without sidelobes, but less in the event of a nonzero sidelobe level; (2) dynamic eigen-beamforming (maximal ratio transmission/combining), in which the increase is shown to be $\Theta(M^{\frac{2}{\alpha}})$; (3) various transmit antenna selection and receive antenna selection combining schemes, which give appreciable but rapidly diminishing gains; and (4) orthogonal space-time block coding, for which there is only a small gain due to channel hardening, equivalent to Nakagami-$m$ fading for increasing $m$. It is concluded that in ad hoc networks, static and dynamic beamforming perform best, selection combining performs well but with rapidly diminishing returns with added antennas, and that space-time block coding offers only marginal gains.


title: Gaussian Interference Channel Capacity to Within One Bit

abstract: The capacity of the two-user Gaussian interference channel has been open for thirty years. The understanding on this problem has been limited. The best known achievable region is due to Han-Kobayashi but its characterization is very complicated. It is also not known how tight the existing outer bounds are. In this work, we show that the existing outer bounds can in fact be arbitrarily loose in some parameter ranges, and by deriving new outer bounds, we show that a simplified Han-Kobayashi type scheme can achieve to within a single bit the capacity for all values of the channel parameters. We also show that the scheme is asymptotically optimal at certain high SNR regimes. Using our results, we provide a natural generalization of the point-to-point classical notion of degrees of freedom to interference-limited scenarios.


title: Design and Analysis of the REESSE1+ Public Key Cryptosystem v2.21

abstract: In this paper, the authors give the definitions of a coprime sequence and a lever function, and describe the five algorithms and six characteristics of a prototypal public key cryptosystem which is used for encryption and signature, and based on three new problems and one existent problem: the multivariate permutation problem (MPP), the anomalous subset product problem (ASPP), the transcendental logarithm problem (TLP), and the polynomial root finding problem (PRFP). Prove by reduction that MPP, ASPP, and TLP are computationally at least equivalent to the discrete logarithm problem (DLP) in the same prime field, and meanwhile find some evidence which inclines people to believe that the new problems are harder than DLP each, namely unsolvable in DLP subexponential time. Demonstrate the correctness of the decryption and the verification, deduce the probability of a plaintext solution being nonunique is nearly zero, and analyze the exact securities of the cryptosystem against recovering a plaintext from a ciphertext, extracting a private key from a public key or a signature, and forging a signature through known signatures, public keys, and messages on the assumption that IFP, DLP, and LSSP can be solved. Studies manifest that the running times of effectual attack tasks are greater than or equal to O(2^n) so far when n = 80, 96, 112, or 128 with lgM = 696, 864, 1030, or 1216. As viewed from utility, it should be researched further how to decrease the length of a modulus and to increase the speed of the decryption.


title: Hierarchical Unambiguity

abstract: We develop techniques to investigate relativized hierarchical unambiguous computation. We apply our techniques to generalize known constructs involving relativized unambiguity based complexity classes (UP and \mathcal{UP}) to new constructs involving arbitrary higher levels of the relativized unambiguous polynomial hierarchy (UPH). Our techniques are developed on constraints imposed by hierarchical arrangement of unambiguous nondeterministic polynomial-time Turing machines, and so they differ substantially, in applicability and in nature, from standard methods (such as the switching lemma [Hastad, Computational Limitations of Small-Depth Circuits, MIT Press, 1987]), which play roles in carrying out similar generalizations. Aside from achieving these generalizations, we resolve a question posed by Cai, Hemachandra, and Vyskoc [J. Cai, L. Hemachandra, and J. Vyskoc, Promises and fault-tolerant database access, In K. Ambos-Spies, S. Homer, and U. Schoening, editors, Complexity Theory, pages 101-146. Cambridge University Press, 1993] on an issue related to nonadaptive Turing access to UP and adaptive smart Turing access to \mathcal{UP}.


title: Finding Community Structure in Mega-scale Social Networks

abstract: Community analysis algorithm proposed by Clauset, Newman, and Moore (CNM algorithm) finds community structure in social networks. Unfortunately, CNM algorithm does not scale well and its use is practically limited to networks whose sizes are up to 500,000 nodes. The paper identifies that this inefficiency is caused from merging communities in unbalanced manner. The paper introduces three kinds of metrics (consolidation ratio) to control the process of community analysis trying to balance the sizes of the communities being merged. Three flavors of CNM algorithms are built incorporating those metrics. The proposed techniques are tested using data sets obtained from existing social networking service that hosts 5.5 million users. All the methods exhibit dramatic improvement of execution efficiency in comparison with the original CNM algorithm and shows high scalability. The fastest method processes a network with 1 million nodes in 5 minutes and a network with 4 million nodes in 35 minutes, respectively. Another one processes a network with 500,000 nodes in 50 minutes (7 times faster than the original algorithm), finds community structures that has improved modularity, and scales to a network with 5.5 million.


title: Parameterized Algorithms for Directed Maximum Leaf Problems

abstract: We prove that finding a rooted subtree with at least $k$ leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family $\cal L$ that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in $\cal L$. Our algorithms are based on the following combinatorial result which can be viewed as a generalization of many results for a `spanning tree with many leaves' in the undirected case, and which is interesting on its own: If a digraph $D\in \cal L$ of order $n$ with minimum in-degree at least 3 contains a rooted spanning tree, then $D$ contains one with at least $(n/2)^{1/5}-1$ leaves.


title: Permutation Decoding and the Stopping Redundancy Hierarchy of Linear Block Codes

abstract: We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.


title: The Gaussian multiple access wire-tap channel: wireless secrecy and cooperative jamming

abstract: We consider the General Gaussian Multiple Access Wire-Tap Channel (GGMAC-WT). In this scenario, multiple users communicate with an intended receiver in the presence of an intelligent and informed eavesdropper. We define two suitable secrecy measures, termed individual and collective, to reflect the confidence in the system for this multi-access environment. We determine achievable rates such that secrecy to some pre-determined degree can be maintained, using Gaussian codebooks. We also find outer bounds for the case when the eavesdropper receives a degraded version of the intended receiver's signal. In the degraded case, Gaussian codewords are shown to achieve the sum capacity for collective constraints. In addition, a TDMA scheme is shown to also achieve sum capacity for both sets of constraints. Numerical results showing the new rate region are presented and compared with the capacity region of the Gaussian Multiple-Access Channel (GMAC) with no secrecy constraints. We then find the secrecy sum-rate maximizing power allocations for the transmitters, and show that a cooperative jamming scheme can be used to increase achievable rates in this scenario.


title: On Random Network Coding for Multicast

abstract: Random linear network coding is a particularly decentralized approach to the multicast problem. Use of random network codes introduces a non-zero probability however that some sinks will not be able to successfully decode the required sources. One of the main theoretical motivations for random network codes stems from the lower bound on the probability of successful decoding reported by Ho et. al. (2003). This result demonstrates that all sinks in a linearly solvable network can successfully decode all sources provided that the random code field size is large enough. This paper develops a new bound on the probability of successful decoding.


title: The DFAs of Finitely Different Languages

abstract: Two languages are "finitely different" if their symmetric difference is finite. We consider the DFAs of finitely different regular languages and find major structural similarities. We proceed to consider the smallest DFAs that recognize a language finitely different from some given DFA. Such "f-minimal" DFAs are not unique, and this non-uniqueness is characterized. Finally, we offer a solution to the minimization problem of finding such f-minimal DFAs.


title: Nash equilibria in Voronoi games on graphs

abstract: In this paper we study a game where every player is to choose a vertex (facility) in a given undirected graph. All vertices (customers) are then assigned to closest facilities and a player's payoff is the number of customers assigned to it. We show that deciding the existence of a Nash equilibrium for a given graph is NP-hard which to our knowledge is the first result of this kind for a zero-sum game. We also introduce a new measure, the social cost discrepancy, defined as the ratio of the costs between the worst and the best Nash equilibria. We show that the social cost discrepancy in our game is Omega(sqrt(n/k)) and O(sqrt(kn)), where n is the number of vertices and k the number of players.


title: On the possibility of making the complete computer model of a human brain

abstract: The development of the algorithm of a neural network building by the corresponding parts of a DNA code is discussed.


title: A probabilistic analysis of a leader election algorithm

abstract: A {\em leader election} algorithm is an elimination process that divides recursively into tow subgroups an initial group of n items, eliminates one subgroup and continues the procedure until a subgroup is of size 1. In this paper the biased case is analyzed. We are interested in the {\em cost} of the algorithm, i.e. the number of operations needed until the algorithm stops. Using a probabilistic approach, the asymptotic behavior of the algorithm is shown to be related to the behavior of a hitting time of two random sequences on [0,1].


title: An Efficient Algorithm to Recognize Locally Equivalent Graphs in Non-Binary Case

abstract: Let $v$ be a vertex of a graph $G$. By the local complementation of $G$ at $v$ we mean to complement the subgraph induced by the neighbors of $v$. This operator can be generalized as follows. Assume that, each edge of $G$ has a label in the finite field $\mathbf{F}_q$. Let $(g_{ij})$ be set of labels ($g_{ij}$ is the label of edge $ij$). We define two types of operators. For the first one, let $v$ be a vertex of $G$ and $a\in \mathbf{F}_q$, and obtain the graph with labels $g'_{ij}=g_{ij}+ag_{vi}g_{vj}$. For the second, if $0\neq b\in \mathbf{F}_q$ the resulted graph is a graph with labels $g''_{vi}=bg_{vi}$ and $g''_{ij}=g_{ij}$, for $i,j$ unequal to $v$. It is clear that if the field is binary, the operators are just local complementations that we described. The problem of whether two graphs are equivalent under local complementations has been studied, \cite{bouchalg}. Here we consider the general case and assuming that $q$ is odd, present the first known efficient algorithm to verify whether two graphs are locally equivalent or not.


title: Exploring k-Colorability

abstract: An introductory paper to the graph k-colorability problem.


title: Redundancy-Related Bounds on Generalized Huffman Codes

abstract: This paper presents new lower and upper bounds for the compression rate of binary prefix codes optimized over memoryless sources according to various nonlinear codeword length objectives. Like the most well-known redundancy bounds for minimum average redundancy coding - Huffman coding - these are in terms of a form of entropy and/or the probability of an input symbol, often the most probable one. The bounds here, some of which are tight, improve on known bounds of the form L in [H,H+1), where H is some form of entropy in bits (or, in the case of redundancy objectives, 0) and L is the length objective, also in bits. The objectives explored here include exponential-average length, maximum pointwise redundancy, and exponential-average pointwise redundancy (also called dth exponential redundancy). The first of these relates to various problems involving queueing, uncertainty, and lossless communications; the second relates to problems involving Shannon coding and universal modeling. For these two objectives we also explore the related problem of the necessary and sufficient conditions for the shortest codeword of a code being a specific length.


title: A local balance property of episturmian words

abstract: We prove that episturmian words and Arnoux-Rauzy sequences can be characterized using a local balance property. We also give a new characterization of epistandard words and show that the set of finite words that are not factors of an episturmian word is not context-free.


title: Sudo-Lyndon

abstract: Based on Lyndon words, a new Sudoku-like puzzle is presented and some relative theoretical questions are proposed.


title: Noise Limited Computational Speed

abstract: In modern transistor based logic gates, the impact of noise on computation has become increasingly relevant since the voltage scaling strategy, aimed at decreasing the dissipated power, has increased the probability of error due to the reduced switching threshold voltages. In this paper we discuss the role of noise in a two state model that mimic the dynamics of standard logic gates and show that the presence of the noise sets a fundamental limit to the computing speed. An optimal idle time interval that minimizes the error probability, is derived.


title: Entropy vectors and network codes

abstract: We consider a network multicast example that relates the solvability of the multicast problem with the existence of an entropy function. As a result, we provide an alternative approach to the proving of the insufficiency of linear (and abelian) network codes and demonstrate the utility of non-Shannon inequalities to tighten outer bounds on network coding capacity regions.


title: Group characterizable entropy functions

abstract: This paper studies properties of entropy functions that are induced by groups and subgroups. We showed that many information theoretic properties of those group induced entropy functions also have corresponding group theoretic interpretations. Then we propose an extension method to find outer bound for these group induced entropy functions.


title: Towards a New ODE Solver Based on Cartan's Equivalence Method

abstract: The aim of the present paper is to propose an algorithm for a new ODE--solver which should improve the abilities of current solvers to handle second order differential equations. The paper provides also a theoretical result revealing the relationship between the change of coordinates, that maps the generic equation to a given target equation, and the symmetry $\D$-groupoid of this target.


title: Comments on "Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks''

abstract: Min, Veeravalli, and Barlas proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments. We show on a very simple example that the proposed approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal scheduling for any instance, once the number of installments per load is given. Finally, we formally prove that under a linear cost model, as in the original paper, an optimal schedule has an infinite number of installments. Such a cost model can therefore not be sed to design practical multi-installment strategies.


title: The Haar Wavelet Transform of a Dendrogram: Additional Notes

abstract: We consider the wavelet transform of a finite, rooted, node-ranked, $p$-way tree, focusing on the case of binary ($p = 2$) trees. We study a Haar wavelet transform on this tree. Wavelet transforms allow for multiresolution analysis through translation and dilation of a wavelet function. We explore how this works in our tree context.


title: Distributed Decision Through Self-Synchronizing Sensor Networks in the Presence of Propagation Delays and Nonreciprocal Channels

abstract: In this paper we propose and analyze a distributed algorithm for achieving globally optimal decisions, either estimation or detection, through a self-synchronization mechanism among linearly coupled integrators initialized with local measurements. We model the interaction among the nodes as a directed graph with weights dependent on the radio interface and we pose special attention to the effect of the propagation delays occurring in the exchange of data among sensors, as a function of the network geometry. We derive necessary and sufficient conditions for the proposed system to reach a consensus on globally optimal decision statistics. One of the major results proved in this work is that a consensus is achieved for any bounded delay condition if and only if the directed graph is quasi-strongly connected. We also provide a closed form expression for the global consensus, showing that the effect of delays is, in general, to introduce a bias in the final decision. The closed form expression is also useful to modify the consensus mechanism in order to get rid of the bias with minimum extra complexity.


title: Feasible reactivity in a synchronous pi-calculus

abstract: Reactivity is an essential property of a synchronous program. Informally, it guarantees that at each instant the program fed with an input will `react' producing an output. In the present work, we consider a refined property that we call ` feasible reactivity'. Beyond reactivity, this property guarantees that at each instant both the size of the program and its reaction time are bounded by a polynomial in the size of the parameters at the beginning of the computation and the size of the largest input. We propose a method to annotate programs and we develop related static analysis techniques that guarantee feasible reactivity for programs expressed in the S-pi-calculus. The latter is a synchronous version of the pi-calculus based on the SL synchronous programming model.


title: A Practical Approach to Lossy Joint Source-Channel Coding

abstract: This work is devoted to practical joint source channel coding. Although the proposed approach has more general scope, for the sake of clarity we focus on a specific application example, namely, the transmission of digital images over noisy binary-input output-symmetric channels. The basic building blocks of most state-of the art source coders are: 1) a linear transformation; 2) scalar quantization of the transform coefficients; 3) probability modeling of the sequence of quantization indices; 4) an entropy coding stage. We identify the weakness of the conventional separated source-channel coding approach in the catastrophic behavior of the entropy coding stage. Hence, we replace this stage with linear coding, that maps directly the sequence of redundant quantizer output symbols into a channel codeword. We show that this approach does not entail any loss of optimality in the asymptotic regime of large block length. However, in the practical regime of finite block length and low decoding complexity our approach yields very significant improvements. Furthermore, our scheme allows to retain the transform, quantization and probability modeling of current state-of the art source coders, that are carefully matched to the features of specific classes of sources. In our working example, we make use of ``bit-planes'' and ``contexts'' model defined by the JPEG2000 standard and we re-interpret the underlying probability model as a sequence of conditionally Markov sources. The Markov structure allows to derive a simple successive coding and decoding scheme, where the latter is based on iterative Belief Propagation. We provide a construction example of the proposed scheme based on punctured Turbo Codes and we demonstrate the gain over a conventional separated scheme by running extensive numerical experiments on test images.


title: What is needed to exploit knowledge of primary transmissions?

abstract: Recently, Tarokh and others have raised the possibility that a cognitive radio might know the interference signal being transmitted by a strong primary user in a non-causal way, and use this knowledge to increase its data rates. However, there is a subtle difference between knowing the signal transmitted by the primary and the actual interference at our receiver since there is a wireless channel between these two points. We show that even an unknown phase results in a substantial decrease in the data rates that can be achieved, and thus there is a need to feedback interference channel estimates to the cognitive transmitter. We then consider the case of fading channels. We derive an upper bound on the rate for given outage error probability for faded dirt. We give a scheme that uses appropriate "training" to obtain such estimates and quantify this scheme's required overhead as a function of the relevant coherence time and interference power.


title: Logic Programming with Satisfiability

abstract: This paper presents a Prolog interface to the MiniSat satisfiability solver. Logic program- ming with satisfiability combines the strengths of the two paradigms: logic programming for encoding search problems into satisfiability on the one hand and efficient SAT solving on the other. This synergy between these two exposes a programming paradigm which we propose here as a logic programming pearl. To illustrate logic programming with SAT solving we give an example Prolog program which solves instances of Partial MAXSAT.


title: Tradeoff between decoding complexity and rate for codes on graphs

abstract: We consider transmission over a general memoryless channel, with bounded decoding complexity per bit under message passing decoding. We show that the achievable rate is bounded below capacity if there is a finite success in the decoding in a specified number of operations per bit at the decoder for some codes on graphs. These codes include LDPC and LDGM codes. Good performance with low decoding complexity suggests strong local structures in the graphs of these codes, which are detrimental to the code rate asymptotically. The proof method leads to an interesting necessary condition on the code structures which could achieve capacity with bounded decoding complexity. We also show that if a code sequence achieves a rate epsilon close to the channel capacity, the decoding complexity scales at least as O(log(1/epsilon).


title: Dynamic Random Geometric Graphs

abstract: In this work we introduce Dynamic Random Geometric Graphs as a basic rough model for mobile wireless sensor networks, where communication distances are set to the known threshold for connectivity of static random geometric graphs. We provide precise asymptotic results for the expected length of the connectivity and disconnectivity periods of the network. We believe the formal tools developed in this work could be of use in future studies in more concrete settings. In addition, for static random geometric graphs at the threshold for connectivity, we provide asymptotic expressions on the probability of existence of components according to their sizes.


title: Firebird Database Backup by Serialized Database Table Dump

abstract: This paper presents a simple data dump and load utility for Firebird databases which mimics mysqldump in MySQL. This utility, fb_dump and fb_load, for dumping and loading respectively, retrieves each database table using kinterbasdb and serializes the data using marshal module. This utility has two advantages over the standard Firebird database backup utility, gbak. Firstly, it is able to backup and restore single database tables which might help to recover corrupted databases. Secondly, the output is in text-coded format (from marshal module) making it more resilient than a compressed text backup, as in the case of using gbak.


title: A First Step Towards Automatically Building Network Representations

abstract: To fully harness Grids, users or middlewares must have some knowledge on the topology of the platform interconnection network. As such knowledge is usually not available, one must uses tools which automatically build a topological network model through some measurements. In this article, we define a methodology to assess the quality of these network model building tools, and we apply this methodology to representatives of the main classes of model builders and to two new algorithms. We show that none of the main existing techniques build models that enable to accurately predict the running time of simple application kernels for actual platforms. However some of the new algorithms we propose give excellent results in a wide range of situations.


title: Properties of Rank Metric Codes

abstract: This paper investigates general properties of codes with the rank metric. We first investigate asymptotic packing properties of rank metric codes. Then, we study sphere covering properties of rank metric codes, derive bounds on their parameters, and investigate their asymptotic covering properties. Finally, we establish several identities that relate the rank weight distribution of a linear code to that of its dual code. One of our identities is the counterpart of the MacWilliams identity for the Hamming metric, and it has a different form from the identity by Delsarte.


title: A Local Algorithm for Finding Dense Subgraphs

abstract: We present a local algorithm for finding dense subgraphs of bipartite graphs, according to the definition of density proposed by Kannan and Vinay. Our algorithm takes as input a bipartite graph with a specified starting vertex, and attempts to find a dense subgraph near that vertex. We prove that for any subgraph S with k vertices and density theta, there are a significant number of starting vertices within S for which our algorithm produces a subgraph S' with density theta / O(log n) on at most O(D k^2) vertices, where D is the maximum degree. The running time of the algorithm is O(D k^2), independent of the number of vertices in the graph.


title: The Hadwiger Number of Jordan Regions is Unbounded

abstract: We show that for every n > 0 there is a planar topological disk A_0 and n translates A_1, A_2, ..., A_n of A_0 such that the interiors of A_0, ... A_n are pairwise disjoint, but with each A_i touching A_0 for 1 <= i <= n.


title: Sparse geometric graphs with small dilation

abstract: Given a set S of n points in R^D, and an integer k such that 0 <= k < n, we show that a geometric graph with vertex set S, at most n - 1 + k edges, maximum degree five, and dilation O(n / (k+1)) can be computed in time O(n log n). For any k, we also construct planar n-point sets for which any geometric graph with n-1+k edges has dilation Omega(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.


title: Random Sentences from a Generalized Phrase-Structure Grammar Interpreter

abstract: In numerous domains in cognitive science it is often useful to have a source for randomly generated corpora. These corpora may serve as a foundation for artificial stimuli in a learning experiment (e.g., Ellefson & Christiansen, 2000), or as input into computational models (e.g., Christiansen & Dale, 2001). The following compact and general C program interprets a phrase-structure grammar specified in a text file. It follows parameters set at a Unix or Unix-based command-line and generates a corpus of random sentences from that grammar.


title: Invariant template matching in systems with spatiotemporal coding: a vote for instability

abstract: We consider the design of a pattern recognition that matches templates to images, both of which are spatially sampled and encoded as temporal sequences. The image is subject to a combination of various perturbations. These include ones that can be modeled as parameterized uncertainties such as image blur, luminance, translation, and rotation as well as unmodeled ones. Biological and neural systems require that these perturbations be processed through a minimal number of channels by simple adaptation mechanisms. We found that the most suitable mathematical framework to meet this requirement is that of weakly attracting sets. This framework provides us with a normative and unifying solution to the pattern recognition problem. We analyze the consequences of its explicit implementation in neural systems. Several properties inherent to the systems designed in accordance with our normative mathematical argument coincide with known empirical facts. This is illustrated in mental rotation, visual search and blur/intensity adaptation. We demonstrate how our results can be applied to a range of practical problems in template matching and pattern recognition.


title: Improving Prolog programs: Refactoring for Prolog

abstract: Refactoring is an established technique from the object-oriented (OO) programming community to restructure code: it aims at improving software readability, maintainability and extensibility. Although refactoring is not tied to the OO-paradigm in particular, its ideas have not been applied to Logic Programming until now. This paper applies the ideas of refactoring to Prolog programs. A catalogue is presented listing refactorings classified according to scope. Some of the refactorings have been adapted from the OO-paradigm, while others have been specifically designed for Prolog. The discrepancy between intended and operational semantics in Prolog is also addressed by some of the refactorings. In addition, ViPReSS, a semi-automatic refactoring browser, is discussed and the experience with applying ViPReSS to a large Prolog legacy system is reported. The main conclusion is that refactoring is both a viable technique in Prolog and a rather desirable one.


title: Performance of Ultra-Wideband Impulse Radio in Presence of Impulsive Interference

abstract: We analyze the performance of coherent impulsive-radio (IR) ultra-wideband (UWB) channel in presence of the interference generated by concurrent transmissions of the systems with the same impulsive radio. We derive a novel algorithm, using Monte-Carlo method, to calculate a lower bound on the rate that can be achieved using maximum-likelihood estimator. Using this bound we show that such a channel is very robust to interference, in contrast to the nearest-neighbor detector.


title: Social Behaviours Applied to P2P Systems: An efficient Algorithm for Resource Organisation

abstract: P2P systems are a great solution to the problem of distributing resources. The main issue of P2P networks is that searching and retrieving resources shared by peers is usually expensive and does not take into account similarities among peers. In this paper we present preliminary simulations of PROSA, a novel algorithm for P2P network structuring, inspired by social behaviours. Peers in PROSA self--organise in social groups of similar peers, called ``semantic--groups'', depending on the resources they are sharing. Such a network smoothly evolves to a small--world graph, where queries for resources are efficiently and effectively routed.


title: Protection of DVB Systems by Trusted Computing

abstract: We describe a concept to employ Trusted Computing technology to secure Conditional Access Systems (CAS) for DVB. Central is the embedding of a trusted platform module (TPM) into the set-top-box or residential home gateway. Various deployment scenarios exhibit possibilities of charging co-operation with mobile network operators (MNO), or other payment providers.


title: An Upper Bound on the Average Size of Silhouettes

abstract: It is a widely observed phenomenon in computer graphics that the size of the silhouette of a polyhedron is much smaller than the size of the whole polyhedron. This paper provides, for the first time, theoretical evidence supporting this for a large class of objects, namely for polyhedra that approximate surfaces in some reasonable way; the surfaces may be non-convex and non-differentiable and they may have boundaries. We prove that such polyhedra have silhouettes of expected size $O(\sqrt{n})$ where the average is taken over all points of view and n is the complexity of the polyhedron.


title: Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation

abstract: In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. Since the randomized query complexity of global optimization over [1:n]^d is Theta (n^{d}), the randomized query model over [1:n]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the query model; the deterministic complexity of this problem is Theta (n^{d-1}).


title: Mapping the Object-Role Modeling language ORM2 into Description Logic language DLRifd

abstract: In recent years, several efforts have been made to enhance conceptual data modelling with automated reasoning to improve the model's quality and derive implicit information. One approach to achieve this in implementations, is to constrain the language. Advances in Description Logics can help choosing the right language to have greatest expressiveness yet to remain within the decidable fragment of first order logic to realise a workable implementation with good performance using DL reasoners. The best fit DL language appears to be the ExpTime-complete DLRifd. To illustrate trade-offs and highlight features of the modelling languages, we present a precise transformation of the mappable features of the very expressive (undecidable) ORM/ORM2 conceptual data modelling languages to exactly DLRifd. Although not all ORM2 features can be mapped, this is an interesting fragment because it has been shown that DLRifd can also encode UML Class Diagrams and EER, and therefore can foster interoperation between conceptual data models and research into ontological aspects of the modelling languages.


title: Aperture-Angle and Hausdorff-Approximation of Convex Figures

abstract: The aperture angle alpha(x, Q) of a point x not in Q in the plane with respect to a convex polygon Q is the angle of the smallest cone with apex x that contains Q. The aperture angle approximation error of a compact convex set C in the plane with respect to an inscribed convex polygon Q of C is the minimum aperture angle of any x in C Q with respect to Q. We show that for any compact convex set C in the plane and any k > 2, there is an inscribed convex k-gon Q of C with aperture angle approximation error (1 - 2/(k+1)) pi. This bound is optimal, and settles a conjecture by Fekete from the early 1990s. The same proof technique can be used to prove a conjecture by Brass: If a polygon P admits no approximation by a sub-k-gon (the convex hull of k vertices of P) with Hausdorff distance sigma, but all subpolygons of P (the convex hull of some vertices of P) admit such an approximation, then P is a (k+1)-gon. This implies the following result: For any k > 2 and any convex polygon P of perimeter at most 1 there is a sub-k-gon Q of P such that the Hausdorff-distance of P and Q is at most 1/(k+1) * sin(pi/(k+1)).


title: Observable Graphs

abstract: An edge-colored directed graph is \emph{observable} if an agent that moves along its edges is able to determine his position in the graph after a sufficiently long observation of the edge colors. When the agent is able to determine his position only from time to time, the graph is said to be \emph{partly observable}. Observability in graphs is desirable in situations where autonomous agents are moving on a network and one wants to localize them (or the agent wants to localize himself) with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to observable discrete event systems and to local automata. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. From this it follows that it may be necessary for an agent to pass through the same node several times before he is finally able to determine his position in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete.


title: A Note on the Periodicity and the Output Rate of Bit Search Type Generators

abstract: We investigate the bit-search type irregular decimation algorithms that are used within LFSR-based stream ciphers. In particular, we concentrate on BSG and ABSG, and consider two different setups for the analysis. In the first case, the input is assumed to be a m-sequence; we show that all possible output sequences can be classified into two sets, each of which is characterized by the equivalence of their elements up to shifts. Furthermore, we prove that the cardinality of each of these sets is equal to the period of one of its elements and subsequently derive the first known bounds on the expected output period (assuming that no subperiods exist). In the second setup, we work in a probabilistic framework and assume that the input sequence is evenly distributed (i.e., independent identically distributed Bernoulli process with probability 1/2). Under these assumptions, we derive closed-form expressions for the distribution of the output length and the output rate, which is shown to be asymptotically Gaussian-distributed and concentrated around the mean with exponential tightness.


title: Secure Broadcasting

abstract: Wyner's wiretap channel is extended to parallel broadcast channels and fading channels with multiple receivers. In the first part of the paper, we consider the setup of parallel broadcast channels with one sender, multiple intended receivers, and one eavesdropper. We study the situations where the sender broadcasts either a common message or independent messages to the intended receivers. We derive upper and lower bounds on the common-message-secrecy capacity, which coincide when the users are reversely degraded. For the case of independent messages we establish the secrecy sum-capacity when the users are reversely degraded. In the second part of the paper we apply our results to fading channels: perfect channel state information of all intended receivers is known globally, whereas the eavesdropper channel is known only to her. For the common message case, a somewhat surprising result is proven: a positive rate can be achieved independently of the number of intended receivers. For independent messages, an opportunistic transmission scheme is presented that achieves the secrecy sum-capacity in the limit of large number of receivers. Our results are stated for a fast fading channel model. Extensions to the block fading model are also discussed.


title: Authentication via wireless networks

abstract: Personal authentication is an important process we encounter almost every day; when we are logging on a computer, entering a company where we work, or a restricted area, when we are using our plastic credit cards to pay for a service or to complete some other financial transaction, etc. In each of these processes of personal authentication some kind of magnetic or optical token is required. But by using novel technologies like mobile computing and wireless networking, it is possible to avoid carrying multitude of ID cards or remembering a number of PIN codes. Article shows how to efficiently authenticate users via Personal Area Networks (PAN) like Bluetooth or IrDA using commonplace AES (Rijndel) or MD5 encryption. This method can be implemented on many types of mobile devices like Pocket PC PDA with Windows CE (Windows Mobile 2003) real-time operating system, or any other customized OS, so we will explain all components and key features of such basic system.


title: A note on using finite non-abelian $p$-groups in the MOR cryptosystem

abstract: The MOR cryptosystem is a natural generalization of the El-Gamal cryptosystem to non-abelian groups. Using a $p$-group, a cryptosystem was built by this author in 'A simple generalization of El-Gamal cryptosystem to non-abelian groups'. It seems reasonable to assume the cryptosystem is as secure as the El-Gamal cryptosystem over finite fields. A natural question arises can one make a better cryptosystem using $p$-groups? In this paper we show that the answer is no.


title: Overcoming Hierarchical Difficulty by Hill-Climbing the Building Block Structure

abstract: The Building Block Hypothesis suggests that Genetic Algorithms (GAs) are well-suited for hierarchical problems, where efficient solving requires proper problem decomposition and assembly of solution from sub-solution with strong non-linear interdependencies. The paper proposes a hill-climber operating over the building block (BB) space that can efficiently address hierarchical problems. The new Building Block Hill-Climber (BBHC) uses past hill-climb experience to extract BB information and adapts its neighborhood structure accordingly. The perpetual adaptation of the neighborhood structure allows the method to climb the hierarchical structure solving successively the hierarchical levels. It is expected that for fully non deceptive hierarchical BB structures the BBHC can solve hierarchical problems in linearithmic time. Empirical results confirm that the proposed method scales almost linearly with the problem size thus clearly outperforms population based recombinative methods.


title: Avoiding bias in cards cryptography

abstract: We outline the need for stricter requirements for unconditionally secure cryptographic protocols inspired by the Russian Cards problem. A new requirement CA4 is proposed that checks for bias in single card occurrence in announcements consisting of alternatives for players' holdings of cards. This requirement CA4 is shown to be equivalent to an alternative requirement CA5. All announcements found to satisfy CA4 are 2-designs. We also show that all binary designs are 3-designs. Instead of avoiding bias in announcements produced by such protocols, one may as well apply unbiased protocols such that patterns in announcements become meaningless. We gave two examples of such protocols for card deal parameters (3,3,1), i.e. two of the players hold three cards, and the remaining player, playing the role of eavesdropper, holds a single card.


title: A Sum-Product Model as a Physical Basis for Shadow Fading

abstract: Shadow fading (slow fading) effects play a central role in mobile communication system design and analysis. Experimental evidence indicates that shadow fading exhibits log-normal power distribution almost universally, and yet it is still not well understood what causes this. In this paper, we propose a versatile sum-product signal model as a physical basis for shadow fading. Simulation results imply that the proposed model results in log-normally distributed local mean power regardless of the distributions of the interactions in the radio channel, and hence it is capable of explaining the log-normality in a wide variety of propagation scenarios. The sum-product model also includes as its special cases the conventional product model as well as the recently proposed sum model, and improves upon these by: a) being applicable in both global and local distance scales; b) being more plausible from physical point of view; c) providing better goodness-of-fit to log-normal distribution than either of these models.


title: Discrete Memoryless Interference and Broadcast Channels with Confidential Messages: Secrecy Rate Regions

abstract: We study information-theoretic security for discrete memoryless interference and broadcast channels with independent confidential messages sent to two receivers. Confidential messages are transmitted to their respective receivers with information-theoretic secrecy. That is, each receiver is kept in total ignorance with respect to the message intended for the other receiver. The secrecy level is measured by the equivocation rate at the eavesdropping receiver. In this paper, we present inner and outer bounds on secrecy capacity regions for these two communication systems. The derived outer bounds have an identical mutual information expression that applies to both channel models. The difference is in the input distributions over which the expression is optimized. The inner bound rate regions are achieved by random binning techniques. For the broadcast channel, a double-binning coding scheme allows for both joint encoding and preserving of confidentiality. Furthermore, we show that, for a special case of the interference channel, referred to as the switch channel, the two bound bounds meet. Finally, we describe several transmission schemes for Gaussian interference channels and derive their achievable rate regions while ensuring mutual information-theoretic secrecy. An encoding scheme in which transmitters dedicate some of their power to create artificial noise is proposed and shown to outperform both time-sharing and simple multiplexed transmission of the confidential messages.


title: A Class of Multi-Channel Cosine Modulated IIR Filter Banks

abstract: This paper presents a class of multi-channel cosine-modulated filter banks satisfying the perfect reconstruction (PR) property using an IIR prototype filter. By imposing a suitable structure on the polyphase filter coefficients, we show that it is possible to greatly simplify the PR condition, while preserving the causality and stability of the system. We derive closed-form expressions for the synthesis filters and also study the numerical stability of the filter bank using frame theoretic bounds. Further, we show that it is possible to implement this filter bank with much lower number of arithmetic operations when compared to FIR filter banks with comparable performance. The filter bank's modular structure also lends itself to efficient VLSI implementation.


title: An identity of Chernoff bounds with an interpretation in statistical physics and applications in information theory

abstract: An identity between two versions of the Chernoff bound on the probability a certain large deviations event, is established. This identity has an interpretation in statistical physics, namely, an isothermal equilibrium of a composite system that consists of multiple subsystems of particles. Several information--theoretic application examples, where the analysis of this large deviations probability naturally arises, are then described from the viewpoint of this statistical mechanical interpretation. This results in several relationships between information theory and statistical physics, which we hope, the reader will find insightful.


title: Paging and Registration in Cellular Networks: Jointly Optimal Policies and an Iterative Algorithm

abstract: This paper explores optimization of paging and registration policies in cellular networks. Motion is modeled as a discrete-time Markov process, and minimization of the discounted, infinite-horizon average cost is addressed. The structure of jointly optimal paging and registration policies is investigated through the use of dynamic programming for partially observed Markov processes. It is shown that there exist policies with a certain simple form that are jointly optimal, though the dynamic programming approach does not directly provide an efficient method to find the policies. An iterative algorithm for policies with the simple form is proposed and investigated. The algorithm alternates between paging policy optimization and registration policy optimization. It finds a pair of individually optimal policies, but an example is given showing that the policies need not be jointly optimal. Majorization theory and Riesz's rearrangement inequality are used to show that jointly optimal paging and registration policies are given for symmetric or Gaussian random walk models by the nearest-location-first paging policy and distance threshold registration policies.


title: Exploring the academic invisible web

abstract: Purpose: To provide a critical review of Bergman's 2001 study on the Deep Web. In addition, we bring a new concept into the discussion, the Academic Invisible Web (AIW). We define the Academic Invisible Web as consisting of all databases and collections relevant to academia but not searchable by the general-purpose internet search engines. Indexing this part of the Invisible Web is central to scientific search engines. We provide an overview of approaches followed thus far. Design/methodology/approach: Discussion of measures and calculations, estimation based on informetric laws. Literature review on approaches for uncovering information from the Invisible Web. Findings: Bergman's size estimate of the Invisible Web is highly questionable. We demonstrate some major errors in the conceptual design of the Bergman paper. A new (raw) size estimate is given. Research limitations/implications: The precision of our estimate is limited due to a small sample size and lack of reliable data. Practical implications: We can show that no single library alone will be able to index the Academic Invisible Web. We suggest collaboration to accomplish this task. Originality/value: Provides library managers and those interested in developing academic search engines with data on the size and attributes of the Academic Invisible Web.


title: A Union Bound Approximation for Rapid Performance Evaluation of Punctured Turbo Codes

abstract: In this paper, we present a simple technique to approximate the performance union bound of a punctured turbo code. The bound approximation exploits only those terms of the transfer function that have a major impact on the overall performance. We revisit the structure of the constituent convolutional encoder and we develop a rapid method to calculate the most significant terms of the transfer function of a turbo encoder. We demonstrate that, for a large interleaver size, this approximation is very accurate. Furthermore, we apply our proposed method to a family of punctured turbo codes, which we call pseudo-randomly punctured codes. We conclude by emphasizing the benefits of our approach compared to those employed previously. We also highlight the advantages of pseudo-random puncturing over other puncturing schemes.


title: The Simplest Solution to an Underdetermined System of Linear Equations

abstract: Consider a d*n matrix A, with d<n. The problem of solving for x in y=Ax is underdetermined, and has infinitely many solutions (if there are any). Given y, the minimum Kolmogorov complexity solution (MKCS) of the input x is defined to be an input z (out of many) with minimum Kolmogorov-complexity that satisfies y=Az. One expects that if the actual input is simple enough, then MKCS will recover the input exactly. This paper presents a preliminary study of the existence and value of the complexity level up to which such a complexity-based recovery is possible. It is shown that for the set of all d*n binary matrices (with entries 0 or 1 and d<n), MKCS exactly recovers the input for an overwhelming fraction of the matrices provided the Kolmogorov complexity of the input is O(d). A weak converse that is loose by a log n factor is also established for this case. Finally, we investigate the difficulty of finding a matrix that has the property of recovering inputs with complexity of O(d) using MKCS.


title: Wild, Wild Wikis: A way forward

abstract: Wikis can be considered as public domain knowledge sharing system. They provide opportunity for those who may not have the privilege to publish their thoughts through the traditional methods. They are one of the fastest growing systems of online encyclopaedia. In this study, we consider the importance of wikis as a way of creating, sharing and improving public knowledge. We identify some of the problems associated with wikis to include, (a) identification of the identities of information and its creator (b) accuracy of information (c) justification of the credibility of authors (d) vandalism of quality of information (e) weak control over the contents. A solution to some of these problems is sought through the use of an annotation model. The model assumes that contributions in wikis can be seen as annotation to the initial document. It proposed a systematic control of contributors and contributions to the initiative and the keeping of records of what existed and what was done to initial documents. We believe that with this model, analysis can be done on the progress of wiki initiatives. We assumed that using this model, wikis can be better used for creation and sharing of knowledge for public use.