OpenRaiser/Intern-Atlas huggingface dataset:
Inverse Determinant Sums and Connections Between Fading Channel Information Theory and Algebra
Venue: arXiv cs.IT 2013
Year: 2013

This work concentrates on the study of inverse determinant sums, which arise from the union bound on the error probability, as a tool for designing and analyzing algebraic space-time block codes. A general framework to study these sums is established, and the connection between asymptotic growth of inverse determinant sums and the diversity-multiplexing gain trade-off is investigated. It is proven that the growth of the inverse determinant sum of a division algebra-based space-time code is completely determined by the growth of the unit group. This reduces the inverse determinant sum analysis to studying certain asymptotic integrals in Lie groups. Using recent methods from ergodic theory, a complete classification of the inverse determinant sums of the most well known algebraic space-time codes is provided. The approach reveals an interesting and tight relation between diversity-multiplexing gain trade-off and point counting in Lie groups.
A Constrained Coding Approach to Error-Free Half-Duplex Relay Networks
Venue: arXiv cs.IT 2013
Year: 2013

We show that the broadcast capacity of an infinite-depth tree-structured network of error-free half-duplex-constrained relays can be achieved using constrained coding at the source and symbol forwarding at the relays.
A new proof to complexity of dual basis of a type I optimal normal basis
Venue: arXiv cs.DM 2013
Year: 2013

The complexity of dual basis of a type I optimal normal basis of $\mathbb{F}_{q^n}$ over $\mathbb{F}_{q}$ was determined to be $3n-3$ or $3n-2$ according as $q$ is even or odd, respectively, by Z.-X. Wan and K. Zhou in 2007. We give a new proof to this result by clearly deriving the dual of a type I optimal normal basis with the aid of a lemma on the dual of a polynomial basis.
Max-Cut Parameterized Above the Edwards-Erdős Bound
Venue: arXiv cs.DS 2013
Year: 2013

We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut above the Edwards-Erdős bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size m/2 + (n-1)/4 + k in time 2^O(k)n^4, or decides that no such cut exists. This answers a long-standing open question from parameterized complexity that has been posed several times over the past 15 years. Our algorithm is asymptotically optimal, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size.
Subexponential fixed-parameter tractability of cluster editing
Venue: arXiv cs.CC 2013
Year: 2013

In the Correlation Clustering, also known as Cluster Editing, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k edges. We give a subexponential algorithm that, in time 2^O(sqrt(pk)) + n^O(1) decides whether G can be transformed into a cluster graph with p cliques by changing at most k adjacencies. We complement our algorithmic findings by the following tight lower bounds on the asymptotic behaviour of our algorithm. We show that, unless ETH fails, for any constant 0 < s <= 1, there is p = Theta(k^s) such that there is no algorithm deciding in time 2^o(sqrt(pk)) n^O(1) whether G can be transformed into a cluster graph with p cliques by changing at most k adjacencies.
Reliability Analysis of Electric Power Systems Using an Object-oriented Hybrid Modeling Approach
Venue: arXiv cs.SY 2013
Year: 2013

The ongoing evolution of the electric power systems brings about the need to cope with increasingly complex interactions of technical components and relevant actors. In order to integrate a more comprehensive spectrum of different aspects into a probabilistic reliability assessment and to include time-dependent effects, this paper proposes an object-oriented hybrid approach combining agent-based modeling techniques with classical methods such as Monte Carlo simulation. Objects represent both technical components such as generators and transmission lines and non-technical components such as grid operators. The approach allows the calculation of conventional reliability indices and the estimation of blackout frequencies. Furthermore, the influence of the time needed to remove line overloads on the overall system reliability can be assessed. The applicability of the approach is demonstrated by performing simulations on the IEEE Reliability Test System 1996 and on a model of the Swiss high-voltage grid.
There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem
Venue: arXiv cs.DS 2013
Year: 2013

The sudoku minimum number of clues problem is the following question: what is the smallest number of clues that a sudoku puzzle can have? For several years it had been conjectured that the answer is 17. We have performed an exhaustive computer search for 16-clue sudoku puzzles, and did not find any, thus proving that the answer is indeed 17. In this article we describe our method and the actual search. As a part of this project we developed a novel way for enumerating hitting sets. The hitting set problem is computationally hard; it is one of Karp's 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today's supercomputer speeds. To make an exhaustive search possible, we designed an algorithm that allowed us to efficiently enumerate hitting sets of a suitable size.
An Enhanced DMT-optimality Criterion for STBC-schemes for Asymmetric MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

For any $n_t$ transmit, $n_r$ receive antenna ($n_t\times n_r$) MIMO system in a quasi-static Rayleigh fading environment, it was shown by Elia et al. that linear space-time block code-schemes (LSTBC-schemes) which have the non-vanishing determinant (NVD) property are diversity-multiplexing gain tradeoff (DMT)-optimal for arbitrary values of $n_r$ if they have a code-rate of $n_t$ complex dimensions per channel use. However, for asymmetric MIMO systems (where $n_r < n_t$), with the exception of a few LSTBC-schemes, it is unknown whether general LSTBC-schemes with NVD and a code-rate of $n_r$ complex dimensions per channel use are DMT-optimal. In this paper, an enhanced sufficient criterion for any STBC-scheme to be DMT-optimal is obtained, and using this criterion, it is established that any LSTBC-scheme with NVD and a code-rate of $\min\{n_t,n_r\}$ complex dimensions per channel use is DMT-optimal. This result settles the DMT-optimality of several well-known, low-ML-decoding-complexity LSTBC-schemes for certain asymmetric MIMO systems.
A Faster Algorithm for Solving One-Clock Priced Timed Games
Venue: arXiv cs.GT 2013
Year: 2013

One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12^n n^(O(1)), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2^(O(n^2+m)), due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.
A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction
Venue: arXiv cs.GT 2013
Year: 2013

The bi-objective winner determination problem (2WDP-SC) of a combinatorial procurement auction for transport contracts is characterized by a set B of bundle bids, with each bundle bid b in B consisting of a bidding carrier c_b, a bid price p_b, and a set tau_b transport contracts which is a subset of the set T of tendered transport contracts. Additionally, the transport quality q_{t,c_b} is given which is expected to be realized when a transport contract t is executed by a carrier c_b. The task of the auctioneer is to find a set X of winning bids (X subset B), such that each transport contract is part of at least one winning bid, the total procurement costs are minimized, and the total transport quality is maximized. This article presents a metaheuristic approach for the 2WDP-SC which integrates the greedy randomized adaptive search procedure with a two-stage candidate component selection procedure, large neighborhood search, and self-adaptive parameter setting in order to find a competitive set of non-dominated solutions. The heuristic outperforms all existing approaches. For seven small benchmark instances, the heuristic is the sole approach that finds all Pareto-optimal solutions. For 28 out of 30 large instances, none of the existing approaches is able to compute a solution that dominates a solution found by the proposed heuristic.
Timely Throughput of Heterogeneous Wireless Networks: Fundamental Limits and Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

The proliferation of different wireless access technologies, together with the growing number of multi-radio wireless devices suggest that the opportunistic utilization of multiple connections at the users can be an effective solution to the phenomenal growth of traffic demand in wireless networks. In this paper we consider the downlink of a wireless network with $N$ Access Points (AP's) and $M$ clients, where each client is connected to several out-of-band AP's, and requests delay-sensitive traffic (e.g., real-time video). We adopt the framework of Hou, Borkar, and Kumar, and study the maximum total timely throughput of the network, denoted by $C_{T^3}$, which is the maximum average number of packets delivered successfully before their deadline. Solving this problem is challenging since even the number of different ways of assigning packets to the AP's is $N^M$. We overcome the challenge by proposing a deterministic relaxation of the problem, which converts the problem to a network with deterministic delays in each link. We show that the additive gap between the capacity of the relaxed problem, denoted by $C_{det}$, and $C_{T^3}$ is bounded by $2\sqrt{N(C_{det}+N/4)}$, which is asymptotically negligible compared to $C_{det}$, when the network is operating at high-throughput regime. In addition, our numerical results show that the actual gap between $C_{T^3}$ and $C_{det}$ is in most cases much less than the worst-case gap proven analytically. Moreover, using LP rounding methods we prove that the relaxed problem can be approximated within additive gap of $N$. We extend the analytical results to the case of time-varying channel states, real-time traffic, prioritized traffic, and optimal online policies. Finally, we generalize the model for deterministic relaxation to consider fading, rate adaptation, and multiple simultaneous transmissions.
The thermodynamic cost of fast thought
Venue: arXiv cs.AI 2013
Year: 2013

After more than sixty years, Shannon's research [1-3] continues to raise fundamental questions, such as the one formulated by Luce [4,5], which is still unanswered: "Why is information theory not very applicable to psychological problems, despite apparent similarities of concepts?" On this topic, Pinker [6], one of the foremost defenders of the computational theory of mind [6], has argued that thought is simply a type of computation, and that the gap between human cognition and computational models may be illusory. In this context, in his latest book, titled Thinking Fast and Slow [8], Kahneman [7,8] provides further theoretical interpretation by differentiating the two assumed systems of the cognitive functioning of the human mind. He calls them intuition (system 1) determined to be an associative (automatic, fast and perceptual) machine, and reasoning (system 2) required to be voluntary and to operate logical- deductively. In this paper, we propose an ansatz inspired by Ausubel's learning theory for investigating, from the constructivist perspective [9-12], information processing in the working memory of cognizers. Specifically, a thought experiment is performed utilizing the mind of a dual-natured creature known as Maxwell's demon: a tiny "man-machine" solely equipped with the characteristics of system 1, which prevents it from reasoning. The calculation presented here shows that [...]. This result indicates that when the system 2 is shut down, both an intelligent being, as well as a binary machine, incur the same energy cost per unit of information processed, which mathematically proves the computational attribute of the system 1, as Kahneman [7,8] theorized. This finding links information theory to human psychological features and opens a new path toward the conception of a multi-bit reasoning machine.
A Graph Theoretical Approach to Network Encoding Complexity
Venue: arXiv cs.IT 2013
Year: 2013

Consider an acyclic directed network $G$ with sources $S_1, S_2,..., S_l$ and distinct sinks $R_1, R_2,..., R_l$. For $i=1, 2,..., l$, let $c_i$ denote the min-cut between $S_i$ and $R_i$. Then, by Menger's theorem, there exists a group of $c_i$ edge-disjoint paths from $S_i$ to $R_i$, which will be referred to as a group of Menger's paths from $S_i$ to $R_i$ in this paper. Although within the same group they are edge-disjoint, the Menger's paths from different groups may have to merge with each other. It is known that by choosing Menger's paths appropriately, the number of mergings among different groups of Menger's paths is always bounded by a constant, which is independent of the size and the topology of $G$. The tightest such constant for the all the above-mentioned networks is denoted by $\mathcal{M}(c_1, c_2,..., c_2)$ when all $S_i$'s are distinct, and by $\mathcal{M}^*(c_1, c_2,..., c_2)$ when all $S_i$'s are in fact identical. It turns out that $\mathcal{M}$ and $\mathcal{M}^*$ are closely related to the network encoding complexity for a variety of networks, such as multicast networks, two-way networks and networks with multiple sessions of unicast. Using this connection, we compute in this paper some exact values and bounds in network encoding complexity using a graph theoretical approach.
Beyond Sentiment: The Manifold of Human Emotions
Venue: arXiv cs.CL 2013
Year: 2013

Sentiment analysis predicts the presence of positive or negative emotions in a text document. In this paper we consider higher dimensional extensions of the sentiment concept, which represent a richer set of human emotions. Our approach goes beyond previous work in that our model contains a continuous manifold rather than a finite set of human emotions. We investigate the resulting model, compare it to psychological observations, and explore its predictive capabilities. Besides obtaining significant improvements over a baseline without manifold, we are also able to visualize different notions of positive sentiment in different domains.
Near-optimal Coresets For Least-Squares Regression
Venue: arXiv cs.DS 2013
Year: 2013

We study (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to compute a good approximate solution to the regression. We give deterministic, low order polynomial-time algorithms to construct such coresets with approximation guarantees, together with lower bounds indicating that there is not much room for improvement upon our results.
Refinement Modal Logic
Venue: arXiv cs.LO 2013
Year: 2013

In this paper we present {\em refinement modal logic}. A refinement is like a bisimulation, except that from the three relational requirements only `atoms' and `back' need to be satisfied. Our logic contains a new operator 'all' in addition to the standard modalities 'box' for each agent. The operator 'all' acts as a quantifier over the set of all refinements of a given model. As a variation on a bisimulation quantifier, this refinement operator or refinement quantifier 'all' can be seen as quantifying over a variable not occurring in the formula bound by it. The logic combines the simplicity of multi-agent modal logic with some powers of monadic second-order quantification. We present a sound and complete axiomatization of multi-agent refinement modal logic. We also present an extension of the logic to the modal mu-calculus, and an axiomatization for the single-agent version of this logic. Examples and applications are also discussed: to software verification and design (the set of agents can also be seen as a set of actions), and to dynamic epistemic logic. We further give detailed results on the complexity of satisfiability, and on succinctness.
Combinatorial limitations of average-radius list-decoding
Venue: arXiv cs.IT 2013
Year: 2013

We study certain combinatorial aspects of list-decoding, motivated by the exponential gap between the known upper bound (of $O(1/γ)$) and lower bound (of $Ω_p(\log (1/γ))$) for the list-size needed to decode up to radius $p$ with rate $γ$ away from capacity, i.e., $1-\h(p)-γ$ (here $p\in (0,1/2)$ and $γ> 0$). Our main result is the following: We prove that in any binary code $C \subseteq \{0,1\}^n$ of rate $1-\h(p)-γ$, there must exist a set $\mathcal{L} \subset C$ of $Ω_p(1/\sqrtγ)$ codewords such that the average distance of the points in $\mathcal{L}$ from their centroid is at most $pn$. In other words, there must exist $Ω_p(1/\sqrtγ)$ codewords with low "average radius." The standard notion of list-decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average-radius form is in itself quite natural and is implied by the classical Johnson bound. The remaining results concern the standard notion of list-decoding, and help clarify the combinatorial landscape of list-decoding: 1. We give a short simple proof, over all fixed alphabets, of the above-mentioned $Ω_p(\log (γ))$ lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. 2. We show that one {\em cannot} improve the $Ω_p(\log (1/γ))$ lower bound via techniques based on identifying the zero-rate regime for list decoding of constant-weight codes. 3. We show a "reverse connection" showing that constant-weight codes for list decoding imply general codes for list decoding with higher rate. 4. We give simple second moment based proofs of tight (up to constant factors) lower bounds on the list-size needed for list decoding random codes and random linear codes from errors as well as erasures.
(Dual) Hoops Have Unique Halving
Venue: arXiv cs.AI 2013
Year: 2013

Continuous logic extends the multi-valued Lukasiewicz logic by adding a halving operator on propositions. This extension is designed to give a more satisfactory model theory for continuous structures. The semantics of these logics can be given using specialisations of algebraic structures known as hoops. As part of an investigation into the metatheory of propositional continuous logic, we were indebted to Prover9 for finding a proof of an important algebraic law.
Fluid Model Checking
Venue: arXiv cs.LO 2013
Year: 2013

In this paper we investigate a potential use of fluid approximation techniques in the context of stochastic model checking of CSL formulae. We focus on properties describing the behaviour of a single agent in a (large) population of agents, exploiting a limit result known also as fast simulation. In particular, we will approximate the behaviour of a single agent with a time-inhomogeneous CTMC which depends on the environment and on the other agents only through the solution of the fluid differential equation. We will prove the asymptotic correctness of our approach in terms of satisfiability of CSL formulae and of reachability probabilities. We will also present a procedure to model check time-inhomogeneous CTMC against CSL formulae.
Analytical Modeling of Uplink Cellular Networks
Venue: arXiv cs.IT 2013
Year: 2013

Cellular uplink analysis has typically been undertaken by either a simple approach that lumps all interference into a single deterministic or random parameter in a Wyner-type model, or via complex system level simulations that often do not provide insight into why various trends are observed. This paper proposes a novel middle way using point processes that is both accurate and also results in easy-to-evaluate integral expressions based on the Laplace transform of the interference. We assume mobiles and base stations are randomly placed in the network with each mobile pairing up to its closest base station. Compared to related recent work on downlink analysis, the proposed uplink model differs in two key features. First, dependence is considered between user and base station point processes to make sure each base station serves a single mobile in the given resource block. Second, per-mobile power control is included, which further couples the transmission of mobiles due to location-dependent channel inversion. Nevertheless, we succeed in deriving the coverage (equivalently outage) probability of a typical link in the network. This model can be used to address a wide variety of system design questions in the future. In this paper we focus on the implications for power control and see that partial channel inversion should be used at low signal-to-interference-plus-noise ratio (SINR), while full power transmission is optimal at higher SINR.
Retrieval of Sparse Solutions of Multiple-Measurement Vectors via Zero-point Attracting Projection
Venue: arXiv cs.IT 2013
Year: 2013

A new sparse signal recovery algorithm for multiple-measurement vectors (MMV) problem is proposed in this paper. The sparse representation is iteratively drawn based on the idea of zero-point attracting projection (ZAP). In each iteration, the solution is first updated along the negative gradient direction of an approximate $\ell_{2,0}$ norm to encourage sparsity, and then projected to the solution space to satisfy the under-determined equation. A variable step size scheme is adopted further to accelerate the convergence as well as to improve the recovery accuracy. Numerical simulations demonstrate that the performance of the proposed algorithm exceeds the references in various aspects, as well as when applied to the Modulated Wideband Converter, where recovering MMV problem is crucial to its performance.
Remarks on low weight codewords of generalized affine and projective Reed-Muller codes
Venue: arXiv cs.IT 2013
Year: 2013

We propose new results on low weight codewords of affine and projective generalized Reed-Muller codes. In the affine case we prove that if the size of the working finite field is large compared to the degree of the code, the low weight codewords are products of affine functions. Then in the general case we study some types of codewords and prove that they cannot be second, thirds or fourth weight depending on the hypothesis. In the projective case the second distance of generalized Reed-Muller codes is estimated, namely a lower bound and an upper bound of this weight are given.
A Pseudo Random Number Generator from Chaos
Venue: arXiv cs.DM 2013
Year: 2013

A random number generator is proposed based on a theorem about existence of chaos in fixed point iteration of x= cot2(x). Digital computer simulation of this function iteration exhibits random behavior. A method is proposed to extract random bytes from this simulation. Diehard and NIST test suite for randomness detection is run on this bytes, and it is found to pass all the tests in the suite. Thus, this method qualifies even for cryptographic quality random number generation.