OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Range Majority Data Structures
Venue: arXiv cs.DS 2012
Year: 2012

Given a set $P$ of coloured points on the real line, we study the problem of answering range $α$-majority (or "heavy hitter") queries on $P$. More specifically, for a query range $Q$, we want to return each colour that is assigned to more than an $α$-fraction of the points contained in $Q$. We present a new data structure for answering range $α$-majority queries on a dynamic set of points, where $α\in (0,1)$. Our data structure uses O(n) space, supports queries in $O((\lg n) / α)$ time, and updates in $O((\lg n) / α)$ amortized time. If the coordinates of the points are integers, then the query time can be improved to $O(\lg n / (α\lg \lg n) + (\lg(1/α))/α))$. For constant values of $α$, this improved query time matches an existing lower bound, for any data structure with polylogarithmic update time. We also generalize our data structure to handle sets of points in d-dimensions, for $d \ge 2$, as well as dynamic arrays, in which each entry is a colour.
The Arbitrarily Varying Multiple-Access Channel with Conferencing Encoders
Venue: arXiv cs.IT 2012
Year: 2012

We derive the capacity region of arbitrarily varying multiple-access channels with conferencing encoders for both deterministic and random coding. For a complete description it is sufficient that one conferencing capacity is positive. We obtain a dichotomy: either the channel's deterministic capacity region is zero or it equals the two-dimensional random coding region. We determine exactly when either case holds. We also discuss the benefits of conferencing. We give the example of an AV-MAC which does not achieve any non-zero rate pair without encoder cooperation, but the two-dimensional random coding capacity region if conferencing is possible. Unlike compound multiple-access channels, arbitrarily varying multiple-access channels may exhibit a discontinuous increase of the capacity region when conferencing in at least one direction is enabled.
Ranking pages and the topology of the web
Venue: arXiv cs.DM 2012
Year: 2012

This paper presents our studies on the rearrangement of links from the structure of websites for the purpose of improving the valuation of a page or group of pages as established by a ranking function as Google's PageRank. We build our topological taxonomy starting from unidirectional and bidirectional rooted trees, and up to more complex hierarchical structures as cyclical rooted trees (obtained by closing cycles on bidirectional trees) and PR--digraph rooted trees (digraphs whose condensation digraph is a rooted tree that behave like cyclical rooted trees). We give different modifications on the structure of these trees and its effect on the valuation given by the PageRank function. We derive closed formulas for the PageRank of the root of various types of trees, and establish a hierarchy of these topologies in terms of PageRank. We show that the PageRank of the root of cyclical and PR--digraph trees basically depends on the number of vertices per level and the number of cycles of distinct lengths among levels, and we give a closed vector formula to compute PageRank.
On the DMT of TDD-SIMO Systems with Channel-Dependent Reverse Channel Training
Venue: arXiv cs.IT 2012
Year: 2012

This paper investigates the Diversity-Multiplexing gain Trade-off (DMT) of a training based reciprocal Single Input Multiple Output (SIMO) system, with (i) perfect Channel State Information (CSI) at the Receiver (CSIR) and noisy CSI at the Transmitter (CSIT), and (ii) noisy CSIR and noisy CSIT. In both the cases, the CSIT is acquired through Reverse Channel Training (RCT), i.e., by sending a training sequence from the receiver to the transmitter. A channel-dependent fixed-power training scheme is proposed for acquiring CSIT, along with a forward-link data transmit power control scheme. With perfect CSIR, the proposed scheme is shown to achieve a diversity order that is quadratically increasing with the number of receive antennas. This is in contrast with conventional orthogonal RCT schemes, where the diversity order is known to saturate as the number of receive antennas is increased, for a given channel coherence time. Moreover, the proposed scheme can achieve a larger DMT compared to the orthogonal training scheme. With noisy CSIR and noisy CSIT, a three-way training scheme is proposed and its DMT performance is analyzed. It is shown that nearly the same diversity order is achievable as in the perfect CSIR case. The time-overhead in the training schemes is explicitly accounted for in this work, and the results show that the proposed channel-dependent RCT and data power control schemes offer a significant improvement in terms of the DMT, compared to channel-agnostic orthogonal RCT schemes. The outage performance of the proposed scheme is illustrated through Monte-Carlo simulations.
Hierarchical Recursive Running Median
Venue: arXiv cs.DS 2012
Year: 2012

To date, the histogram-based running median filter of Perreault and Hébert is considered the fastest for 8-bit images, being roughly O(1) in average case. We present here another approximately constant time algorithm which further improves the aforementioned one and exhibits lower associated constant, being at the time of writing the lowest theoretical complexity algorithm for calculation of 2D and higher dimensional median filters. The algorithm scales naturally to higher precision (e.g. 16-bit) integer data without any modifications. Its adaptive version offers additional speed-up for images showing compact modes in gray-value distribution. The experimental comparison to the previous constant-time algorithm defines the application domain of this new development, besides theoretical interest, as high bit depth data and/or hardware without SIMD extensions. The C/C++ implementation of the algorithm is available under GPL for research purposes.
A novel parallel algorithm for Gaussian Elimination of sparse unsymmetric matrices
Venue: arXiv cs.MS 2012
Year: 2012

We describe a new algorithm for Gaussian Elimination suitable for general (unsymmetric and possibly singular) sparse matrices, of any entry type, which has a natural parallel and distributed-memory formulation but degrades gracefully to sequential execution. We present a sample MPI implementation of a program computing the rank of a sparse integer matrix using the proposed algorithm. Some preliminary performance measurements are presented and discussed, and the performance of the algorithm is compared to corresponding state-of-the-art algorithms for floating-point and integer matrices.
Deciding Kleene Algebras in Coq
Venue: arXiv cs.LO 2012
Year: 2012

We present a reflexive tactic for deciding the equational theory of Kleene algebras in the Coq proof assistant. This tactic relies on a careful implementation of efficient finite automata algorithms, so that it solves casual equations instantaneously and properly scales to larger expressions. The decision procedure is proved correct and complete: correctness is established w.r.t. any model by formalising Kozen's initiality theorem; a counter-example is returned when the given equation does not hold. The correctness proof is challenging: it involves both a precise analysis of the underlying automata algorithms and a lot of algebraic reasoning. In particular, we have to formalise the theory of matrices over a Kleene algebra. We build on the recent addition of firstorder typeclasses in Coq in order to work efficiently with the involved algebraic structures.
Exchanging Secrets without Using Cryptography
Venue: arXiv cs.CR 2012
Year: 2012

We consider the problem where a group of n nodes, connected to the same broadcast channel (e.g., a wireless network), want to generate a common secret bitstream, in the presence of an adversary Eve, who tries to obtain information on the bitstream. We assume that the nodes initially share a (small) piece of information, but do not have access to any out-of-band channel. We ask the question: can this problem be solved without relying on Eve's computational limitations, i.e., without using any form of public-key cryptography? We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct with very high probability. In this task, the nodes are assisted by a small number of interferers, whose role is to create channel noise in a way that bounds the amount of information Eve can overhear. Our protocol has polynomial-time complexity and requires no changes to the physical or MAC layer of network devices. First, we formally show that, under standard theoretical assumptions, our protocol is information-theoretically secure, achieves optimal secret-generation rate for n = 2 nodes, and scales well to an arbitrary number of nodes. Second, we adapt our protocol to a small wireless 14-square-meter testbed; we experimentally show that, if Eve uses a standard wireless physical layer and is not too close to any of the nodes, 8 nodes can achieve a secret-generation rate of 38 Kbps. To the best of our knowledge, ours is the first experimental demonstration of information-theoretic secret exchange on a wireless network at a rate beyond a few tens of bits per second.
RASID: A Robust WLAN Device-free Passive Motion Detection System
Venue: arXiv cs.NI 2012
Year: 2012

WLAN Device-free passive DfP indoor localization is an emerging technology enabling the localization of entities that do not carry any devices nor participate actively in the localization process using the already installed wireless infrastructure. This technology is useful for a variety of applications such as intrusion detection, smart homes and border protection. We present the design, implementation and evaluation of RASID, a DfP system for human motion detection. RASID combines different modules for statistical anomaly detection while adapting to changes in the environment to provide accurate, robust, and low-overhead detection of human activities using standard WiFi hardware. Evaluation of the system in two different testbeds shows that it can achieve an accurate detection capability in both environments with an F-measure of at least 0.93. In addition, the high accuracy and low overhead performance are robust to changes in the environment as compared to the current state of the art DfP detection systems. We also relay the lessons learned during building our system and discuss future research directions.
Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
Venue: arXiv cs.GT 2012
Year: 2012

For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any setting which roughly satisfies the following assumptions: (i) buyers' types must be distributed independently (not necessarily identically), (ii) objective function must be linearly separable over the buyers, and (iii) except for the supply constraints, there should be no other inter-buyer constraints. Our framework is general in the sense that it makes no explicit assumption about buyers' valuations, type distributions, and single buyer constraints (e.g., budget, incentive compatibility, etc). We present two generic multi buyer mechanisms which use single buyer mechanisms as black boxes; if an $α$-approximate single buyer mechanism can be constructed for each buyer, and if no buyer requires more than $\frac{1}{k}$ of all units of each item, then our generic multi buyer mechanisms are $γ_kα$-approximation of the optimal multi buyer mechanism, where $γ_k$ is a constant which is at least $1-\frac{1}{\sqrt{k+3}}$. Observe that $γ_k$ is at least 1/2 (for $k=1$) and approaches 1 as $k \to \infty$. As a byproduct of our construction, we present a generalization of prophet inequalities. Furthermore, as applications of our framework, we present multi buyer mechanisms with improved approximation factor for several settings from the literature.
Analysis of cubic permutation polynomials for turbo codes
Venue: arXiv cs.IT 2012
Year: 2012

Quadratic permutation polynomials (QPPs) have been widely studied and used as interleavers in turbo codes. However, less attention has been given to cubic permutation polynomials (CPPs). This paper proves a theorem which states sufficient and necessary conditions for a cubic permutation polynomial to be a null permutation polynomial. The result is used to reduce the search complexity of CPP interleavers for short lengths (multiples of 8, between 40 and 352), by improving the distance spectrum over the set of polynomials with the largest spreading factor. The comparison with QPP interleavers is made in terms of search complexity and upper bounds of the bit error rate (BER) and frame error rate (FER) for AWGN and for independent fading Rayleigh channels. Cubic permutation polynomials leading to better performance than quadratic permutation polynomials are found for some lengths.
Cut-Free ExpTime Tableaux for Checking Satisfiability of a Knowledge Base in the Description Logic SHI
Venue: arXiv cs.LO 2012
Year: 2012

We give the first cut-free ExpTime (optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic SHI, which extends the description logic ALC with transitive roles, inverse roles and role hierarchies.
Viewpoint: Journals for Certification, Conferences for Rapid Dissemination
Venue: arXiv cs.DL 2012
Year: 2012

The publication culture in Computer Science is different from that of all other disciplines. Whereas other disciplines focus on journal publication, the standard practice in CS has been to publish in a conference and then (sometimes) publish a journal version of the conference paper. We discuss the role of journal publication in CS. Indeed, it is through publication in selective, leading conferences that the quality of CS research is typically assessed.
Learning XML Twig Queries
Venue: arXiv cs.DB 2012
Year: 2012

We investigate the problem of learning XML queries, path queries and tree pattern queries, from examples given by the user. A learning algorithm takes on the input a set of XML documents with nodes annotated by the user and returns a query that selects the nodes in a manner consistent with the annotation. We study two learning settings that differ with the types of annotations. In the first setting the user may only indicate required nodes that the query must return. In the second, more general, setting, the user may also indicate forbidden nodes that the query must not return. The query may or may not return any node with no annotation. We formalize what it means for a class of queries to be \emph{learnable}. One requirement is the existence of a learning algorithm that is sound i.e., always returns a query consistent with the examples given by the user. Furthermore, the learning algorithm should be complete i.e., able to produce every query with a sufficiently rich example. Other requirements involve tractability of learning and its robustness to nonessential examples. We show that the classes of simple path queries and path-subsumption-free tree queries are learnable from positive examples. The learnability of the full class of tree pattern queries (and the full class of path queries) remains an open question. We show also that adding negative examples to the picture renders the learning unfeasible. Published in ICDT 2012, Berlin.
On the behaviours produced by instruction sequences under execution
Venue: arXiv cs.PL 2012
Year: 2012

We study several aspects of the behaviours produced by instruction sequences under execution in the setting of the algebraic theory of processes known as ACP. We use ACP to describe the behaviours produced by instruction sequences under execution and to describe two protocols implementing these behaviours in the case where the processing of instructions takes place remotely. We also show that all finite-state behaviours considered in ACP can be produced by instruction sequences under execution.
Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method
Venue: arXiv cs.CC 2012
Year: 2012

We give new improvements to the Chudnovsky-Chudnovsky method that provides upper bounds on the bilinear complexity of multiplication in extensions of finite fields through interpolation on algebraic curves. Our approach features three independent key ingredients: (1) We allow asymmetry in the interpolation procedure. This allows to prove, via the usual cardinality argument, the existence of auxiliary divisors needed for the bounds, up to optimal degree. (2) We give an alternative proof for the existence of these auxiliary divisors, which is constructive, and works also in the symmetric case, although it requires the curves to have sufficiently many points. (3) We allow the method to deal not only with extensions of finite fields, but more generally with monogenous algebras over finite fields. This leads to sharper bounds, and is designed also to combine well with base field descent arguments in case the curves do not have sufficiently many points. As a main application of these techniques, we fix errors in, improve, and generalize, previous works of Shparlinski-Tsfasman-Vladut, Ballet, and Cenk-Ozbudak. Besides, generalities on interpolation systems, as well as on symmetric and asymmetric bilinear complexity, are also discussed.
Approximating Minimum Manhattan Networks in Higher Dimensions
Venue: arXiv cs.CG 2012
Year: 2012

We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called \emph{terminals} in $\R^d$, find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair's Manhattan (that is, $L_1$-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless ${\cal P}={\cal NP}$). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension $d$ and any $\eps>0$, an $O(n^\eps)$-approximation algorithm. For 3D, we also give a $4(k-1)$-approximation algorithm for the case that the terminals are contained in the union of $k \ge 2$ parallel planes.
Intuitionistic implication makes model checking hard
Venue: arXiv cs.CC 2012
Year: 2012

We investigate the complexity of the model checking problem for intuitionistic and modal propositional logics over transitive Kripke models. More specific, we consider intuitionistic logic IPC, basic propositional logic BPL, formal propositional logic FPL, and Jankov's logic KC. We show that the model checking problem is P-complete for the implicational fragments of all these intuitionistic logics. For BPL and FPL we reach P-hardness even on the implicational fragment with only one variable. The same hardness results are obtained for the strictly implicational fragments of their modal companions. Moreover, we investigate whether formulas with less variables and additional connectives make model checking easier. Whereas for variable free formulas outside of the implicational fragment, FPL model checking is shown to be in LOGCFL, the problem remains P-complete for BPL.
Budget Feasible Mechanism Design via Random Sampling
Venue: arXiv cs.GT 2012
Year: 2012

Budget feasible mechanism considers algorithmic mechanism design questions where there is a budget constraint on the total payment of the mechanism. An important question in the field is that under which valuation domains there exist budget feasible mechanisms that admit `small' approximations (compared to a socially optimal solution). Singer \cite{PS10} showed that additive and submodular functions admit a constant approximation mechanism. Recently, Dobzinski, Papadimitriou, and Singer \cite{DPS11} gave an $O(\log^2n)$ approximation mechanism for subadditive functions and remarked that: "A fundamental question is whether, regardless of computational constraints, a constant-factor budget feasible mechanism exists for subadditive function." In this paper, we give the first attempt to this question. We give a polynomial time $O(\frac{\log n}{\log\log n})$ sub-logarithmic approximation ratio mechanism for subadditive functions, improving the best known ratio $O(\log^2 n)$. Further, we connect budget feasible mechanism design to the concept of approximate core in cooperative game theory, and show that there is a mechanism for subadditive functions whose approximation is, via a characterization of the integrality gap of a linear program, linear to the largest value to which an approximate core exists. Our result implies in particular that the class of XOS functions, which is a superclass of submodular functions, admits a constant approximation mechanism. We believe that our work could be a solid step towards solving the above fundamental problem eventually, and possibly, with an affirmative answer.
On the Computational Complexity of Stochastic Controller Optimization in POMDPs
Venue: arXiv cs.CC 2012
Year: 2012

We show that the problem of finding an optimal stochastic 'blind' controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard, in PSPACE, and SQRT-SUM-hard, hence placing it in NP would imply breakthroughs in long-standing open problems in computer science. Our result establishes that the more general problem of stochastic controller optimization in POMDPs is also NP-hard. Nonetheless, we outline a special case that is convex and admits efficient global solutions.
Exploiting Channel Diversity in Secret Key Generation from Multipath Fading Randomness
Venue: arXiv cs.CR 2012
Year: 2012

We design and analyze a method to extract secret keys from the randomness inherent to wireless channels. We study a channel model for multipath wireless channel and exploit the channel diversity in generating secret key bits. We compare the key extraction methods based both on entire channel state information (CSI) and on single channel parameter such as the received signal strength indicators (RSSI). Due to the reduction in the degree-of-freedom when going from CSI to RSSI, the rate of key extraction based on CSI is far higher than that based on RSSI. This suggests that exploiting channel diversity and making CSI information available to higher layers would greatly benefit the secret key generation. We propose a key generation system based on low-density parity-check (LDPC) codes and describe the design and performance of two systems: one based on binary LDPC codes and the other (useful at higher signal-to-noise ratios) based on four-ary LDPC codes.
Annotating Simplices with a Homology Basis and Its Applications
Venue: arXiv cs.CG 2012
Year: 2012

Let $K$ be a simplicial complex and $g$ the rank of its $p$-th homology group $H_p(K)$ defined with $Z_2$ coefficients. We show that we can compute a basis $H$ of $H_p(K)$ and annotate each $p$-simplex of $K$ with a binary vector of length $g$ with the following property: the annotations, summed over all $p$-simplices in any $p$-cycle $z$, provide the coordinate vector of the homology class $[z]$ in the basis $H$. The basis and the annotations for all simplices can be computed in $O(n^ω)$ time, where $n$ is the size of $K$ and $ω<2.376$ is a quantity so that two $n\times n$ matrices can be multiplied in $O(n^ω)$ time. The pre-computation of annotations permits answering queries about the independence or the triviality of $p$-cycles efficiently. Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1-dimensional homology. Specifically, for computing an optimal basis of $H_1(K)$, we improve the time complexity known for the problem from $O(n^4)$ to $O(n^ω+n^2g^{ω-1})$. Here $n$ denotes the size of the 2-skeleton of $K$ and $g$ the rank of $H_1(K)$. Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking $2^{O(g)}n\log n$ time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in $O(n^ω)+2^{O(g)}n^2\log n$ time using annotations.