OpenRaiser/Intern-Atlas huggingface dataset:
Quantifying Translation-Invariance in Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

A fundamental problem in object recognition is the development of image representations that are invariant to common transformations such as translation, rotation, and small deformations. There are multiple hypotheses regarding the source of translation invariance in CNNs. One idea is that translation invariance is due to the increasing receptive field size of neurons in successive convolution layers. Another possibility is that invariance is due to the pooling operation. We develop a simple a tool, the translation-sensitivity map, which we use to visualize and quantify the translation-invariance of various architectures. We obtain the surprising result that architectural choices such as the number of pooling layers and the convolution filter size have only a secondary effect on the translation-invariance of a network. Our analysis identifies training data augmentation as the most important factor in obtaining translation-invariant representations of images using convolutional neural networks.
Time Matters: Multi-scale Temporalization of Social Media Popularity
Venue: arXiv cs.SI 2017
Year: 2017

The evolution of social media popularity exhibits rich temporality, i.e., popularities change over time at various levels of temporal granularity. This is influenced by temporal variations of public attentions or user activities. For example, popularity patterns of street snap on Flickr are observed to depict distinctive fashion styles at specific time scales, such as season-based periodic fluctuations for Trench Coat or one-off peak in days for Evening Dress. However, this fact is often overlooked by existing research of popularity modeling. We present the first study to incorporate multiple time-scale dynamics into predicting online popularity. We propose a novel computational framework in the paper, named Multi-scale Temporalization, for estimating popularity based on multi-scale decomposition and structural reconstruction in a tensor space of user, post, and time by joint low-rank constraints. By considering the noise caused by context inconsistency, we design a data rearrangement step based on context aggregation as preprocessing to enhance contextual relevance of neighboring data in the tensor space. As a result, our approach can leverage multiple levels of temporal characteristics and reduce the noise of data decomposition to improve modeling effectiveness. We evaluate our approach on two large-scale Flickr image datasets with over 1.8 million photos in total, for the task of popularity prediction. The results show that our approach significantly outperforms state-of-the-art popularity prediction techniques, with a relative improvement of 10.9%-47.5% in terms of prediction accuracy.
An Adaptive Genetic Algorithm for Solving N-Queens Problem
Venue: arXiv cs.NE 2017
Year: 2017

In this paper a Metaheuristic approach for solving the N-Queens Problem is introduced to find the best possible solution in a reasonable amount of time. Genetic Algorithm is used with a novel fitness function as the Metaheuristic. The aim of N-Queens Problem is to place N queens on an N x N chessboard, in a way so that no queen is in conflict with the others. Chromosome representation and genetic operations like Mutation and Crossover are described in detail. Results show that this approach yields promising and satisfactory results in less time compared to that obtained from the previous approaches for several large values of N.
On the Development of Low Power MAC Protocol for WBANs
Venue: arXiv cs.NI 2018
Year: 2018

Current advances in wireless communication, microelectronics, semiconductor technologies, and intelligent sensors have contributed to the development of unobtrusive WBANs. These networks provide long term health monitoring of patients without any constraint in their normal activities. Traditional MAC protocols do not accommodate the assorted WBAN traffic requirements in a power efficient manner. In this paper, we present a brief discussion on the development process of a low power MAC protocol for WBANs. We observe the behavior of a beacon-enabled IEEE 802.15.4 for on-body sensor networks. We further propose a low power technique called traffic based wakeup mechanism for a WBAN that exploits the traffic patterns of the BAN Nodes to ensure power efficient and reliable communication.
FauxCrypt - A Method of Text Obfuscation
Venue: arXiv cs.CR 2018
Year: 2018

Warnings have been raised about the steady diminution of privacy. More and more personal information, such as that contained electronic mail, is moving to cloud computing servers where it might be machine-searched and indexed. FauxCrypt is an algorithm for modification of a plaintext document that leaves it generally readable by a person but not readily searched or indexed by machine. The algorithm employs a dictionary substitution of selected words, and an obfuscating transposition of letters in other words. The obfuscation is designed to leave the words understandable, although they are badly spelled. FauxCrypt is free, open source software, with source code available.
Bit recycling for scaling random number generators
Venue: arXiv cs.IT 2018
Year: 2018

Many Random Number Generators (RNG) are available nowadays; they are divided in two categories, hardware RNG, that provide "true" random numbers, and algorithmic RNG, that generate pseudo random numbers (PRNG). Both types usually generate random numbers $(X_n)$ as independent uniform samples in a range $0,\cdots,2^{b-1}$, with $b = 8, 16, 32$ or $b = 64$. In applications, it is instead sometimes desirable to draw random numbers as independent uniform samples $(Y_n)$ in a range $1, \cdots, M$, where moreover M may change between drawings. Transforming the sequence $(X_n)$ to $(Y_n)$ is sometimes known as scaling. We discuss different methods for scaling the RNG, both in term of mathematical efficiency and of computational speed.
Verifying Real-time Commit Protocols Using Dense-time Model Checking Technology
Venue: arXiv cs.SE 2018
Year: 2018

The timed-based automata model, introduced by Alur and Dill, provides a useful formalism for describing real-time systems. Over the last two decades, several dense-time model checking tools have been developed based on that model. The paper considers the verification of real-time distributed commit protocols using dense-time model checking technology. More precisely, we model and verify the well-known timed two phase commit protocol in three different state-of-the-art real-time model checkers: UPPAAL, Rabbit, and RED, and compare the results.
On Newton-Raphson iteration for multiplicative inverses modulo prime powers
Venue: arXiv cs.SC 2018
Year: 2018

We study algorithms for the fast computation of modular inverses. Newton-Raphson iteration over $p$-adic numbers gives a recurrence relation computing modular inverse modulo $p^m$, that is logarithmic in $m$. We solve the recurrence to obtain an explicit formula for the inverse. Then we study different implementation variants of this iteration and show that our explicit formula is interesting for small exponent values but slower or large exponent, say of more than $700$ bits. Overall we thus propose a hybrid combination of our explicit formula and the best asymptotic variants. This hybrid combination yields then a constant factor improvement, also for large exponents.
On online energy harvesting in multiple access communication systems
Venue: arXiv cs.IT 2018
Year: 2018

We investigate performance limits of a multiple access communication system with energy harvesting nodes where the utility function is taken to be the long-term average sum-throughput. We assume a causal structure for energy arrivals and study the problem in the continuous time regime. For this setting, we first characterize a storage dam model that captures the dynamics of a battery with energy harvesting and variable transmission power. Using this model, we next establish an upper bound on the throughput problem as a function of battery capacity. We also formulate a non-linear optimization problem to determine optimal achievable power policies for transmitters. Applying a calculus of variation technique, we then derive Euler-Lagrange equations as necessary conditions for optimum power policies in terms of a system of coupled partial integro-differential equations (PIDEs). Based on a Gauss-Seidel algorithm, we devise an iterative algorithm to solve these equations. We also propose a fixed-point algorithm for the symmetric multiple access setting in which the statistical descriptions of energy harvesters are identical. Along with the analysis and to support our iterative algorithms, comprehensive numerical results are also obtained.
The Power of Localization for Efficiently Learning Linear Separators with Noise
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and demonstrate its effectiveness by designing algorithms with improved noise tolerance guarantees for learning linear separators. We consider both the malicious noise model and the adversarial label noise model. For malicious noise, where the adversary can corrupt both the label and the features, we provide a polynomial-time algorithm for learning linear separators in $\Re^d$ under isotropic log-concave distributions that can tolerate a nearly information-theoretically optimal noise rate of $η= Ω(ε)$. For the adversarial label noise model, where the distribution over the feature vectors is unchanged, and the overall probability of a noisy label is constrained to be at most $η$, we also give a polynomial-time algorithm for learning linear separators in $\Re^d$ under isotropic log-concave distributions that can handle a noise rate of $η= Ω\left(ε\right)$. We show that, in the active learning model, our algorithms achieve a label complexity whose dependence on the error parameter $ε$ is polylogarithmic. This provides the first polynomial-time active learning algorithm for learning linear separators in the presence of malicious noise or adversarial label noise.
A New Key Establishment Protocol and its Application in Pay-TV Systems
Venue: arXiv cs.CR 2018
Year: 2018

A pay-TV consumer uses a decoder to access encrypted digital content. To this end, the decoder contains a chip capable of decrypting the content if provisioned with the appropriate content decryption keys. A key establishment protocol is used to secure the delivery of the content decryption keys to the chip. This paper presents a new protocol and shows how the protocol can be applied in a pay-TV system. Compared to existing protocols, the presented solution reduces the risk that decoders need to be replaced in order to correct a security breach. The new protocol has recently been incorporated in an ETSI standard.
Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
Venue: arXiv cs.DM 2018
Year: 2018

Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPT graph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is the EPT graph (i.e. the edge intersection graph) of P. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their split vertices is the set of vertices having degree at least 3 in their union. A pair of (edge) intersecting paths is termed non-splitting if they do not have split vertices (namely if their union is a path). We define the graph ENPT(P) of edge intersecting non-splitting paths of a tree, termed the ENPT graph, as the graph having a vertex for each path in P, and an edge between every pair of vertices representing two paths that are both edge-intersecting and non-splitting. A graph G is an ENPT graph if there is a tree T and a set of paths P of T such that G=ENPT(P), and we say that <T,P> is a representation of G. Our goal is to characterize the representation of chordless ENPT cycles (holes). To achieve this goal, we first assume that the EPT graph induced by the vertices of an ENPT hole is given. In [2] we introduce three assumptions (P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, we define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize the representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one by one. We characterize the representations of ENPT holes satisfying (P3) by providing a polynomial-time algorithm to solve P3-HamiltonianPairRec. We also show that there does not exist a polynomial-time algorithm to solve HamiltonianPairRec, unless P=NP.
Coordinated Tethering for Multi-RAT Cellular Networks: An Algorithmic Solution and Performance Analysis
Venue: arXiv cs.NI 2018
Year: 2018

The exploitation of already deployed wireless local area networks (WLAN)s (e.g., WiFi access points (AP)s) has attracted considerable attention, as an efficient and practical method to improve the performance of beyond 4G wireless networks. In this paper, we propose a novel communication paradigm to satisfy the performance demands of future wireless networks: a hybrid Cellular/WLAN network architecture with wireless offloading. In contrast to the commonly adopted practice of WiFi offloading, where the WLAN APs have a wired backhaul (e.g., Digital Subscriber Line), we propose a wireless offloading approach, where the WLAN APs will share their wireless cellular broadband connection with other users. These users will select their serving node, i.e., the macro-cell eNodeB or a WLAN AP, based on a certain selection criterion. Thus a challenging research field is originated, where interfering effects and wireless resources limitations play a dominant role. Important performance metrics of the proposed hybrid scheme, including the bit error probability, the ergodic capacity and the average signal-to-interference-plus noise ratio, are theoretically studied and closed form expressions are derived for the single-user case with multiple interferers, for both identical and non-identical fading conditions. Also, based on the general multi-cellular hybrid WLAN-Cellular concept, we first propose a intercell interference minimization approach. Then we present a novel scheme for achieving frequency reuse equal to one within a single macro-cell, under specific performance criteria and constraints, that guarantee the overall cell or the individual user QoS requirements.
Fingerprinting Codes and the Price of Approximate Differential Privacy
Venue: arXiv cs.CR 2018
Year: 2018

We show new lower bounds on the sample complexity of $(\varepsilon, δ)$-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database $D \in (\{0,1\}^d)^n$ has the form "What fraction of the individual records in the database satisfy the property $q$?" We show that in order to answer an arbitrary set $\mathcal{Q}$ of $\gg nd$ counting queries on $D$ to within error $\pm α$ it is necessary that $$ n \geq \tildeΩ\Bigg(\frac{\sqrt{d} \log |\mathcal{Q}|}{α^2 \varepsilon} \Bigg). $$ This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multiplicative Weights algorithm (Hardt and Rothblum, FOCS'10). In particular, our lower bound is the first to show that the sample complexity required for accuracy and $(\varepsilon, δ)$-differential privacy is asymptotically larger than what is required merely for accuracy, which is $O(\log |\mathcal{Q}| / α^2)$. In addition, we show that our lower bound holds for the specific case of $k$-way marginal queries (where $|\mathcal{Q}| = 2^k \binom{d}{k}$) when $α$ is not too small compared to $d$ (e.g. when $α$ is any fixed constant). Our results rely on the existence of short \emph{fingerprinting codes} (Boneh and Shaw, CRYPTO'95, Tardos, STOC'03), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds.
Group Testing with Prior Statistics
Venue: arXiv cs.IT 2018
Year: 2018

We consider a new group testing model wherein each item is a binary random variable defined by an a priori probability of being defective. We assume that each probability is small and that items are independent, but not necessarily identically distributed. The goal of group testing algorithms is to identify with high probability the subset of defectives via non-linear (disjunctive) binary measurements. Our main contributions are two classes of algorithms: (1) adaptive algorithms with tests based either on a maximum entropy principle, or on a Shannon-Fano/Huffman code; (2) non-adaptive algorithms. Under loose assumptions and with high probability, our algorithms only need a number of measurements that is close to the information-theoretic lower bound, up to an explicitly-calculated universal constant factor. We provide simulations to support our results.
A Stable Marriage Requires Communication
Venue: arXiv cs.GT 2018
Year: 2018

The Gale-Shapley algorithm for the Stable Marriage Problem is known to take $Θ(n^2)$ steps to find a stable marriage in the worst case, but only $Θ(n \log n)$ steps in the average case (with $n$ women and $n$ men). In 1976, Knuth asked whether the worst-case running time can be improved in a model of computation that does not require sequential access to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that $Θ(n^2)$ queries are required in a model that allows certain natural random-access queries to the participants' preferences. A significantly more general - albeit slightly weaker - lower bound follows from Segal's general analysis of communication complexity, namely that $Ω(n^2)$ Boolean queries are required in order to find a stable marriage, regardless of the set of allowed Boolean queries. Using a reduction to the communication complexity of the disjointness problem, we give a far simpler, yet significantly more powerful argument showing that $Ω(n^2)$ Boolean queries of any type are indeed required for finding a stable - or even an approximately stable - marriage. Notably, unlike Segal's lower bound, our lower bound generalizes also to (A) randomized algorithms, (B) allowing arbitrary separate preprocessing of the women's preferences profile and of the men's preferences profile, (C) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage, and (D) determining whether a proposed marriage is stable or far from stable. In order to analyze "approximately stable" marriages, we introduce the notion of "distance to stability" and provide an efficient algorithm for its computation.
Information, Meaning, and Intellectual Organization in Networks of Inter-Human Communication
Venue: arXiv cs.DL 2018
Year: 2018

The Shannon-Weaver model of linear information transmission is extended with two loops potentially generating redundancies: (i) meaning is provided locally to the information from the perspective of hindsight, and (ii) meanings can be codified differently and then refer to other horizons of meaning. Thus, three layers are distinguished: variations in the communications, historical organization at each moment of time, and evolutionary self-organization of the codes of communication over time. Furthermore, the codes of communication can functionally be different and then the system is both horizontally and vertically differentiated. All these subdynamics operate in parallel and necessarily generate uncertainty. However, meaningful information can be considered as the specific selection of a signal from the noise; the codes of communication are social constructs that can generate redundancy by giving different meanings to the same information. Reflexively, one can translate among codes in more elaborate discourses. The second (instantiating) layer can be operationalized in terms of semantic maps using the vector space model; the third in terms of mutual redundancy among the latent dimensions of the vector space. Using Blaise Cronin's œuvre, the different operations of the three layers are demonstrated empirically.
How to Achieve the Capacity of Asymmetric Channels
Venue: arXiv cs.IT 2018
Year: 2018

We survey coding techniques that enable reliable transmission at rates that approach the capacity of an arbitrary discrete memoryless channel. In particular, we take the point of view of modern coding theory and discuss how recent advances in coding for symmetric channels help provide more efficient solutions for the asymmetric case. We consider, in more detail, three basic coding paradigms. The first one is Gallager's scheme that consists of concatenating a linear code with a non-linear mapping so that the input distribution can be appropriately shaped. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Furthermore, we derive a scaling law between the gap to capacity, the cardinality of the input and output alphabets, and the required size of the mapper. The second one is an integrated scheme in which the code is used both for source coding, in order to create codewords distributed according to the capacity-achieving input distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third paradigm is based on an idea of Böcherer and Mathar, and separates the two tasks of source coding and channel coding by a chaining construction that binds together several codewords. We present conditions for the source code and the channel code, and we describe how to combine any source code with any channel code that fulfill those conditions, in order to provide capacity-achieving schemes for asymmetric channels. In particular, we show that polar codes, spatially coupled codes, and homophonic codes are suitable as basic building blocks of the proposed coding strategy.
Isomorphism within Naive Type Theory
Venue: arXiv cs.LO 2018
Year: 2018

We provide a treatment of isomorphism within a set-theoretic formulation of dependent type theory. Type expressions are assigned their natural set-theoretic compositional meaning. Types are divided into small and large types --- sets and proper classes respectively. Each proper class, such as "group" or "topological space", has an associated notion of isomorphism in correspondence with standard definitions. Isomorphism is handled by definging a groupoid structure on the space of all definable values. The values are simultaneously objects (oids) and morphism --- they are "morphoids". Soundness can then be proved for simple and natural inference rules deriving isomorphisms and for the substitution of isomorphics.
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
Venue: arXiv cs.CG 2018
Year: 2018

When can a plane graph with prescribed edge lengths and prescribed angles (from among $\{0,180^\circ, 360^\circ$\}) be folded flat to lie in an infinitesimally thin line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such flat-foldable plane graphs by two obviously necessary but also sufficient conditions, proving a conjecture made in 2001: the angles at each vertex should sum to $360^\circ$, and every face of the graph must itself be flat foldable. This characterization leads to a linear-time algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles, and a polynomial-time algorithm for counting the number of distinct folded states.