OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Compact Regular Expression Matching
Venue: arXiv cs.DS 2008
Year: 2008

We study 4 problems in string matching, namely, regular expression matching, approximate regular expression matching, string edit distance, and subsequence indexing, on a standard word RAM model of computation that allows logarithmic-sized words to be manipulated in constant time. We show how to improve the space and/or remove a dependency on the alphabet size for each problem using either an improved tabulation technique of an existing algorithm or by combining known algorithms in a new way.
Logical Relations for Monadic Types
Venue: arXiv cs.LO 2008
Year: 2008

Logical relations and their generalizations are a fundamental tool in proving properties of lambda-calculi, e.g., yielding sound principles for observational equivalence. We propose a natural notion of logical relations able to deal with the monadic types of Moggi's computational lambda-calculus. The treatment is categorical, and is based on notions of subsconing, mono factorization systems, and monad morphisms. Our approach has a number of interesting applications, including cases for lambda-calculi with non-determinism (where being in logical relation means being bisimilar), dynamic name creation, and probabilistic systems.
A polynomial algorithm for the k-cluster problem on interval graphs
Venue: arXiv cs.DS 2008
Year: 2008

This paper deals with the problem of finding, for a given graph and a given natural number k, a subgraph of k nodes with a maximum number of edges. This problem is known as the k-cluster problem and it is NP-hard on general graphs as well as on chordal graphs. In this paper, it is shown that the k-cluster problem is solvable in polynomial time on interval graphs. In particular, we present two polynomial time algorithms for the class of proper interval graphs and the class of general interval graphs, respectively. Both algorithms are based on a matrix representation for interval graphs. In contrast to representations used in most of the previous work, this matrix representation does not make use of the maximal cliques in the investigated graph.
On the 3-distortion of a path
Venue: arXiv cs.CG 2008
Year: 2008

We prove that, when a path of length n is embedded in R^2, the 3-distortion is an Omega(n^{1/2}), and that, when embedded in R^d, the 3-distortion is an O(n^{1/d-1}).
Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition
Venue: arXiv cs.CG 2008
Year: 2008

We provide efficient constant factor approximation algorithms for the problems of finding a hierarchical clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can also be used to provide a pants decomposition, that is, a set of disjoint simple closed curves partitioning the plane minus the input points into subsets with exactly three boundary components, with approximately minimum total length. In the Euclidean case, these curves are squares; in the hyperbolic case, they combine our Euclidean square pants decomposition with our tree clustering method for general metric spaces.
A Distribution Law for CCS and a New Congruence Result for the pi-calculus
Venue: arXiv cs.LO 2008
Year: 2008

We give an axiomatisation of strong bisimilarity on a small fragment of CCS that does not feature the sum operator. This axiomatisation is then used to derive congruence of strong bisimilarity in the finite pi-calculus in absence of sum. To our knowledge, this is the only nontrivial subcalculus of the pi-calculus that includes the full output prefix and for which strong bisimilarity is a congruence.
Classdesc and Graphcode: support for scientific programming in C++
Venue: arXiv cs.MS 2008
Year: 2008

Object-oriented programming languages such as Java and Objective C have become popular for implementing agent-based and other object-based simulations since objects in those languages can {\em reflect} (i.e. make runtime queries of an object's structure). This allows, for example, a fairly trivial {\em serialisation} routine (conversion of an object into a binary representation that can be stored or passed over a network) to be written. However C++ does not offer this ability, as type information is thrown away at compile time. Yet C++ is often a preferred development environment, whether for performance reasons or for its expressive features such as operator overloading. In scientific coding, changes to a model's codes takes place constantly, as the model is refined, and different phenomena are studied. Yet traditionally, facilities such as checkpointing, routines for initialising model parameters and analysis of model output depend on the underlying model remaining static, otherwise each time a model is modified, a whole slew of supporting routines needs to be changed to reflect the new data structures. Reflection offers the advantage of the simulation framework adapting to the underlying model without programmer intervention, reducing the effort of modifying the model. In this paper, we present the {\em Classdesc} system which brings many of the benefits of object reflection to C++, {\em ClassdescMP} which dramatically simplifies coding of MPI based parallel programs and {\em Graphcode} a general purpose data parallel programming environment.
The Formal System lambda-delta
Venue: arXiv cs.LO 2008
Year: 2008

The formal system lambda-delta is a typed lambda calculus that pursues the unification of terms, types, environments and contexts as the main goal. lambda-delta takes some features from the Automath-related lambda calculi and some from the pure type systems, but differs from both in that it does not include the Pi construction while it provides for an abbreviation mechanism at the level of terms. lambda-delta enjoys some important desirable properties such as the confluence of reduction, the correctness of types, the uniqueness of types up to conversion, the subject reduction of the type assignment, the strong normalization of the typed terms and, as a corollary, the decidability of type inference problem.
Proportional Fairness in Multi-channel Multi-rate Wireless Networks-Part II: The Case of Time-Varying Channels
Venue: arXiv cs.PF 2008
Year: 2008

This is Part II of a two-part paper series that studies the use of the proportional fairness (PF) utility function as the basis for capacity allocation and scheduling in multi-channel multi-rate wireless networks. The contributions of Part II are twofold. (i) First, we extend the problem formulation, theoretical results, and algorithms to the case of time-varying channels, where opportunistic capacity allocation and scheduling can be exploited to improve system performance. We lay down the theoretical foundation for optimization that "couples" the time-varying characteristic of channels with the requirements of the underlying applications into one consideration. In particular, the extent to which opportunistic optimization is possible is not just a function of how fast the channel characteristics vary, but also a function of the elasticity of the underlying applications for delayed capacity allocation. (ii) Second, building upon our theoretical framework and results, we study subcarrier allocation and scheduling in orthogonal frequency division multiplexing (OFDM) cellular wireless networks. We introduce the concept of a W-normalized Doppler frequency to capture the extent to which opportunistic scheduling can be exploited to achieve throughput-fairness performance gain. We show that a "look-back PF" scheduling can strike a good balance between system throughput and fairness while taking the underlying application requirements into account.
A Neutrosophic Description Logic
Venue: arXiv cs.AI 2008
Year: 2008

Description Logics (DLs) are appropriate, widely used, logics for managing structured knowledge. They allow reasoning about individuals and concepts, i.e. set of individuals with common properties. Typically, DLs are limited to dealing with crisp, well defined concepts. That is, concepts for which the problem whether an individual is an instance of it is yes/no question. More often than not, the concepts encountered in the real world do not have a precisely defined criteria of membership: we may say that an individual is an instance of a concept only to a certain degree, depending on the individual's properties. The DLs that deal with such fuzzy concepts are called fuzzy DLs. In order to deal with fuzzy, incomplete, indeterminate and inconsistent concepts, we need to extend the fuzzy DLs, combining the neutrosophic logic with a classical DL. In particular, concepts become neutrosophic (here neutrosophic means fuzzy, incomplete, indeterminate, and inconsistent), thus reasoning about neutrosophic concepts is supported. We'll define its syntax, its semantics, and describe its properties.
On the Decoder Error Probability of Bounded Rank-Distance Decoders for Maximum Rank Distance Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we first introduce the concept of elementary linear subspace, which has similar properties to those of a set of coordinates. We then use elementary linear subspaces to derive properties of maximum rank distance (MRD) codes that parallel those of maximum distance separable codes. Using these properties, we show that, for MRD codes with error correction capability t, the decoder error probability of bounded rank distance decoders decreases exponentially with t^2 based on the assumption that all errors with the same rank are equally likely.
What is the probability of connecting two points ?
Venue: arXiv cs.DM 2008
Year: 2008

The two-terminal reliability, known as the pair connectedness or connectivity function in percolation theory, may actually be expressed as a product of transfer matrices in which the probability of operation of each link and site is exactly taken into account. When link and site probabilities are $p$ and $ρ$, it obeys an asymptotic power-law behavior, for which the scaling factor is the transfer matrix's eigenvalue of largest modulus. The location of the complex zeros of the two-terminal reliability polynomial exhibits structural transitions as $0 \leq ρ\leq 1$.
Orthogonal Codes for Robust Low-Cost Communication
Venue: arXiv cs.IT 2008
Year: 2008

Orthogonal coding schemes, known to asymptotically achieve the capacity per unit cost (CPUC) for single-user ergodic memoryless channels with a zero-cost input symbol, are investigated for single-user compound memoryless channels, which exhibit uncertainties in their input-output statistical relationships. A minimax formulation is adopted to attain robustness. First, a class of achievable rates per unit cost (ARPUC) is derived, and its utility is demonstrated through several representative case studies. Second, when the uncertainty set of channel transition statistics satisfies a convexity property, optimization is performed over the class of ARPUC through utilizing results of minimax robustness. The resulting CPUC lower bound indicates the ultimate performance of the orthogonal coding scheme, and coincides with the CPUC under certain restrictive conditions. Finally, still under the convexity property, it is shown that the CPUC can generally be achieved, through utilizing a so-called mixed strategy in which an orthogonal code contains an appropriate composition of different nonzero-cost input symbols.
Formal proof for delayed finite field arithmetic using floating point operators
Venue: arXiv cs.SC 2008
Year: 2008

Formal proof checkers such as Coq are capable of validating proofs of correction of algorithms for finite field arithmetics but they require extensive training from potential users. The delayed solution of a triangular system over a finite field mixes operations on integers and operations on floating point numbers. We focus in this report on verifying proof obligations that state that no round off error occurred on any of the floating point operations. We use a tool named Gappa that can be learned in a matter of minutes to generate proofs related to floating point arithmetic and hide technicalities of formal proof checkers. We found that three facilities are missing from existing tools. The first one is the ability to use in Gappa new lemmas that cannot be easily expressed as rewriting rules. We coined the second one ``variable interchange'' as it would be required to validate loop interchanges. The third facility handles massive loop unrolling and argument instantiation by generating traces of execution for a large number of cases. We hope that these facilities may sometime in the future be integrated into mainstream code validation.
Constructions of Grassmannian Simplices
Venue: arXiv cs.IT 2008
Year: 2008

In this article an explicit method (relying on representation theory) to construct packings in Grassmannian space is presented. Infinite families of configurations having only one non-trivial set of principal angles are found using 2-transitive groups. These packings are proved to reach the simplex bound and are therefore optimal w.r.t. the chordal distance. The construction is illustrated by an example on the symmetric group. Then some natural extends and consequences of this situation are given.
Unasssuming View-Size Estimation Techniques in OLAP
Venue: arXiv cs.DB 2008
Year: 2008

Even if storage was infinite, a data warehouse could not materialize all possible views due to the running time and update requirements. Therefore, it is necessary to estimate quickly, accurately, and reliably the size of views. Many available techniques make particular statistical assumptions and their error can be quite large. Unassuming techniques exist, but typically assume we have independent hashing for which there is no known practical implementation. We adapt an unassuming estimator due to Gibbons and Tirthapura: its theoretical bounds do not make unpractical assumptions. We compare this technique experimentally with stochastic probabilistic counting, LogLog probabilistic counting, and multifractal statistical models. Our experiments show that we can reliably and accurately (within 10%, 19 times out 20) estimate view sizes over large data sets (1.5 GB) within minutes, using almost no memory. However, only Gibbons-Tirthapura provides universally tight estimates irrespective of the size of the view. For large views, probabilistic counting has a small edge in accuracy, whereas the competitive sampling-based method (multifractal) we tested is an order of magnitude faster but can sometimes provide poor estimates (relative error of 100%). In our tests, LogLog probabilistic counting is not competitive. Experimental validation on the US Census 1990 data set and on the Transaction Processing Performance (TPC H) data set is provided.
Capacity of a Multiple-Antenna Fading Channel with a Quantized Precoding Matrix
Venue: arXiv cs.IT 2009
Year: 2009

Given a multiple-input multiple-output (MIMO) channel, feedback from the receiver can be used to specify a transmit precoding matrix, which selectively activates the strongest channel modes. Here we analyze the performance of Random Vector Quantization (RVQ), in which the precoding matrix is selected from a random codebook containing independent, isotropically distributed entries. We assume that channel elements are i.i.d. and known to the receiver, which relays the optimal (rate-maximizing) precoder codebook index to the transmitter using B bits. We first derive the large system capacity of beamforming (rank-one precoding matrix) as a function of B, where large system refers to the limit as B and the number of transmit and receive antennas all go to infinity with fixed ratios. With beamforming RVQ is asymptotically optimal, i.e., no other quantization scheme can achieve a larger asymptotic rate. The performance of RVQ is also compared with that of a simpler reduced-rank scalar quantization scheme in which the beamformer is constrained to lie in a random subspace. We subsequently consider a precoding matrix with arbitrary rank, and approximate the asymptotic RVQ performance with optimal and linear receivers (matched filter and Minimum Mean Squared Error (MMSE)). Numerical examples show that these approximations accurately predict the performance of finite-size systems of interest. Given a target spectral efficiency, numerical examples show that the amount of feedback required by the linear MMSE receiver is only slightly more than that required by the optimal receiver, whereas the matched filter can require significantly more feedback.
Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
Venue: arXiv cs.CC 2009
Year: 2009

This article belongs to a series on geometric complexity theory (GCT), an approach to the P vs. NP and related problems through algebraic geometry and representation theory. The basic principle behind this approach is called the flip. In essence, it reduces the negative hypothesis in complexity theory (the lower bound problems), such as the P vs. NP problem in characteristic zero, to the positive hypothesis in complexity theory (the upper bound problems): specifically, to showing that the problems of deciding nonvanishing of the fundamental structural constants in representation theory and algebraic geometry, such as the well known plethysm constants--or rather certain relaxed forms of these decision probelms--belong to the complexity class P. In this article, we suggest a plan for implementing the flip, i.e., for showing that these relaxed decision problems belong to P. This is based on the reduction of the preceding complexity-theoretic positive hypotheses to mathematical positivity hypotheses: specifically, to showing that there exist positive formulae--i.e. formulae with nonnegative coefficients--for the structural constants under consideration and certain functions associated with them. These turn out be intimately related to the similar positivity properties of the Kazhdan-Lusztig polynomials and the multiplicative structural constants of the canonical (global crystal) bases in the theory of Drinfeld-Jimbo quantum groups. The known proofs of these positivity properties depend on the Riemann hypothesis over finite fields and the related results. Thus the reduction here, in conjunction with the flip, in essence, says that the validity of the P vs. NP conjecture in characteristic zero is intimately linked to the Riemann hypothesis over finite fields and related problems.
Inapproximability of Maximum Weighted Edge Biclique and Its Applications
Venue: arXiv cs.CC 2009
Year: 2009

Given a bipartite graph $G = (V_1,V_2,E)$ where edges take on {\it both} positive and negative weights from set $\mathcal{S}$, the {\it maximum weighted edge biclique} problem, or $\mathcal{S}$-MWEB for short, asks to find a bipartite subgraph whose sum of edge weights is maximized. This problem has various applications in bioinformatics, machine learning and databases and its (in)approximability remains open. In this paper, we show that for a wide range of choices of $\mathcal{S}$, specifically when $| \frac{\min\mathcal{S}} {\max \mathcal{S}} | \in Ω(η^{δ-1/2}) \cap O(η^{1/2-δ})$ (where $η= \max\{|V_1|, |V_2|\}$, and $δ\in (0,1/2]$), no polynomial time algorithm can approximate $\mathcal{S}$-MWEB within a factor of $n^ε$ for some $ε> 0$ unless $\mathsf{RP = NP}$. This hardness result gives justification of the heuristic approaches adopted for various applied problems in the aforementioned areas, and indicates that good approximation algorithms are unlikely to exist. Specifically, we give two applications by showing that: 1) finding statistically significant biclusters in the SAMBA model, proposed in \cite{Tan02} for the analysis of microarray data, is $n^ε$-inapproximable; and 2) no polynomial time algorithm exists for the Minimum Description Length with Holes problem \cite{Bu05} unless $\mathsf{RP=NP}$.
A Note on the Inapproximability of Correlation Clustering
Venue: arXiv cs.LG 2009
Year: 2009

We consider inapproximability of the correlation clustering problem defined as follows: Given a graph $G = (V,E)$ where each edge is labeled either "+" (similar) or "-" (dissimilar), correlation clustering seeks to partition the vertices into clusters so that the number of pairs correctly (resp. incorrectly) classified with respect to the labels is maximized (resp. minimized). The two complementary problems are called MaxAgree and MinDisagree, respectively, and have been studied on complete graphs, where every edge is labeled, and general graphs, where some edge might not have been labeled. Natural edge-weighted versions of both problems have been studied as well. Let S-MaxAgree denote the weighted problem where all weights are taken from set S, we show that S-MaxAgree with weights bounded by $O(|V|^{1/2-δ})$ essentially belongs to the same hardness class in the following sense: if there is a polynomial time algorithm that approximates S-MaxAgree within a factor of $λ= O(\log{|V|})$ with high probability, then for any choice of S', S'-MaxAgree can be approximated in polynomial time within a factor of $(λ+ ε)$, where $ε> 0$ can be arbitrarily small, with high probability. A similar statement also holds for $S-MinDisagree. This result implies it is hard (assuming $NP \neq RP$) to approximate unweighted MaxAgree within a factor of $80/79-ε$, improving upon a previous known factor of $116/115-ε$ by Charikar et. al. \cite{Chari05}.
Multiple-Description Coding by Dithered Delta-Sigma Quantization
Venue: arXiv cs.IT 2009
Year: 2009

We address the connection between the multiple-description (MD) problem and Delta-Sigma quantization. The inherent redundancy due to oversampling in Delta-Sigma quantization, and the simple linear-additive noise model resulting from dithered lattice quantization, allow us to construct a symmetric and time-invariant MD coding scheme. We show that the use of a noise shaping filter makes it possible to trade off central distortion for side distortion. Asymptotically as the dimension of the lattice vector quantizer and order of the noise shaping filter approach infinity, the entropy rate of the dithered Delta-Sigma quantization scheme approaches the symmetric two-channel MD rate-distortion function for a memoryless Gaussian source and MSE fidelity criterion, at any side-to-central distortion ratio and any resolution. In the optimal scheme, the infinite-order noise shaping filter must be minimum phase and have a piece-wise flat power spectrum with a single jump discontinuity. An important advantage of the proposed design is that it is symmetric in rate and distortion by construction, so the coding rates of the descriptions are identical and there is therefore no need for source splitting.
An approximation trichotomy for Boolean #CSP
Venue: arXiv cs.CC 2009
Year: 2009

We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone IM_2 from Post's lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions in the complexity class #RHΠ_1. This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP.