OpenRaiser/Intern-Atlas huggingface dataset:
The Partition Bound for Classical Communication Complexity and Query Complexity
Venue: arXiv cs.CC 2009
Year: 2009

We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle/corruption bound and the γ_2/generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate polynomial degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than polynomial degree and classical adversary bounds.
Preprocessing of Min Ones Problems: A Dichotomy
Venue: arXiv cs.CC 2009
Year: 2009

A parameterized problem consists of a classical problem and an additional component, the so-called parameter. This point of view allows a formal definition of preprocessing: Given a parameterized instance (I,k), a polynomial kernelization computes an equivalent instance (I',k') of size and parameter bounded by a polynomial in k. We give a complete classification of Min Ones Constraint Satisfaction problems, i.e., Min Ones SAT(Γ), with respect to admitting or not admitting a polynomial kernelization (unless NP \subseteq coNP/poly). For this we introduce the notion of mergeability. If all relations of the constraint language Γare mergeable, then a new variant of sunflower kernelization applies, based on non-zero-closed cores. We obtain a kernel with O(k^{d+1}) variables and polynomial total size, where d is the maximum arity of a constraint in Γ, comparing nicely with the bound of O(k^{d-1}) vertices for the less general and arguably simpler d-Hitting Set problem. Otherwise, any relation in Γthat is not mergeable permits us to construct a log-cost selection formula, i.e., an n-ary selection formula with O(log n) true local variables. From this we can construct our lower bound using recent results by Bodlaender et al. as well as Fortnow and Santhanam, proving that there is no polynomial kernelization, unless NP \subseteq coNP/poly and the polynomial hierarchy collapses to the third level.
Automata and Reduced Words in the Free Group
Venue: arXiv cs.FL 2009
Year: 2009

We consider some questions about formal languages that arise when inverses of letters, words and languages are defined. The reduced representation of a language over the free monoid is its unique equivalent representation in the free group. We show that the class of regular languages is closed under taking the reduced representation, while the class of context-free languages is not. We also give an upper bound on the state complexity of the reduced representation of a regular language, and prove upper and lower bounds on the length of the shortest reducible string in a regular language. Finally we show that the set of all words which are equivalent to the words in a regular language can be nonregular, and that regular languages are not closed under taking a generalized form of the reduced representation.
SPECI, a simulation tool exploring cloud-scale data centres
Venue: arXiv cs.DC 2009
Year: 2009

There is a rapid increase in the size of data centres (DCs) used to provide cloud computing services. It is commonly agreed that not all properties in the middleware that manages DCs will scale linearly with the number of components. Further, "normal failure" complicates the assessment of the per-formance of a DC. However, unlike in other engineering domains, there are no well established tools that allow the prediction of the performance and behav-iour of future generations of DCs. SPECI, Simulation Program for Elastic Cloud Infrastructures, is a simulation tool which allows exploration of aspects of scaling as well as performance properties of future DCs.
Throughput in Asynchronous Networks
Venue: arXiv cs.NI 2009
Year: 2009

We introduce a new, "worst-case" model for an asynchronous communication network and investigate the simplest (yet central) task in this model, namely the feasibility of end-to-end routing. Motivated by the question of how successful a protocol can hope to perform in a network whose reliability is guaranteed by as few assumptions as possible, we combine the main "unreliability" features encountered in network models in the literature, allowing our model to exhibit all of these characteristics simultaneously. In particular, our model captures networks that exhibit the following properties: 1) On-line; 2) Dynamic Topology; 3)Distributed/Local Control 4) Asynchronous Communication; 5) (Polynomially) Bounded Memory; 6) No Minimal Connectivity Assumptions. In the confines of this network, we evaluate throughput performance and prove matching upper and lower bounds. In particular, using competitive analysis (perhaps somewhat surprisingly) we prove that the optimal competitive ratio of any on-line protocol is 1/n (where n is the number of nodes in the network), and then we describe a specific protocol and prove that it is n-competitive. The model we describe in the paper and for which we achieve the above matching upper and lower bounds for throughput represents the "worst-case" network, in that it makes no reliability assumptions. In many practical applications, the optimal competitive ratio of 1/n may be unacceptable, and consequently stronger assumptions must be imposed on the network to improve performance. However, we believe that a fundamental starting point to understanding which assumptions are necessary to impose on a network model, given some desired throughput performance, is to understand what is achievable in the worst case for the simplest task (namely end-to-end routing).
Algorithmic metatheorems for decidable LTL model checking over infinite systems
Venue: arXiv cs.LO 2009
Year: 2009

By algorithmic metatheorems for a model checking problem P over infinite-state systems we mean generic results that can be used to infer decidability (possibly complexity) of P not only over a specific class of infinite systems, but over a large family of classes of infinite systems. Such results normally start with a powerful formalism of infinite-state systems, over which P is undecidable, and assert decidability when is restricted by means of an extra "semantic condition" C. We prove various algorithmic metatheorems for the problems of model checking LTL and its two common fragments LTL(Fs,Gs) and LTLdet over the expressive class of word/tree automatic transition systems, which are generated by synchronized finite-state transducers operating on finite words and trees. We present numerous applications, where we derive (in a unified manner) many known and previously unknown decidability and complexity results of model checking LTL and its fragments over specific classes of infinite-state systems including pushdown systems; prefix-recognizable systems; reversal-bounded counter systems with discrete clocks and a free counter; concurrent pushdown systems with a bounded number of context-switches; various subclasses of Petri nets; weakly extended PA-processes; and weakly extended ground-tree rewrite systems. In all cases,we are able to derive optimal (or near optimal) complexity. Finally, we pinpoint the exact locations in the arithmetic and analytic hierarchies of the problem of checking a relevant semantic condition and the LTL model checking problems over all word/tree automatic systems.
Compiling and securing cryptographic protocols
Venue: arXiv cs.LO 2009
Year: 2009

Protocol narrations are widely used in security as semi-formal notations to specify conversations between roles. We define a translation from a protocol narration to the sequences of operations to be performed by each role. Unlike previous works, we reduce this compilation process to well-known decision problems in formal protocol analysis. This allows one to define a natural notion of prudent translation and to reuse many known results from the literature in order to cover more crypto-primitives. In particular this work is the first one to show how to compile protocols parameterised by the properties of the available operations.
Isogenies of Elliptic Curves: A Computational Approach
Venue: arXiv cs.CR 2009
Year: 2009

Isogenies, the mappings of elliptic curves, have become a useful tool in cryptology. These mathematical objects have been proposed for use in computing pairings, constructing hash functions and random number generators, and analyzing the reducibility of the elliptic curve discrete logarithm problem. With such diverse uses, understanding these objects is important for anyone interested in the field of elliptic curve cryptography. This paper, targeted at an audience with a knowledge of the basic theory of elliptic curves, provides an introduction to the necessary theoretical background for understanding what isogenies are and their basic properties. This theoretical background is used to explain some of the basic computational tasks associated with isogenies. Herein, algorithms for computing isogenies are collected and presented with proofs of correctness and complexity analyses. As opposed to the complex analytic approach provided in most texts on the subject, the proofs in this paper are primarily algebraic in nature. This provides alternate explanations that some with a more concrete or computational bias may find more clear.
An Analysis of Phase Synchronization Mismatch Sensitivity for Coherent MIMO Radar Systems
Venue: arXiv cs.IT 2009
Year: 2009

In this study, the hybrid Cramer-Rao bound (CRB) is developed for target localization, to establish the sensitivity of the estimation mean-square error (MSE) to the level of phase synchronization mismatch in coherent Multiple-Input Multiple-Output (MIMO) radar systems with widely distributed antennas. The lower bound on the MSE is derived for the joint estimation of the vector of unknown parameters, consisting of the target location and the mismatch of the allegedly known system parameters, i.e., phase offsets at the radars. Synchronization errors are modeled as being random and Gaussian. A closed-form expression for the hybrid CRB is derived for the case of orthogonal waveforms.The bound on the target localization MSE is expressed as the sum of two terms - the first represents the CRB with no phase mismatch, and the second captures the mismatch effect. The latter is shown to depend on the phase error variance, the number of mismatched transmitting and receiving sensors and the system geometry. For a given phase synchronization error variance, this expression offers the means to analyze the achievable localization accuracy. Alternatively, for a predetermined localization MSE target value, the derived expression may be used to determine the necessary phase synchronization level in the distributed system.
Exact algorithms for OWA-optimization in multiobjective spanning tree problems
Venue: arXiv cs.DS 2009
Year: 2009

This paper deals with the multiobjective version of the optimal spanning tree problem. More precisely, we are interested in determining the optimal spanning tree according to an Ordered Weighted Average (OWA) of its objective values. We first show that the problem is weakly NP-hard. In the case where the weights of the OWA are strictly decreasing, we then propose a mixed integer programming formulation, and provide dedicated optimality conditions yielding an important reduction of the size of the program. Next, we present two bounds that can be used to prune subspaces of solutions either in a shaving phase or in a branch and bound procedure. The validity of these bounds does not depend on specific properties of the weights (apart from non-negativity). All these exact resolution algorithms are compared on the basis of numerical experiments, according to their respective validity scopes.
Evaluating Trust in Grid Certificates
Venue: arXiv cs.CR 2009
Year: 2009

Digital certificates are used to secure international computation and data storage grids used for e-Science projects, like the Worldwide Large Hadron Collider Computing Grid. The International Grid Trust Federation has defined the Grid Certificate Profile: a set of guidelines for digital certificates used for grid authentication. We have designed and implemented a program and related test suites for checking X.509 certificates against the certificate profiles and policies relevant for use on the Grid. The result is a practical tool that assists implementers and users of public key infrastructures to reach appropriate trust decisions.
A Gibbs Sampling Based MAP Detection Algorithm for OFDM Over Rapidly Varying Mobile Radio Channels
Venue: arXiv cs.IT 2009
Year: 2009

In orthogonal frequency-division multiplexing (OFDM) systems operating over rapidly time-varying channels, the orthogonality between subcarriers is destroyed leading to inter-carrier interference (ICI) and resulting in an irreducible error floor. In this paper, a new and low-complexity maximum {\em a posteriori} probability (MAP) detection algorithm is proposed for OFDM systems operating over rapidly time-varying multipath channels. The detection algorithm exploits the banded structure of the frequency-domain channel matrix whose bandwidth is a parameter to be adjusted according to the speed of the mobile terminal. Based on this assumption, the received signal vector is decomposed into reduced dimensional sub-observations in such a way that all components of the observation vector contributing to the symbol to be detected are included in the decomposed observation model. The data symbols are then detected by the MAP algorithm by means of a Markov chain Monte Carlo (MCMC) technique in an optimal and computationally efficient way. Computational complexity investigation as well as simulation results indicate that this algorithm has significant performance and complexity advantages over existing suboptimal detection and equalization algorithms proposed earlier in the literature.
The capacity region of a product of two unmatched Gaussian broadcast channels with three particular messages and a common message
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers a Gaussian broadcast channel with two unmatched degraded components, three particular messages, and a common message that is intended for all three receivers. It is shown that for this channel superposition coding and Gaussian signalling is sufficient to achieve every point in the capacity region.
A proof of the log-concavity conjecture related to the computation of the ergodic capacity of MIMO channels
Venue: arXiv cs.IT 2009
Year: 2009

An upper bound on the ergodic capacity of {\bf MIMO} channels was introduced recently in arXiv:0903.1952. This upper bound amounts to the maximization on the simplex of some multilinear polynomial $p(λ_1,...,λ_n)$ with non-negative coefficients. Interestingly, the coefficients are subpermanents of some non-negative matrix. In general, such maximizations problems are {\bf NP-HARD}. But if say, the functional $\log(p)$ is concave on the simplex and can be efficiently evaluated, then the maximization can also be done efficiently. Such log-concavity was conjectured in arXiv:0903.1952. We give in this paper self-contained proof of the conjecture, based on the theory of {\bf H-Stable} polynomials.
Management of Location Based Advertisement Services using Spatial Triggers in Cellular Networks
Venue: arXiv cs.NI 2009
Year: 2009

This paper discusses the advent of new technologies which have emerged under the area of Location Based Services (LBS). An innovative implementation and approach has been presented for design of applications which are inventive and attractive towards the user. Spatial Trigger is one of the most promising additions to the LBS technologies. This paper describes ways in which mobile advertisement services can be introduced effectively in the cellular market by bringing innovation in them through effective usage of Spatial Triggers. Hence, opening new horizons to make the consumer cellular networks, commercially, more effective and informative.
Multi-Agent System Interaction in Integrated SCM
Venue: arXiv cs.MA 2009
Year: 2009

Coordination between organizations on strategic, tactical and operation levels leads to more effective and efficient supply chains. Supply chain management is increasing day by day in modern enterprises. The environment is becoming competitive and many enterprises will find it difficult to survive if they do not make their sourcing, production and distribution more efficient. Multi-agent supply chain management has recognized as an effective methodology for supply chain management. Multi-agent systems (MAS) offer new methods compared to conventional, centrally organized architectures in the scope of supply chain management (SCM). Since necessary data are not available within the whole supply chain, an integrated approach for production planning and control taking into account all the partners involved is not feasible. In this study we show how MAS architecture interacts in the integrated SCM architecture with the help of various intelligent agents to highlight the above problem.
Sum Rates, Rate Allocation, and User Scheduling for Multi-User MIMO Vector Perturbation Precoding
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers the multiuser multiple-input multiple-output (MIMO) broadcast channel. We consider the case where the multiple transmit antennas are used to deliver independent data streams to multiple users via vector perturbation. We derive expressions for the sum rate in terms of the average energy of the precoded vector, and use this to derive a high signal-to-noise ratio (SNR) closed-form upper bound, which we show to be tight via simulation. We also propose a modification to vector perturbation where different rates can be allocated to different users. We conclude that for vector perturbation precoding most of the sum rate gains can be achieved by reducing the rate allocation problem to the user selection problem. We then propose a low-complexity user selection algorithm that attempts to maximize the high-SNR sum rate upper bound. Simulations show that the algorithm outperforms other user selection algorithms of similar complexity.
Memento: Time Travel for the Web
Venue: arXiv cs.IR 2009
Year: 2009

The Web is ephemeral. Many resources have representations that change over time, and many of those representations are lost forever. A lucky few manage to reappear as archived resources that carry their own URIs. For example, some content management systems maintain version pages that reflect a frozen prior state of their changing resources. Archives recurrently crawl the web to obtain the actual representation of resources, and subsequently make those available via special-purpose archived resources. In both cases, the archival copies have URIs that are protocol-wise disconnected from the URI of the resource of which they represent a prior state. Indeed, the lack of temporal capabilities in the most common Web protocol, HTTP, prevents getting to an archived resource on the basis of the URI of its original. This turns accessing archived resources into a significant discovery challenge for both human and software agents, which typically involves following a multitude of links from the original to the archival resource, or of searching archives for the original URI. This paper proposes the protocol-based Memento solution to address this problem, and describes a proof-of-concept experiment that includes major servers of archival content, including Wikipedia and the Internet Archive. The Memento solution is based on existing HTTP capabilities applied in a novel way to add the temporal dimension. The result is a framework in which archived resources can seamlessly be reached via the URI of their original: protocol-based time travel for the Web.
The Dynamics of Exchanges and References among Scientific Texts, and the Autopoiesis of Discursive Knowledge
Venue: arXiv cs.CY 2009
Year: 2009

Discursive knowledge emerges as codification in flows of communication. The flows of communication are constrained and enabled by networks of communications as their historical manifestations at each moment of time. New publications modify the existing networks by changing the distributions of attributes and relations in document sets, while the networks are self-referentially updated along trajectories. Codification operates reflexively: the network structures are reconstructed from the perspective of hindsight. Codification along different axes differentiates discursive knowledge into specialties. These intellectual control structures are constructed bottom-up, but feed top-down back upon the production of new knowledge. However, the forward dynamics of diffusion in the development of the communication networks along trajectories differs from the feedback mechanisms of control. Analysis of the development of scientific communication in terms of evolving scientific literatures provides us with a model which makes these evolutionary processes amenable to measurement.
On the maximal number of cubic subwords in a string
Venue: arXiv cs.FL 2009
Year: 2009

We investigate the problem of the maximum number of cubic subwords (of the form $www$) in a given word. We also consider square subwords (of the form $ww$). The problem of the maximum number of squares in a word is not well understood. Several new results related to this problem are produced in the paper. We consider two simple problems related to the maximum number of subwords which are squares or which are highly repetitive; then we provide a nontrivial estimation for the number of cubes. We show that the maximum number of squares $xx$ such that $x$ is not a primitive word (nonprimitive squares) in a word of length $n$ is exactly $\lfloor \frac{n}{2}\rfloor - 1$, and the maximum number of subwords of the form $x^k$, for $k\ge 3$, is exactly $n-2$. In particular, the maximum number of cubes in a word is not greater than $n-2$ either. Using very technical properties of occurrences of cubes, we improve this bound significantly. We show that the maximum number of cubes in a word of length $n$ is between $(1/2)n$ and $(4/5)n$. (In particular, we improve the lower bound from the conference version of the paper.)
On the Capacity of the Half-Duplex Diamond Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, a dual-hop communication system composed of a source S and a destination D connected through two non-interfering half-duplex relays, R1 and R2, is considered. In the literature of Information Theory, this configuration is known as the diamond channel. In this setup, four transmission modes are present, namely: 1) S transmits, and R1 and R2 listen (broadcast mode), 2) S transmits, R1 listens, and simultaneously, R2 transmits and D listens. 3) S transmits, R2 listens, and simultaneously, R1 transmits and D listens. 4) R1, R2 transmit, and D listens (multiple-access mode). Assuming a constant power constraint for all transmitters, a parameter $Δ$ is defined, which captures some important features of the channel. It is proven that for $Δ$=0 the capacity of the channel can be attained by successive relaying, i.e, using modes 2 and 3 defined above in a successive manner. This strategy may have an infinite gap from the capacity of the channel when $Δ\neq$0. To achieve rates as close as 0.71 bits to the capacity, it is shown that the cases of $Δ$>0 and $Δ$<0 should be treated differently. Using new upper bounds based on the dual problem of the linear program associated with the cut-set bounds, it is proven that the successive relaying strategy needs to be enhanced by an additional broadcast mode (mode 1), or multiple access mode (mode 4), for the cases of $Δ$<0 and $Δ$>0, respectively. Furthermore, it is established that under average power constraints the aforementioned strategies achieve rates as close as 3.6 bits to the capacity of the channel.