OpenRaiser/Intern-Atlas huggingface dataset:
Right buffer sizing matters: some dynamical and statistical studies on Compound TCP
Venue: arXiv cs.NI 2018
Year: 2018

Motivated by recent concerns that queuing delays in the Internet are on the rise, we conduct a performance evaluation of Compound TCP (C-TCP) in two topologies: a single bottleneck and a multi-bottleneck topology, under different traffic scenarios. The first topology consists of a single bottleneck router, and the second consists of two distinct sets of TCP flows, regulated by two edge routers, feeding into a common core router. We focus on some dynamical and statistical properties of the underlying system. From a dynamical perspective, we develop fluid models in a regime wherein the number of flows is large, bandwidth-delay product is high, buffers are dimensioned small (independent of the bandwidth-delay product) and routers deploy a Drop-Tail queue policy. A detailed local stability analysis for these models yields the following key insight: smaller buffers favour stability. Additionally, we highlight that larger buffers, in addition to increasing latency, are prone to inducing limit cycles in the system dynamics, via a Hopf bifurcation. These limit cycles in turn cause synchronisation among the TCP flows, and also result in a loss of link utilisation. For the topologies considered, we also empirically analyse some statistical properties of the bottleneck queues. These statistical analyses serve to validate an important modelling assumption: that in the regime considered, each bottleneck queue may be approximated as either an $M/M/1/B$ or an $M/D/1/B$ queue. This immediately makes the modelling perspective attractive and the analysis tractable. Finally, we show that smaller buffers, in addition to ensuring stability and low latency, would also yield fairly good system performance, in terms of throughput and flow completion times.
On Medium Chemical Reaction in Diffusion-Based Molecular Communication: a Two-Way Relaying Example
Venue: arXiv cs.IT 2018
Year: 2018

Chemical reactions are a prominent feature of molecular communication (MC) systems, with no direct parallels in wireless communications. While chemical reactions may be used inside the transmitter nodes, receiver nodes or the communication medium, we focus on its utility in the medium in this paper. Such chemical reactions can be used to perform computation over the medium as molecules diffuse and react with each other (physical-layer computation). We propose the use of chemical reactions for the following purposes: (i) to reduce signal-dependent observation noise of receivers by reducing the signal density, (ii) to realize molecular physical-layer network coding (molecular PNC) by performing the natural XOR operation inside the medium, and (iii) to reduce the inter-symbol interference (ISI) of other transmitters by canceling out the remaining molecules from previous transmissions. To make the ideas formal, we consider an explicit two-way relaying example with a transparent receiver (which has a signal-dependent noise). The proposed ideas are used to define a modulation scheme (which we call the PNC scheme). We compare the PNC with a previously proposed scheme for this problem where the XOR operation is performed at the relay node (using a molecular logic gate). We call the latter, the straightforward network coding (SNC). It is observed that in addition to the simplicity of the proposed PNC scheme, it outperforms the SNC scheme especially when we consider ISI.
Knowledge model: a method to evaluate an individual's knowledge quantitatively
Venue: arXiv cs.HC 2018
Year: 2018

As the quantity of human knowledge increasing rapidly, it is harder and harder to evaluate a knowledge worker's knowledge quantitatively. There are lots of demands for evaluating a knowledge worker's knowledge. For example, accurately finding out a researcher's research concentrations for the last three years; searching for common topics for two scientists with different academic backgrounds; helping a researcher discover his deficiencies on a research field etc. This paper proposes a method named knowledge model to evaluate a knowledge worker's knowledge quantitatively without taking an examination. It records and analyzes an individual's each learning experience, discovering all the involved knowledge points and calculating their shares by analyzing the text learning contents with topic model. It calculates a score for a knowledge point by accumulating the effects of one's all learning experiences about it. A preliminary knowledge evaluating system is developed to testify the practicability of knowledge model.
A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs
Venue: arXiv cs.DM 2018
Year: 2018

There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, we develop a general two-stage framework which consists of efficiently solving a problem-specific number problem and transferring its solution to a solution for the graph problem by applying flow computations. In this way, we obtain fixed-parameter tractability and polynomial kernelizability results, with the central parameter being the maximum vertex in- or outdegree of the output digraph. Although there are certain similarities with the much better studied undirected case, the flow computation used in the directed case seems not to work for the undirected case while $f$-factor computations as used in the undirected case seem not to work for the directed case.
Clustering with Missing Features: A Penalized Dissimilarity Measure based approach
Venue: arXiv cs.LG 2018
Year: 2018

Many real-world clustering problems are plagued by incomplete data characterized by missing or absent features for some or all of the data instances. Traditional clustering methods cannot be directly applied to such data without preprocessing by imputation or marginalization techniques. In this article, we overcome this drawback by utilizing a penalized dissimilarity measure which we refer to as the Feature Weighted Penalty based Dissimilarity (FWPD). Using the FWPD measure, we modify the traditional k-means clustering algorithm and the standard hierarchical agglomerative clustering algorithms so as to make them directly applicable to datasets with missing features. We present time complexity analyses for these new techniques and also undertake a detailed theoretical analysis showing that the new FWPD based k-means algorithm converges to a local optimum within a finite number of iterations. We also present a detailed method for simulating random as well as feature dependent missingness. We report extensive experiments on various benchmark datasets for different types of missingness showing that the proposed clustering techniques have generally better results compared to some of the most well-known imputation methods which are commonly used to handle such incomplete data. We append a possible extension of the proposed dissimilarity measure to the case of absent features (where the unobserved features are known to be undefined).
Syntactic complexity of bifix-free languages
Venue: arXiv cs.FL 2018
Year: 2018

We study the properties of syntactic monoids of bifix-free regular languages. In particular, we solve an open problem concerning syntactic complexity: We prove that the cardinality of the syntactic semigroup of a bifix-free language with state complexity $n$ is at most $(n-1)^{n-3}+(n-2)^{n-3}+(n-3)2^{n-3}$ for $n\ge 6$. The main proof uses a large construction with the method of injective function. Since this bound is known to be reachable, and the values for $n \le 5$ are known, this completely settles the problem. We also prove that $(n-2)^{n-3} + (n-3)2^{n-3} - 1$ is the minimal size of the alphabet required to meet the bound for $n \ge 6$. Finally, we show that the largest transition semigroups of minimal DFAs which recognize bifix-free languages are unique up to renaming the states.
On Polynomial Approximations to ${AC}^0$
Venue: arXiv cs.CC 2018
Year: 2018

We make progress on some questions related to polynomial approximations of ${\rm AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC, 1991), that any ${\rm AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals of degree $(\log (s/\varepsilon))^{O(d)}$. We improve this upper bound to $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$, which is much better for small values of $\varepsilon$. We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that $(\log s)^{O(d)}\cdot \log(1/\varepsilon)$-wise independence fools ${\rm AC}^0$, improving on Tal's strengthening of Braverman's theorem (J. ACM, 2010) that $(\log (s/\varepsilon))^{O(d)}$-wise independence fools ${\rm AC}^0$. Up to the constant implicit in the $O(d)$, our result is tight. As far as we know, this is the first PRG construction for ${\rm AC}^0$ that achieves optimal dependence on the error $\varepsilon$. We also prove lower bounds on the best polynomial approximations to ${\rm AC}^0$. We show that any polynomial approximating the ${\rm OR}$ function on $n$ bits to a small constant error must have degree at least $\widetildeΩ(\sqrt{\log n})$. This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).
Distributed Inertial Best-Response Dynamics
Venue: arXiv cs.SY 2018
Year: 2018

The note considers the problem of computing pure Nash equilibrium (NE) strategies in distributed (i.e., network-based) settings. The paper studies a class of inertial best response dynamics based on the fictitious play (FP) algorithm. It is shown that inertial best response dynamics are robust to informational limitations common in distributed settings. Fully distributed variants of FP with inertia and joint strategy FP with inertia are developed and convergence is proven to the set of pure NE. The distributed algorithms rely on consensus methods. Results are validated using numerical simulations.
Comparing Kalman Filters and Observers for Power System Dynamic State Estimation with Model Uncertainty and Malicious Cyber Attacks
Venue: arXiv cs.SY 2018
Year: 2018

Kalman filters and observers are two main classes of dynamic state estimation (DSE) routines. Power system DSE has been implemented by various Kalman filters, such as the extended Kalman filter (EKF) and the unscented Kalman filter (UKF). In this paper, we discuss two challenges for an effective power system DSE: (a) model uncertainty and (b) potential cyber attacks. To address this, the cubature Kalman filter (CKF) and a nonlinear observer are introduced and implemented. Various Kalman filters and the observer are then tested on the 16-machine, 68-bus system given realistic scenarios under model uncertainty and different types of cyber attacks against synchrophasor measurements. It is shown that CKF and the observer are more robust to model uncertainty and cyber attacks than their counterparts. Based on the tests, a thorough qualitative comparison is also performed for Kalman filter routines and observers.
Deterministic Leader Election Takes $Θ(D + \log n)$ Bit Rounds
Venue: arXiv cs.DC 2018
Year: 2018

Leader election is, together with consensus, one of the most central problems in distributed computing. This paper presents a distributed algorithm, called \STT, for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size $O(\log n)$, where $n$ is the number of processors. It elects a leader in $O(D +\log n)$ rounds, where $D$ is the diameter of the network, with messages of size $O(1)$. Thus it has a bit round complexity of $O(D +\log n)$. This substantially improves upon the best known algorithm whose bit round complexity is $O(D\log n)$. In fact, using the lower bound by Kutten et al. (2015) and a result of Dinitz and Solomon (2007), we show that the bit round complexity of \STT is optimal (up to a constant factor), which is a significant step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as $n$ or $D$, and the pipelining technique we introduce to break the $O(D\log n)$ barrier is general.
t-multiple discrete logarithm problem and solving difficulty
Venue: arXiv cs.CR 2018
Year: 2018

Considering the difficult problem under classical computing model can be solved by the quantum algorithm in polynomial time, t-multiple discrete logarithm problems presented. The problem is non-degeneracy and unique solution. We talk about what the parameter effects the problem solving difficulty. Then we pointed out that the index-calculus algorithm is not suitable for the problem, and two sufficient conditions of resistance to the quantum algorithm for the hidden subgroup problem are given.
Dataflow matrix machines as programmable, dynamically expandable, self-referential generalized recurrent neural networks
Venue: arXiv cs.NE 2018
Year: 2018

Dataflow matrix machines are a powerful generalization of recurrent neural networks. They work with multiple types of linear streams and multiple types of neurons, including higher-order neurons which dynamically update the matrix describing weights and topology of the network in question while the network is running. It seems that the power of dataflow matrix machines is sufficient for them to be a convenient general purpose programming platform. This paper explores a number of useful programming idioms and constructions arising in this context.
Enhancing Performance Bounds of Multiple-Ring Networks with Cyclic Dependencies based on Network Calculus
Venue: arXiv cs.PF 2018
Year: 2018

Tightening performance bounds of ring networks with cyclic dependencies is still an open problem in the literature. In this paper, we tackle such a challenging issue based on Network Calculus. First, we review the conventional timing approaches in the area and identify their main limitations, in terms of delay bounds pessimism. Afterwards, we have introduced a new concept called Pay Multiplexing Only at Convergence points (PMOC) to overcome such limitations. PMOC considers the flow serialization phenomena along the flow path, by paying the bursts of interfering flows only at the convergence points. The guaranteed endto- end service curves under such a concept have been defined and proved for mono-ring and multiple-ring networks, as well as under Arbitrary and Fixed Priority multiplexing. A sensitivity analysis of the computed delay bounds for mono and multiple-ring networks is conducted with respect to various flow and network parameters, and their tightness is assessed in comparison with an achievable worst-case delay. A noticeable enhancement of the delay bounds, thus network resource efficiency and scalability, is highlighted under our proposal with reference to conventional approaches. Finally, the efficiency of the PMOC approach to provide timing guarantees is confirmed in the case of a realistic avionics application.
Systems Aliasing in Dynamic Network Reconstruction: Issues on Low Sampling Frequencies
Venue: arXiv cs.SY 2018
Year: 2018

Network reconstruction of dynamical continuous-time (CT) systems is motivated by applications in many fields. Due to experimental limitations, especially in biology, data could be sampled at low frequencies, leading to significant challenges in network inference. We introduce the concept of "system aliasing" and characterize the minimal sampling frequency that allows reconstruction of CT systems from low sampled data. A test criterion is also proposed to check whether system aliasing is presented. With no system aliasing, the paper provides an algorithm to reconstruct dynamic network from data in the presence of noise. In addition, when there is system aliasing we perform studies that add additional prior information of the system such as sparsity. This paper opens new directions in modelling of network systems where samples have significant costs. Such tools are essential to process the available data in applications subject to current experimental limitations.
Finite Sample Analysis of Approximate Message Passing Algorithms
Venue: arXiv cs.IT 2018
Year: 2018

Approximate message passing (AMP) refers to a class of efficient algorithms for statistical estimation in high-dimensional problems such as compressed sensing and low-rank matrix estimation. This paper analyzes the performance of AMP in the regime where the problem dimension is large but finite. For concreteness, we consider the setting of high-dimensional regression, where the goal is to estimate a high-dimensional vector $β_0$ from a noisy measurement $y=A β_0 + w$. AMP is a low-complexity, scalable algorithm for this problem. Under suitable assumptions on the measurement matrix $A$, AMP has the attractive feature that its performance can be accurately characterized in the large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this paper, we derive a concentration inequality for AMP with i.i.d. Gaussian measurement matrices with finite size $n \times N$. The result shows that the probability of deviation from the state evolution prediction falls exponentially in $n$. This provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions. The concentration inequality also indicates that the number of AMP iterations $t$ can grow no faster than order $\frac{\log n}{\log \log n}$ for the performance to be close to the state evolution predictions with high probability. The analysis can be extended to obtain similar non-asymptotic results for AMP in other settings such as low-rank matrix estimation.
Egalitarian computing
Venue: arXiv cs.CR 2018
Year: 2018

In this paper we explore several contexts where an adversary has an upper hand over the defender by using special hardware in an attack. These include password processing, hard-drive protection, cryptocurrency mining, resource sharing, code obfuscation, etc. We suggest memory-hard computing as a generic paradigm, where every task is amalgamated with a certain procedure requiring intensive access to RAM both in terms of size and (very importantly) bandwidth, so that transferring the computation to GPU, FPGA, and even ASIC brings little or no cost reduction. Cryptographic schemes that run in this framework become egalitarian in the sense that both users and attackers are equal in the price-performance ratio conditions. Based on existing schemes like {Argon2} and the recent generalized-birthday proof-of-work, we suggest a generic framework and two new schemes: MTP, a memory-hard Proof-of-Work based on the memory-hard function with fast verification and short proofs. It can be also used for memory-hard time-lock puzzles. {MHE}, the concept of memory-hard encryption, which utilizes available RAM to strengthen the encryption for the low-entropy keys (allowing to bring back 6 letter passwords).
Downlink Performance of Superimposed Pilots in Massive MIMO systems
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we investigate the downlink throughput performance of a massive multiple-input multiple-output (MIMO) system that employs superimposed pilots for channel estimation. The component of downlink (DL) interference that results from transmitting data alongside pilots in the uplink (UL) is shown to decrease at a rate proportional to the square root of the number of antennas at the BS. The normalized mean-squared error (NMSE) of the channel estimate is compared with the Bayesian Cramér-Rao lower bound that is derived for the system, and the former is also shown to diminish with increasing number of antennas at the base station (BS). Furthermore, we show that staggered pilots are a particular case of superimposed pilots and offer the downlink throughput of superimposed pilots while retaining the UL spectral and energy efficiency of regular pilots. We also extend the framework for designing a hybrid system, consisting of users that transmit either regular or superimposed pilots, to minimize both the UL and DL interference. The improved NMSE and DL rates of the channel estimator based on superimposed pilots are demonstrated by means of simulations.
Faster Coreset Construction for Projective Clustering via Low-Rank Approximation
Venue: arXiv cs.CG 2018
Year: 2018

In this work, we present a randomized coreset construction for projective clustering, which involves computing a set of $k$ closest $j$-dimensional linear (affine) subspaces of a given set of $n$ vectors in $d$ dimensions. Let $A \in \mathbb{R}^{n\times d}$ be an input matrix. An earlier deterministic coreset construction of Feldman \textit{et. al.} relied on computing the SVD of $A$. The best known algorithms for SVD require $\min\{nd^2, n^2d\}$ time, which may not be feasible for large values of $n$ and $d$. We present a coreset construction by projecting the rows of matrix $A$ on some orthonormal vectors that closely approximate the right singular vectors of $A$. As a consequence, when the values of $k$ and $j$ are small, we are able to achieve a faster algorithm, as compared to the algorithm of Feldman \textit{et. al.}, while maintaining almost the same approximation. We also benefit in terms of space as well as exploit the sparsity of the input dataset. Another advantage of our approach is that it can be constructed in a streaming setting quite efficiently.
Weak embeddings of posets to the Boolean lattice
Venue: arXiv cs.DM 2018
Year: 2018

The goal of this paper is to prove that several variants of deciding whether a poset can be (weakly) embedded into a small Boolean lattice, or to a few consecutive levels of a Boolean lattice, are NP-complete, answering a question of Griggs and of Patkos. As an equivalent reformulation of one of these problems, we also derive that it is NP-complete to decide whether a given graph can be embedded to the two middle levels of some hypercube.
On the Convergence Rate of Average Consensus and Distributed Optimization over Unreliable Networks
Venue: arXiv cs.DC 2018
Year: 2018

We consider the problems of reaching average consensus and solving consensus-based optimization over unreliable communication networks wherein packets may be dropped accidentally during transmission. Existing work either assumes that the link failures affect the communication on both directions or that the message senders {\em know exactly}, in each iteration, how many of their outgoing links are functioning properly. In this paper, we consider directed links, and we {\em do not} require each node know its current outgoing degree. First, we propose and characterize the convergence rate of reaching average consensus. Then we apply our robust consensus update to the classical distributed dual averaging method wherein the consensus update is used as the information aggregation primitive. We show that the local iterates converge to a common optimum of the global objective at rate $O(\frac{1}{\sqrt{t}})$, where $t$ is the number of iterations, matching the failure-free performance of the distributed dual averaging method.