OpenRaiser/Intern-Atlas huggingface dataset:
A Simple Converse Proof and a Unified Capacity Formula for Channels with Input Constraints
Venue: arXiv cs.IT 2008
Year: 2008

Given the single-letter capacity formula and the converse proof of a channel without constraints, we provide a simple approach to extend the results for the same channel but with constraints. The resulting capacity formula is the minimum of a Lagrange dual function. It gives an unified formula in the sense that it works regardless whether the problem is convex. If the problem is non-convex, we show that the capacity can be larger than the formula obtained by the naive approach of imposing constraints on the maximization in the capacity formula of the case without the constraints. The extension on the converse proof is simply by adding a term involving the Lagrange multiplier and the constraints. The rest of the proof does not need to be changed. We name the proof method the Lagrangian Converse Proof. In contrast, traditional approaches need to construct a better input distribution for convex problems or need to introduce a time sharing variable for non-convex problems. We illustrate the Lagrangian Converse Proof for three channels, the classic discrete time memoryless channel, the channel with non-causal channel-state information at the transmitter, the channel with limited channel-state feedback. The extension to the rate distortion theory is also provided.
Nonstandard linear recurring sequence subgroups in finite fields and automorphisms of cyclic codes
Venue: arXiv cs.IT 2008
Year: 2008

Let $q=p^r$ be a prime power, and let $f(x)=x^m-\gs_{m-1}x^{m-1}- >...-\gs_1x-\gs_0$ be an irreducible polynomial over the finite field $\GF(q)$ of size $q$. A zero $ξ$ of $f$ is called {\em nonstandard (of degree $m$) over $\GF(q)$} if the recurrence relation $u_m=\gs_{m-1}u_{m-1} + ... + \gs_1u_1+\gs_0u_0$ with characteristic polynomial $f$ can generate the powers of $ξ$ in a nontrivial way, that is, with $u_0=1$ and $f(u_1)\neq 0$. In 2003, Brison and Nogueira asked for a characterisation of all nonstandard cases in the case $m=2$, and solved this problem for $q$ a prime, and later for $q=p^r$ with $r\leq4$. In this paper, we first show that classifying nonstandard finite field elements is equivalent to classifying those cyclic codes over $\GF(q)$ generated by a single zero that posses extra permutation automorphisms. Apart from two sporadic examples of degree 11 over $\GF(2)$ and of degree 5 over $\GF(3)$, related to the Golay codes, there exist two classes of examples of nonstandard finite field elements. One of these classes (type I) involves irreducible polynomials $f$ of the form $f(x)=x^m-f_0$, and is well-understood. The other class (type II) can be obtained from a primitive element in some subfield by a process that we call extension and lifting. We will use the known classification of the subgroups of $\PGL(2,q)$ in combination with a recent result by Brison and Nogueira to show that a nonstandard element of degree two over $\GF(q)$ necessarily is of type I or type II, thus solving completely the classification problem for the case $m=2$.
Exact two-terminal reliability of some directed networks
Venue: arXiv cs.PF 2008
Year: 2008

The calculation of network reliability in a probabilistic context has long been an issue of practical and academic importance. Conventional approaches (determination of bounds, sums of disjoint products algorithms, Monte Carlo evaluations, studies of the reliability polynomials, etc.) only provide approximations when the network's size increases, even when nodes do not fail and all edges have the same reliability p. We consider here a directed, generic graph of arbitrary size mimicking real-life long-haul communication networks, and give the exact, analytical solution for the two-terminal reliability. This solution involves a product of transfer matrices, in which individual reliabilities of edges and nodes are taken into account. The special case of identical edge and node reliabilities (p and rho, respectively) is addressed. We consider a case study based on a commonly-used configuration, and assess the influence of the edges being directed (or not) on various measures of network performance. While the two-terminal reliability, the failure frequency and the failure rate of the connection are quite similar, the locations of complex zeros of the two-terminal reliability polynomials exhibit strong differences, and various structure transitions at specific values of rho. The present work could be extended to provide a catalog of exactly solvable networks in terms of reliability, which could be useful as building blocks for new and improved bounds, as well as benchmarks, in the general case.
Collaborative Virtual Queue: Fair Management of Congested Departure Operations and Benefit Analysis
Venue: arXiv cs.OH 2008
Year: 2008

Due to the stochastic nature of departure operations, working at full capacity makes major US airports very sensitive to uncertainties. Consequently, airport ground operations face critically congested taxiways and long runway queues. In this report, we show how improved management of departure operations from the ready-to-push-back time to the wheels-off time can potentially yield significant benefits to airlines and air traffic services. We develop a Collaborative Virtual Queue to enable better optimization capabilities during congested situations while taking into account the laissez-faire competitive environment. Results are evaluated using a departure system model, validated using current statistics and previous studies. First, the Collaborative Virtual Queue enables keeping aircraft away from runway queues, which increases wheels-off time predictability. Second, holding aircraft enables last-minute intra-airline flight switching. This creates new optimization capabilities for airlines i.e. it gives airlines the flexibility to prioritize their flight sequence in real-time. These capabilities are illustrated by the trade-off between minimizing the average passenger waiting time and minimizing the level of unfairness between aircraft of the same airline. For instance, airlines could choose to decrease by up to 15% their average passenger waiting time by prioritizing heavy planes over small planes when the taxiway system is congested.
The Parikh functions of sparse context-free languages are quasi-polynomials
Venue: arXiv cs.DM 2008
Year: 2008

We prove that the Parikh map of a bounded context-free language is a box spline. Moreover we prove that in this case, such a function is rational.
A VoIP Privacy Mechanism and its Application in VoIP Peering for Voice Service Provider Topology and Identity Hiding
Venue: arXiv cs.NI 2008
Year: 2008

Voice Service Providers (VSPs) participating in VoIP peering frequently want to withhold their identity and related privacy-sensitive information from other parties during the VoIP communication. A number of existing documents on VoIP privacy exist, but most of them focus on end user privacy. By summarizing and extending existing work, we present a unified privacy mechanism for both VoIP users and service providers. We also show a case study on how VSPs can use this mechanism for identity and topology hiding in VoIP peering.
Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections
Venue: arXiv cs.DM 2008
Year: 2008

We derive new results for the performance of a simple greedy algorithm for finding large independent sets and matchings in constant degree regular graphs. We show that for $r$-regular graphs with $n$ nodes and girth at least $g$, the algorithm finds an independent set of expected cardinality $f(r)n - O\big(\frac{(r-1)^{\frac{g}{2}}}{\frac{g}{2}!} n\big)$, where $f(r)$ is a function which we explicitly compute. A similar result is established for matchings. Our results imply improved bounds for the size of the largest independent set in these graphs, and provide the first results of this type for matchings. As an implication we show that the greedy algorithm returns a nearly perfect matching when both the degree $r$ and girth $g$ are large. Furthermore, we show that the cardinality of independent sets and matchings produced by the greedy algorithm in \emph{arbitrary} bounded degree graphs is concentrated around the mean. Finally, we analyze the performance of the greedy algorithm for the case of random i.i.d. weighted independent sets and matchings, and obtain a remarkably simple expression for the limiting expected values produced by the algorithm. In fact, all the other results are obtained as straightforward corollaries from the results for the weighted case.
Satisfiability of Almost Disjoint CNF Formulas
Venue: arXiv cs.DM 2008
Year: 2008

We call a CNF formula linear if any two clauses have at most one variable in common. Let m(k) be the largest integer m such that any linear k-CNF formula with <= m clauses is satisfiable. We show that 4^k / (4e^2k^3) <= m(k) < ln(2) k^4 4^k. More generally, a (k,d)-CSP is a constraint satisfaction problem in conjunctive normal form where each variable can take on one of d values, and each constraint contains k variables and forbids exacty one of the d^k possible assignments to these variables. Call a (k,d)-CSP l-disjoint if no two distinct constraints have l or more variables in common. Let m_l(k,d) denote the largest integer m such that any l-disjoint (k,d)-CSP with at most m constraints is satisfiable. We show that 1/k (d^k/(ed^(l-1)k))^(1+1/(l-1))<= m_l(k,d) < c (k^2/l ln(d) d^k)^(1+1/(l-1)). for some constant c. This means for constant l, upper and lower bound differ only in a polynomial factor in d and k.
Quasi-Mandelbrot sets for perturbed complex analytic maps: visual patterns
Venue: arXiv cs.GR 2008
Year: 2008

We consider perturbations of the complex quadratic map $ z \to z^2 +c$ and corresponding changes in their quasi-Mandelbrot sets. Depending on particular perturbation, visual forms of quasi-Mandelbrot set changes either sharply (when the perturbation reaches some critical value) or continuously. In the latter case we have a smooth transition from the classical form of the set to some forms, constructed from mostly linear structures, as it is typical for two-dimensional real number dynamics. Two examples of continuous evolution of the quasi-Mandelbrot set are described.
Faster Sequential Search with a Two-Pass Dynamic-Time-Warping Lower Bound
Venue: arXiv cs.DB 2008
Year: 2008

The Dynamic Time Warping (DTW) is a popular similarity measure between time series. The DTW fails to satisfy the triangle inequality and its computation requires quadratic time. Hence, to find closest neighbors quickly, we use bounding techniques. We can avoid most DTW computations with an inexpensive lower bound (LB_Keogh). We compare LB_Keogh with a tighter lower bound (LB_Improved). We find that LB_Improved-based search is faster for sequential search. As an example, our approach is 3 times faster over random-walk and shape time series. We also review some of the mathematical properties of the DTW. We derive a tight triangle inequality for the DTW. We show that the DTW becomes the l_1 distance when time series are separated by a constant.
Extension of Inagaki General Weighted Operators and A New Fusion Rule Class of Proportional Redistribution of Intersection Masses
Venue: arXiv cs.AI 2008
Year: 2008

In this paper we extend Inagaki Weighted Operators fusion rule (WO) in information fusion by doing redistribution of not only the conflicting mass, but also of masses of non-empty intersections, that we call Double Weighted Operators (DWO). Then we propose a new fusion rule Class of Proportional Redistribution of Intersection Masses (CPRIM), which generates many interesting particular fusion rules in information fusion. Both formulas are presented for any number of sources of information. An application and comparison with other fusion rules are given in the last section.
Optimal Acyclic Hamiltonian Path Completion for Outerplanar Triangulated st-Digraphs (with Application to Upward Topological Book Embeddings)
Venue: arXiv cs.DS 2008
Year: 2008

Given an embedded planar acyclic digraph G, we define the problem of "acyclic hamiltonian path completion with crossing minimization (Acyclic-HPCCM)" to be the problem of determining an hamiltonian path completion set of edges such that, when these edges are embedded on G, they create the smallest possible number of edge crossings and turn G to a hamiltonian digraph. Our results include: --We provide a characterization under which a triangulated st-digraph G is hamiltonian. --For an outerplanar triangulated st-digraph G, we define the st-polygon decomposition of G and, based on its properties, we develop a linear-time algorithm that solves the Acyclic-HPCCM problem with at most one crossing per edge of G. --For the class of st-planar digraphs, we establish an equivalence between the Acyclic-HPCCM problem and the problem of determining an upward 2-page topological book embedding with minimum number of spine crossings. We infer (based on this equivalence) for the class of outerplanar triangulated st-digraphs an upward topological 2-page book embedding with minimum number of spine crossings and at most one spine crossing per edge. To the best of our knowledge, it is the first time that edge-crossing minimization is studied in conjunction with the acyclic hamiltonian completion problem and the first time that an optimal algorithm with respect to spine crossing minimization is presented for upward topological book embeddings.
CPBVP: A Constraint-Programming Framework for Bounded Program Verification
Venue: arXiv cs.SE 2008
Year: 2008

This paper studies how to verify the conformity of a program with its specification and proposes a novel constraint-programming framework for bounded program verification (CPBPV). The CPBPV framework uses constraint stores to represent the specification and the program and explores execution paths nondeterministically. The input program is partially correct if each constraint store so produced implies the post-condition. CPBPV does not explore spurious execution paths as it incrementally prunes execution paths early by detecting that the constraint store is not consistent. CPBPV uses the rich language of constraint programming to express the constraint store. Finally, CPBPV is parametrized with a list of solvers which are tried in sequence, starting with the least expensive and less general. Experimental results often produce orders of magnitude improvements over earlier approaches, running times being often independent of the variable domains. Moreover, CPBPV was able to detect subtle errors in some programs while other frameworks based on model checking have failed.
Topological Observations on Multiplicative Additive Linear Logic
Venue: arXiv cs.LO 2008
Year: 2008

As an attempt to uncover the topological nature of composition of strategies in game semantics, we present a ``topological'' game for Multiplicative Additive Linear Logic without propositional variables, including cut moves. We recast the notion of (winning) strategy and the question of cut elimination in this context, and prove a cut elimination theorem. Finally, we prove soundness and completeness. The topology plays a crucial role, in particular through the fact that strategies form a sheaf.
A Cutting Plane Method based on Redundant Rows for Improving Fractional Distance
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, an idea of the cutting plane method is employed to improve the fractional distance of a given binary parity check matrix. The fractional distance is the minimum weight (with respect to l1-distance) of vertices of the fundamental polytope. The cutting polytope is defined based on redundant rows of the parity check matrix and it plays a key role to eliminate unnecessary fractional vertices in the fundamental polytope. We propose a greedy algorithm and its efficient implementation for improving the fractional distance based on the cutting plane method.
An Asymptotic Analysis of the MIMO BC under Linear Filtering
Venue: arXiv cs.IT 2008
Year: 2008

We investigate the MIMO broadcast channel in the high SNR regime when linear filtering is applied instead of dirty paper coding. Using a user-wise rate duality where the streams of every single user are not treated as self-interference as in the hitherto existing stream-wise rate dualities for linear filtering, we solve the weighted sum rate maximization problem of the broadcast channel in the dual multiple access channel. Thus, we can exactly quantify the asymptotic rate loss of linear filtering compared to dirty paper coding for any channel realization. Having converted the optimum covariance matrices to the broadcast channel by means of the duality, we observe that the optimal covariance matrices in the broadcast channel feature quite complicated but still closed form expressions although the respective transmit covariance matrices in the dual multiple access channel share a very simple structure. We immediately come to the conclusion that block-diagonalization is the asymptotically optimum transmit strategy in the broadcast channel. Out of the set of block-diagonalizing precoders, we present the one which achieves the largest sum rate and thus corresponds to the optimum solution found in the dual multiple access channel. Additionally, we quantify the ergodic rate loss of linear coding compared to dirty paper coding for Gaussian channels with correlations at the mobiles.
Audit and Change Analysis of Spreadsheets
Venue: arXiv cs.HC 2008
Year: 2008

Because spreadsheets have a large and growing importance in real-world work, their contents need to be controlled and validated. Generally spreadsheets have been difficult to verify, since data and executable information are stored together. Spreadsheet applications with multiple authors are especially difficult to verify, since controls over access are difficult to enforce. Facing similar problems, traditional software engineering has developed numerous tools and methodologies to control, verify and audit large applications with multiple developers. We present some tools we have developed to enable 1) the audit of selected, filtered, or all changes in a spreadsheet, that is, when a cell was changed, its original and new contents and who made the change, and 2) control of access to the spreadsheet file(s) so that auditing is trustworthy. Our tools apply to OpenOffice.org calc spreadsheets, which can generally be exchanged with Microsoft Excel.
Research Strategy and Scoping Survey on Spreadsheet Practices
Venue: arXiv cs.HC 2008
Year: 2008

We propose a research strategy for creating and deploying prescriptive recommendations for spreadsheet practice. Empirical data on usage can be used to create a taxonomy of spreadsheet classes. Within each class, existing practices and ideal practices can he combined into proposed best practices for deployment. As a first step we propose a scoping survey to gather non-anecdotal data on spreadsheet usage. The scoping survey will interview people who develop spreadsheets. We will investigate the determinants of spreadsheet importance, identify current industry practices, and document existing standards for creation and use of spreadsheets. The survey will provide insight into user attributes, spreadsheet importance, and current practices. Results will be valuable in themselves, and will guide future empirical research.
A characterization of 2-player mechanisms for scheduling
Venue: arXiv cs.GT 2008
Year: 2008

We study the mechanism design problem of scheduling unrelated machines and we completely characterize the decisive truthful mechanisms for two players when the domain contains both positive and negative values. We show that the class of truthful mechanisms is very limited: A decisive truthful mechanism partitions the tasks into groups so that the tasks in each group are allocated independently of the other groups. Tasks in a group of size at least two are allocated by an affine minimizer and tasks in singleton groups by a task-independent mechanism. This characterization is about all truthful mechanisms, including those with unbounded approximation ratio. A direct consequence of this approach is that the approximation ratio of mechanisms for two players is 2, even for two tasks. In fact, it follows that for two players, VCG is the unique algorithm with optimal approximation 2. This characterization provides some support that any decisive truthful mechanism (for 3 or more players) partitions the tasks into groups some of which are allocated by affine minimizers, while the rest are allocated by a threshold mechanism (in which a task is allocated to a player when it is below a threshold value which depends only on the values of the other players). We also show here that the class of threshold mechanisms is identical to the class of additive mechanisms.
Formal semantics of language and the Richard-Berry paradox
Venue: arXiv cs.CL 2008
Year: 2008

The classical logical antinomy known as Richard-Berry paradox is combined with plausible assumptions about the size i.e. the descriptional complexity of Turing machines formalizing certain sentences, to show that formalization of language leads to contradiction.
A Distributed Process Infrastructure for a Distributed Data Structure
Venue: arXiv cs.AI 2008
Year: 2008

The Resource Description Framework (RDF) is continuing to grow outside the bounds of its initial function as a metadata framework and into the domain of general-purpose data modeling. This expansion has been facilitated by the continued increase in the capacity and speed of RDF database repositories known as triple-stores. High-end RDF triple-stores can hold and process on the order of 10 billion triples. In an effort to provide a seamless integration of the data contained in RDF repositories, the Linked Data community is providing specifications for linking RDF data sets into a universal distributed graph that can be traversed by both man and machine. While the seamless integration of RDF data sets is important, at the scale of the data sets that currently exist and will ultimately grow to become, the "download and index" philosophy of the World Wide Web will not so easily map over to the Semantic Web. This essay discusses the importance of adding a distributed RDF process infrastructure to the current distributed RDF data structure.
DMT of weighted Parallel Channels: Application to Broadcast Channel
Venue: arXiv cs.IT 2008
Year: 2008

In a broadcast channel with random packet arrival and transmission queues, the stability of the system is achieved by maximizing a weighted sum rate capacity with suitable weights that depend on the queue size. The weighted sum rate capacity using Dirty Paper Coding (DPC) and Zero Forcing (ZF) is asymptotically equivalent to the weighted sum capacity over parallel single-channels. In this paper, we study the Diversity Multiplexing Tradeoff (DMT) of the fading broadcast channel under a fixed weighted sum rate capacity constraint. The DMT of both identical and different parallel weighted MISO channels is first derived. Finally, we deduce the DMT of a broadcast channel using DPC and ZF precoders.