OpenRaiser/Intern-Atlas huggingface dataset:
Equalized Time Reversal Beamforming for Indoor Wireless Communications
Venue: arXiv cs.NI 2017
Year: 2017

Time-reversal (TR) is a beamforming technique for frequency-selective channels, which has received increasing attention due to its high energy efficiency and low computational complexity for wireless communications. In this paper, we present two contributions on time-reversal (TR) wireless beamforming for single-user indoor wideband MISO systems. First, we provide novel analyses of a baseband TR system using two commonly used indoor propagation channel models. We derive closed-form approximations for the inter-symbol interference (ISI) with these channel models in order to characterize the influence of propagation conditions (such as the power-delay profile, delay spread, and bandwidth) on TR performance metrics. In particular, we analyze spatial focusing and time compression performance of TR beamforming, and their impact on the bit error rate (BER). As a second contribution, we introduce an equalized TR (ETR) technique that mitigates the ISI of conventional TR. The proposed ETR utilizes a zero-forcing pre-equalizer at the transmitter in a cascade configuration with the TR pre-filter. Unlike previous approaches to ISI mitigation in TR systems, we derive theoretical performance bounds for ETR and show that it greatly enhances the BER performance of conventional TR with minimal impact to its beamforming capabilities. By means of numerical simulations, we verify our closed-form approximations and show that the proposed ETR technique outperforms conventional TR with respect to the BER under any SNR.
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Venue: arXiv cs.CC 2017
Year: 2017

The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. The problem of computing the edit distance between two strings is a classical computational task, with a well-known algorithm based on dynamic programming. Unfortunately, all known algorithms for this problem run in nearly quadratic time. In this paper we provide evidence that the near-quadratic running time bounds known for the problem of computing edit distance might be tight. Specifically, we show that, if the edit distance can be computed in time $O(n^{2-δ})$ for some constant $δ>0$, then the satisfiability of conjunctive normal form formulas with $N$ variables and $M$ clauses can be solved in time $M^{O(1)} 2^{(1-ε)N}$ for a constant $ε>0$. The latter result would violate the Strong Exponential Time Hypothesis, which postulates that such algorithms do not exist.
Path Checking for MTL and TPTL over Data Words
Venue: arXiv cs.LO 2017
Year: 2017

Metric temporal logic (MTL) and timed propositional temporal logic (TPTL) are quantitative extensions of linear temporal logic, which are prominent and widely used in the verification of real-timed systems. It was recently shown that the path checking problem for MTL, when evaluated over finite timed words, is in the parallel complexity class NC. In this paper, we derive precise complexity results for the path-checking problem for MTL and TPTL when evaluated over infinite data words over the non-negative integers. Such words may be seen as the behaviours of one-counter machines. For this setting, we give a complete analysis of the complexity of the path-checking problem depending on the number of register variables and the encoding of constraint numbers (unary or binary). As the two main results, we prove that the path-checking problem for MTL is P-complete, whereas the path-checking problem for TPTL is PSPACE-complete. The results yield the precise complexity of model checking deterministic one-counter machines against formulae of MTL and TPTL.
How Much Lookahead is Needed to Win Infinite Games?
Venue: arXiv cs.GT 2017
Year: 2017

Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent's moves. For $ω$-regular winning conditions it is known that such games can be solved in doubly-exponential time and that doubly-exponential lookahead is sufficient. We improve upon both results by giving an exponential time algorithm and an exponential upper bound on the necessary lookahead. This is complemented by showing EXPTIME-hardness of the solution problem and tight exponential lower bounds on the lookahead. Both lower bounds already hold for safety conditions. Furthermore, solving delay games with reachability conditions is shown to be PSPACE-complete. This is a corrected version of the paper https://arxiv.org/abs/1412.3701v4 published originally on August 26, 2016.
Max-Product Belief Propagation for Linear Programming: Applications to Combinatorial Optimization
Venue: arXiv cs.AI 2017
Year: 2017

The max-product {belief propagation} (BP) is a popular message-passing heuristic for approximating a maximum-a-posteriori (MAP) assignment in a joint distribution represented by a graphical model (GM). In the past years, it has been shown that BP can solve a few classes of linear programming (LP) formulations to combinatorial optimization problems including maximum weight matching, shortest path and network flow, i.e., BP can be used as a message-passing solver for certain combinatorial optimizations. However, those LPs and corresponding BP analysis are very sensitive to underlying problem setups, and it has been not clear what extent these results can be generalized to. In this paper, we obtain a generic criteria that BP converges to the optimal solution of given LP, and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, traveling salesman, cycle packing, vertex/edge cover and network flow.
Performance of Compressive Parameter Estimation via K-Median Clustering
Venue: arXiv cs.IT 2017
Year: 2017

Compressive sensing (CS) has attracted significant attention in parameter estimation tasks, where parametric dictionaries (PDs) collect signal observations for a sampling of the parameter space and yield sparse representations for signals of interest when the sampling is dense. While this sampling also leads to high dictionary coherence, one can leverage structured sparsity models to prevent highly coherent dictionary elements from appearing simultaneously in the recovered signal. However, the resulting approaches depend heavily on the careful setting of the maximum allowable coherence; furthermore, their guarantees are not concerned with general parameter estimation performance. We propose the use of earth mover's distance (EMD), as applied to a pair of true and estimated PD coefficient vectors, to measure the parameter estimation error. We formally analyze the connection between the EMD and the parameter estimation error and show that the EMD provides a better-suited metric for parameter estimation performance than the Euclidean distance. Additionally, we analyze the previously described relationship between K-median clustering and EMD-optimal sparse approximation and leverage it to develop improved PD-based parameter estimation algorithms. Finally, our numerical experiments verify our theoretical results and show that the proposed compressive parameter estimation algorithms have improved performance over existing approaches.
Musical elements in the discrete-time representation of sound
Venue: arXiv cs.SD 2017
Year: 2017

The representation of basic elements of music in terms of discrete audio signals is often used in software for musical creation and design. Nevertheless, there is no unified approach that relates these elements to the discrete samples of digitized sound. In this article, each musical element is related by equations and algorithms to the discrete-time samples of sounds, and each of these relations are implemented in scripts within a software toolbox, referred to as MASS (Music and Audio in Sample Sequences). The fundamental element, the musical note with duration, volume, pitch and timbre, is related quantitatively to characteristics of the digital signal. Internal variations of a note, such as tremolos, vibratos and spectral fluctuations, are also considered, which enables the synthesis of notes inspired by real instruments and new sonorities. With this representation of notes, resources are provided for the generation of higher scale musical structures, such as rhythmic meter, pitch intervals and cycles. This framework enables precise and trustful scientific experiments, data sonification and is useful for education and art. The efficacy of MASS is confirmed by the synthesis of small musical pieces using basic notes, elaborated notes and notes in music, which reflects the organization of the toolbox and thus of this article. It is possible to synthesize whole albums through collage of the scripts and settings specified by the user. With the open source paradigm, the toolbox can be promptly scrutinized, expanded in co-authorship processes and used with freedom by musicians, engineers and other interested parties. In fact, MASS has already been employed for diverse purposes which include music production, artistic presentations, psychoacoustic experiments and computer language diffusion where the appeal of audiovisual artifacts is exploited for education.
Numerically Safe Gaussian Elimination with No Pivoting
Venue: arXiv cs.SC 2017
Year: 2017

Gaussian elimination with no pivoting and block Gaussian elimination are attractive alternatives to the customary but communication intensive Gaussian elimination with partial pivoting (hereafter we use the acronyms GENP, BGE, and GEPP} provided that the computations proceed safely and numerically safely}, that is, run into neither division by 0 nor numerical problems. Empirically, safety and numerical safety of GENP have been consistently observed in a number of papers where an input matrix was pre-processed with various structured multipliers chosen ad hoc. Our present paper provides missing formal support for this empirical observation and explains why it was elusive so far. Namely we prove that GENP is numerically unsafe for a specific class of input matrices in spite of its pre-processing with some well-known and well-tested structured multipliers, but we also prove that GENP and BGE are safe and numerically safe for the average input matrix pre-processed with any nonsingular and well-conditioned multiplier. This should embolden search for sparse and structured multipliers, and we list and test some new classes of them. We also seek randomized pre-processing that universally (that is, for all input matrices) supports (i) safe GENP and BGE with probability 1 and/or (ii) numerically safe GENP and BGE with a probability close to 1.We achieve goal (i) with a Gaussian structured multiplier and goal (ii) with a Gaussian unstructured multiplier and alternatively with Gaussian structured augmentation. We consistently confirm all these formal results with our tests of GENP for benchmark inputs. We have extended our approach to other fundamental matrix computations and keep working on further extensions.
Fourier Analysis of MAC Polarization
Venue: arXiv cs.IT 2017
Year: 2017

One problem with MAC polar codes that are based on MAC polarization is that they may not achieve the entire capacity region. The reason behind this problem is that MAC polarization sometimes induces a loss in the capacity region. This paper provides a single letter necessary and sufficient condition which characterizes all the MACs that do not lose any part of their capacity region by polarization.
On The Average-Case Complexity of Shellsort
Venue: arXiv cs.DS 2017
Year: 2017

We prove a lower bound expressed in the increment sequence on the average-case complexity of the number of inversions of Shellsort. This lower bound is sharp in every case where it could be checked. A special case of this lower bound yields the general Jiang-Li-Vitányi lower bound. We obtain new results e.g. determining the average-case complexity precisely in the Yao-Janson-Knuth 3-pass case.
TDMA is Optimal for All-unicast DoF Region of TIM if and only if Topology is Chordal Bipartite
Venue: arXiv cs.IT 2017
Year: 2017

The main result of this work is that an orthogonal access scheme such as TDMA achieves the all-unicast degrees of freedom (DoF) region of the topological interference management (TIM) problem if and only if the network topology graph is chordal bipartite, i.e., every cycle that can contain a chord, does contain a chord. The all-unicast DoF region includes the DoF region for any arbitrary choice of a unicast message set, so e.g., the results of Maleki and Jafar on the optimality of orthogonal access for the sum-DoF of one-dimensional convex networks are recovered as a special case. The result is also established for the corresponding topological representation of the index coding problem.
Does Dirichlet Prior Smoothing Solve the Shannon Entropy Estimation Problem?
Venue: arXiv cs.IT 2017
Year: 2017

The Dirichlet prior is widely used in estimating discrete distributions and functionals of discrete distributions. In terms of Shannon entropy estimation, one approach is to plug-in the Dirichlet prior smoothed distribution into the entropy functional, while the other one is to calculate the Bayes estimator for entropy under the Dirichlet prior for squared error, which is the conditional expectation. We show that in general they do \emph{not} improve over the maximum likelihood estimator, which plugs-in the empirical distribution into the entropy functional. No matter how we tune the parameters in the Dirichlet prior, this approach cannot achieve the minimax rates in entropy estimation, as recently characterized by Jiao, Venkat, Han, and Weissman, and Wu and Yang. The performance of the minimax rate-optimal estimator with $n$ samples is essentially \emph{at least} as good as that of the Dirichlet smoothed entropy estimators with $n\ln n$ samples. We harness the theory of approximation using positive linear operators for analyzing the bias of plug-in estimators for general functionals under arbitrary statistical models, thereby further consolidating the interplay between these two fields, which was thoroughly developed and exploited by Jiao, Venkat, Han, and Weissman. We establish new results in approximation theory, and apply them to analyze the bias of the Dirichlet prior smoothed plug-in entropy estimator. This interplay between bias analysis and approximation theory is of relevance and consequence far beyond the specific problem setting in this paper.
On asymptotically good ramp secret sharing schemes
Venue: arXiv cs.IT 2017
Year: 2017

Asymptotically good sequences of linear ramp secret sharing schemes have been intensively studied by Cramer et al. in terms of sequences of pairs of nested algebraic geometric codes. In those works the focus is on full privacy and full reconstruction. In this paper we analyze additional parameters describing the asymptotic behavior of partial information leakage and possibly also partial reconstruction giving a more complete picture of the access structure for sequences of linear ramp secret sharing schemes. Our study involves a detailed treatment of the (relative) generalized Hamming weights of the considered codes.
Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
Venue: arXiv cs.DC 2017
Year: 2017

Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Despite their extreme simplicity, these systems have been shown to cooperatively perform complex computational tasks, such as simulating register machines to compute standard arithmetic functions. The election of a unique leader agent is a key requirement in such computational constructions. Yet, the fastest currently known population protocol for electing a leader only has linear stabilization time, and, it has recently been shown that no population protocol using a constant number of states per node may overcome this linear bound. In this paper, we give the first population protocol for leader election with polylogarithmic stabilization time, using polylogarithmic memory states per node. The protocol structure is quite simple: each node has an associated value, and is either a leader (still in contention) or a minion (following some leader). A leader keeps incrementing its value and "defeats" other leaders in one-to-one interactions, and will drop from contention and become a minion if it meets a leader with higher value. Importantly, a leader also drops out if it meets a minion with higher absolute value. While these rules are quite simple, the proof that this algorithm achieves polylogarithmic stabilization time is non-trivial. In particular, the argument combines careful use of concentration inequalities with anti-concentration bounds, showing that the leaders' values become spread apart as the execution progresses, which in turn implies that straggling leaders get quickly eliminated. We complement our analysis with empirical results, showing that our protocol stabilizes extremely fast, even for large network sizes.
Swendsen-Wang Algorithm on the Mean-Field Potts Model
Venue: arXiv cs.DM 2017
Year: 2017

We study the $q$-state ferromagnetic Potts model on the $n$-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics. Long et al. studied the case $q=2$, the Swendsen-Wang algorithm for the mean-field ferromagnetic Ising model, and showed that the mixing time satisfies: (i) $Θ(1)$ for $β<β_c$, (ii) $Θ(n^{1/4})$ for $β=β_c$, (iii) $Θ(\log n)$ for $β>β_c$, where $β_c$ is the critical temperature for the ordered/disordered phase transition. In contrast, for $q\geq 3$ there are two critical temperatures $0<β_u<β_{rc}$ that are relevant. We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the $n$-vertex complete graph satisfies: (i) $Θ(1)$ for $β<β_u$, (ii) $Θ(n^{1/3})$ for $β=β_u$, (iii) $\exp(n^{Ω(1)})$ for $β_u<β<β_{rc}$, and (iv) $Θ(\log{n})$ for $β\geqβ_{rc}$. These results complement refined results of Cuff et al. on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.
Dynamic Spectrum Access in Time-varying Environment: Distributed Learning Beyond Expectation Optimization
Venue: arXiv cs.IT 2017
Year: 2017

This article investigates the problem of dynamic spectrum access for canonical wireless networks, in which the channel states are time-varying. In the most existing work, the commonly used optimization objective is to maximize the expectation of a certain metric (e.g., throughput or achievable rate). However, it is realized that expectation alone is not enough since some applications are sensitive to fluctuations. Effective capacity is a promising metric for time-varying service process since it characterizes the packet delay violating probability (regarded as an important statistical QoS index), by taking into account not only the expectation but also other high-order statistic. Therefore, we formulate the interactions among the users in the time-varying environment as a non-cooperative game, in which the utility function is defined as the achieved effective capacity. We prove that it is an ordinal potential game which has at least one pure strategy Nash equilibrium. Based on an approximated utility function, we propose a multi-agent learning algorithm which is proved to achieve stable solutions with dynamic and incomplete information constraints. The convergence of the proposed learning algorithm is verified by simulation results. Also, it is shown that the proposed multi-agent learning algorithm achieves satisfactory performance.
Minimal Distance of Propositional Models
Venue: arXiv cs.CC 2017
Year: 2017

We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula ($\mathsf{NeareastOtherSolution}$, $\mathsf{NOSol}$) or that does not need to satisfy it ($\mathsf{NearestSolution}$, $\mathsf{NSol}$). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments ($\mathsf{MinSolutionDistance}$, $\mathsf{MSD}$). For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, APX, NPO, or equivalence to well-known hard optimization problems.
The Complexity of General-Valued CSPs
Venue: arXiv cs.CC 2017
Year: 2017

An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates infeasible assignments. The goal is to find an assignment of labels to the variables that minimizes the sum. We study (assuming that P $\ne$ NP) how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in $\{0,\infty\}$ corresponds to ordinary CSPs, where one deals only with the feasibility issue and there is no optimization. This case is the subject of the Algebraic CSP Dichotomy Conjecture predicting for which constraint languages CSPs are tractable and for which NP-hard. The case when all allowed functions take only finite values corresponds to finite-valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.