OpenRaiser/Intern-Atlas huggingface dataset:
The Primal versus the Dual Ising Model
Venue: arXiv cs.IT 2018
Year: 2018

We represent the Ising model of statistical physics by normal factor graphs in the primal and in the dual domains. By analogy with Kirchhoff's voltage and current laws, we show that in the primal normal factor graphs, the dependency among the variables is along the cycles, whereas in the dual normal factor graphs, the dependency is on the cutsets. In the primal (resp. dual) domain, dependent variables can be computed via their fundamental cycles (resp. fundamental cutsets). Using Onsager's closed form solution, we illustrate the opposite behavior of the uniform sampling estimator for estimating the partition function in the primal and in the dual of the homogeneous Ising model on a two-dimensional torus.
Improving Sparse Representation-Based Classification Using Local Principal Component Analysis
Venue: arXiv cs.CV 2018
Year: 2018

Sparse representation-based classification (SRC), proposed by Wright et al., seeks the sparsest decomposition of a test sample over the dictionary of training samples, with classification to the most-contributing class. Because it assumes test samples can be written as linear combinations of their same-class training samples, the success of SRC depends on the size and representativeness of the training set. Our proposed classification algorithm enlarges the training set by using local principal component analysis to approximate the basis vectors of the tangent hyperplane of the class manifold at each training sample. The dictionary in SRC is replaced by a local dictionary that adapts to the test sample and includes training samples and their corresponding tangent basis vectors. We use a synthetic data set and three face databases to demonstrate that this method can achieve higher classification accuracy than SRC in cases of sparse sampling, nonlinear class manifolds, and stringent dimension reduction.
Domains via approximation operators
Venue: arXiv cs.LO 2018
Year: 2018

In this paper, we tailor-make new approximation operators inspired by rough set theory and specially suited for domain theory. Our approximation operators offer a fresh perspective to existing concepts and results in domain theory, but also reveal ways to establishing novel domain-theoretic results. For instance, (1) the well-known interpolation property of the way-below relation on a continuous poset is equivalent to the idempotence of a certain set-operator; (2) the continuity of a poset can be characterized by the coincidence of the Scott closure operator and the upper approximation operator induced by the way below relation; (3) meet-continuity can be established from a certain property of the topological closure operator. Additionally, we show how, to each approximating relation, an associated order-compatible topology can be defined in such a way that for the case of a continuous poset the topology associated to the way-below relation is exactly the Scott topology. A preliminary investigation is carried out on this new topology.
Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations
Venue: arXiv cs.CR 2018
Year: 2018

Ideas from Fourier analysis have been used in cryptography for the last three decades. Akavia, Goldwasser and Safra unified some of these ideas to give a complete algorithm that finds significant Fourier coefficients of functions on any finite abelian group. Their algorithm stimulated a lot of interest in the cryptography community, especially in the context of `bit security'. This manuscript attempts to be a friendly and comprehensive guide to the tools and results in this field. The intended readership is cryptographers who have heard about these tools and seek an understanding of their mechanics and their usefulness and limitations. A compact overview of the algorithm is presented with emphasis on the ideas behind it. We show how these ideas can be extended to a `modulus-switching' variant of the algorithm. We survey some applications of this algorithm, and explain that several results should be taken in the right context. In particular, we point out that some of the most important bit security problems are still open. Our original contributions include: a discussion of the limitations on the usefulness of these tools; an answer to an open question about the modular inversion hidden number problem.
The Ho-Zhao Problem
Venue: arXiv cs.LO 2018
Year: 2018

Given a poset $P$, the set, $Γ(P)$, of all Scott closed sets ordered by inclusion forms a complete lattice. A subcategory $\mathbf{C}$ of $\mathbf{Pos}_d$ (the category of posets and Scott-continuous maps) is said to be $Γ$-faithful if for any posets $P$ and $Q$ in $\mathbf{C}$, $Γ(P) \cong Γ(Q)$ implies $P \cong Q$. It is known that the category of all continuous dcpos and the category of bounded complete dcpos are $Γ$-faithful, while $\mathbf{Pos}_d$ is not. Ho & Zhao (2009) asked whether the category $\mathbf{DCPO}$ of dcpos is $Γ$-faithful. In this paper, we answer this question in the negative by exhibiting a counterexample. To achieve this, we introduce a new subcategory of dcpos which is $Γ$-faithful. This subcategory subsumes all currently known $Γ$-faithful subcategories. With this new concept in mind, we construct the desired counterexample which relies heavily on Johnstone's famous dcpo which is not sober in its Scott topology.
The Anarchy of Scheduling Without Money
Venue: arXiv cs.GT 2018
Year: 2018

We consider the scheduling problem on $n$ strategic unrelated machines when no payments are allowed, under the objective of minimizing the makespan. We adopt the model introduced in [Koutsoupias, Theory Comput. Syst. (2014)] where a machine is bound by her declarations in the sense that if she is assigned a particular job then she will have to execute it for an amount of time at least equal to the one she reported, even if her private, true processing capabilities are actually faster. We provide a (non-truthful) randomized algorithm whose pure Price of Anarchy is arbitrarily close to $1$ for the case of a single task and close to $n$ if it is applied independently to schedule many tasks. Previous work considers the constraint of truthfulness and proves a tight approximation ratio of $(n+1)/2$ for one task which generalizes to $n(n+1)/2$ for many tasks. Furthermore, we revisit the truthfulness case and reduce the latter approximation ratio for many tasks down to $n$, asymptotically matching the best known lower bound. This is done via a detour to the relaxed, fractional version of the problem, for which we are also able to provide an optimal approximation ratio of $1$. Finally, we mention that all our algorithms achieve optimal ratios of $1$ for the social welfare objective.
Wavelet decomposition of software entropy reveals symptoms of malicious code
Venue: arXiv cs.CR 2018
Year: 2018

Sophisticated malware authors can sneak hidden malicious code into portable executable files, and this code can be hard to detect, especially if encrypted or compressed. However, when an executable file switches between code regimes (e.g. native, encrypted, compressed, text, and padding), there are corresponding shifts in the file's representation as an entropy signal. In this paper, we develop a method for automatically quantifying the extent to which patterned variations in a file's entropy signal make it "suspicious." In Experiment 1, we use wavelet transforms to define a Suspiciously Structured Entropic Change Score (SSECS), a scalar feature that quantifies the suspiciousness of a file based on its distribution of entropic energy across multiple levels of spatial resolution. Based on this single feature, it was possible to raise predictive accuracy on a malware detection task from 50.0% to 68.7%, even though the single feature was applied to a heterogeneous corpus of malware discovered "in the wild." In Experiment 2, we describe how wavelet-based decompositions of software entropy can be applied to a parasitic malware detection task involving large numbers of samples and features. By extracting only string and entropy features (with wavelet decompositions) from software samples, we are able to obtain almost 99% detection of parasitic malware with fewer than 1% false positives on good files. Moreover, the addition of wavelet-based features uniformly improved detection performance across plausible false positive rates, both in a strings-only model (e.g., from 80.90% to 82.97%) and a strings-plus-entropy model (e.g. from 92.10% to 94.74%, and from 98.63% to 98.90%). Overall, wavelet decomposition of software entropy can be useful for machine learning models for detecting malware based on extracting millions of features from executable files.
Cantor meets Scott: Semantic Foundations for Probabilistic Networks
Venue: arXiv cs.PL 2018
Year: 2018

ProbNetKAT is a probabilistic extension of NetKAT with a denotational semantics based on Markov kernels. The language is expressive enough to generate continuous distributions, which raises the question of how to compute effectively in the language. This paper gives an new characterization of ProbNetKAT's semantics using domain theory, which provides the foundation needed to build a practical implementation. We show how to use the semantics to approximate the behavior of arbitrary ProbNetKAT programs using distributions with finite support. We develop a prototype implementation and show how to use it to solve a variety of problems including characterizing the expected congestion induced by different routing schemes and reasoning probabilistically about reachability in a network.
A Complexity-Based Hierarchy for Multiprocessor Synchronization
Venue: arXiv cs.DC 2018
Year: 2018

For many years, Herlihy's elegant computability based Consensus Hierarchy has been our best explanation of the relative power of various types of multiprocessor synchronization objects when used in deterministic algorithms. However, key to this hierarchy is treating synchronization instructions as distinct objects, an approach that is far from the real-world, where multiprocessor programs apply synchronization instructions to collections of arbitrary memory locations. We were surprised to realize that, when considering instructions applied to memory locations, the computability based hierarchy collapses. This leaves open the question of how to better capture the power of various synchronization instructions. In this paper, we provide an approach to answering this question. We present a hierarchy of synchronization instructions, classified by their space complexity in solving obstruction-free consensus. Our hierarchy provides a classification of combinations of known instructions that seems to fit with our intuition of how useful some are in practice, while questioning the effectiveness of others. We prove an essentially tight characterization of the power of buffered read and write instructions.Interestingly, we show a similar result for multi-location atomic assignments.
Location Aware Opportunistic Bandwidth Sharing between Static and Mobile Users with Stochastic Learning in Cellular Networks
Venue: arXiv cs.NI 2018
Year: 2018

We consider location-dependent opportunistic bandwidth sharing between static and mobile downlink users in a cellular network. Each cell has some fixed number of static users. Mobile users enter the cell, move inside the cell for some time and then leave the cell. In order to provide higher data rate to mobile users, we propose to provide higher bandwidth to the mobile users at favourable times and locations, and provide higher bandwidth to the static users in other times. We formulate the problem as a long run average reward Markov decision process (MDP) where the per-step reward is a linear combination of instantaneous data volumes received by static and mobile users, and find the optimal policy. The transition structure of this MDP is not known in general. To alleviate this issue, we propose a learning algorithm based on single timescale stochastic approximation. Also, noting that the unconstrained MDP can be used to solve a constrained problem, we provide a learning algorithm based on multi-timescale stochastic approximation. The results are extended to address the issue of fair bandwidth sharing between the two classes of users. Numerical results demonstrate performance improvement by our scheme, and also the trade-off between performance gain and fairness.
Densely Connected Convolutional Networks
Venue: arXiv cs.CV 2018
Year: 2018

Recent work has shown that convolutional networks can be substantially deeper, more accurate, and efficient to train if they contain shorter connections between layers close to the input and those close to the output. In this paper, we embrace this observation and introduce the Dense Convolutional Network (DenseNet), which connects each layer to every other layer in a feed-forward fashion. Whereas traditional convolutional networks with L layers have L connections - one between each layer and its subsequent layer - our network has L(L+1)/2 direct connections. For each layer, the feature-maps of all preceding layers are used as inputs, and its own feature-maps are used as inputs into all subsequent layers. DenseNets have several compelling advantages: they alleviate the vanishing-gradient problem, strengthen feature propagation, encourage feature reuse, and substantially reduce the number of parameters. We evaluate our proposed architecture on four highly competitive object recognition benchmark tasks (CIFAR-10, CIFAR-100, SVHN, and ImageNet). DenseNets obtain significant improvements over the state-of-the-art on most of them, whilst requiring less computation to achieve high performance. Code and pre-trained models are available at https://github.com/liuzhuang13/DenseNet .
Graph parameters, Ramsey theory and the speed of hereditary properties
Venue: arXiv cs.DM 2018
Year: 2018

The speed of a hereditary property $P$ is the number $P_n$ of $n$-vertex labelled graphs in $P$. It is known that the rates of growth of $P_n$ constitute discrete layers and the speed jumps, in particular, from constant to polynomial, from polynomial to exponential and from exponential to factorial. One more jump occurs when the entropy $\lim_{n\to\infty}\frac{\log_2 P_n}{\binom{n}{2}}$ changes from 0 to a nonzero value. In the present paper, for each of these jumps we identify a graph parameter responsible for it, i.e. we show that a jump of the speed coincides with a jump of the respective parameter from finitude to infinity. In particular, we show that the speed of a hereditary property $P$ is sub-factorial if and only if the neighbourhood diversity of graphs in $P$ is bounded by a constant, and that the entropy of a hereditary property $P$ is 0 if and only if the VC-dimension of graphs in $P$ is bounded by a constant. All the result are obtained by Ramsey-type arguments.
Polar Coding Strategies for the Interference Channel with Partially-Joint Decoding
Venue: arXiv cs.IT 2018
Year: 2018

Existing polar coding schemes for the two-user interference channel follow the original idea of Han and Kobayashi, in which component messages are encoded independently and then mapped by some deterministic functions (i.e., homogeneous superposition coding). In this paper, we propose a new polar coding scheme for the interference channel based on the heterogeneous superposition coding approach of Chong, Motani and Garg. We prove that fully-joint decoding (the receivers simultaneously decode both senders' common messages and the intended sender's private message) in the Han-Kobayashi strategy can be simplified to two types of partially-joint decoding, which are friendly to polar coding with practical decoding algorithms. The proposed coding scheme requires less auxiliary random variables and no deterministic functions, and can be efficiently constructed. Further, we extend this result to interference networks and show that the proposed partially-joint decoding scheme is a general method for designing heterogeneous superposition polar coding schemes in interference networks.
Optimal Self-Stabilizing Mobile Byzantine-Tolerant Regular Register with bounded timestamp
Venue: arXiv cs.DC 2018
Year: 2018

This paper proposes the first implementation of a self-stabilizing regular register emulated by $n$ servers that is tolerant to both mobile Byzantine agents, and \emph{transient failures} in a round-free synchronous model. Differently from existing Mobile Byzantine tolerant register implementations, this paper considers a more powerful adversary where (i) the message delay (i.e., $δ$) and the period of mobile Byzantine agents movement (i.e., $Δ$) are completely decoupled and (ii) servers are not aware of their state i.e., they do not know if they have been corrupted or not by a mobile Byzantine agent.The proposed protocol tolerates \emph{(i)} any number of transient failures, and \emph{(ii)} up to $f$ Mobile Byzantine agents. In addition, our implementation uses bounded timestamps from the $\mathcal{Z}\_{13}$ domain and it is optimal with respect to the number of servers needed to tolerate $f$ mobile Byzantine agents in the given model.
The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections
Venue: arXiv cs.GT 2018
Year: 2018

We propose the maximin support method, a novel extension of the D'Hondt apportionment method to approval-based multiwinner elections. The maximin support method is based on maximizing the support of the least supported elected candidate. It can be computed efficiently and satisfies (adjusted versions of) the main properties of the original D'Hondt method: house monotonicity, population monotonicity, and proportional representation. We also establish a close relationship between the maximin support method and Phragmén's voting rules.
Playing FPS Games with Deep Reinforcement Learning
Venue: arXiv cs.AI 2018
Year: 2018

Advances in deep reinforcement learning have allowed autonomous agents to perform well on Atari games, often outperforming humans, using only raw pixels to make their decisions. However, most of these games take place in 2D environments that are fully observable to the agent. In this paper, we present the first architecture to tackle 3D environments in first-person shooter games, that involve partially observable states. Typically, deep reinforcement learning methods only utilize visual input for training. We present a method to augment these models to exploit game feature information such as the presence of enemies or items, during the training phase. Our model is trained to simultaneously learn these features along with minimizing a Q-learning objective, which is shown to dramatically improve the training speed and performance of our agent. Our architecture is also modularized to allow different models to be independently trained for different phases of the game. We show that the proposed architecture substantially outperforms built-in AI agents of the game as well as humans in deathmatch scenarios.
Energy-Efficient Scheduling: Classification, Bounds, and Algorithms
Venue: arXiv cs.DC 2018
Year: 2018

The problem of attaining energy efficiency in distributed systems is of importance, but a general, non-domain-specific theory of energy-minimal scheduling is far from developed. In this paper, we classify the problems of energy-minimal scheduling and present theoretical foundations of the same. We derive results concerning energy-minimal scheduling of independent jobs in a distributed system with functionally similar machines with different working and idle power ratings. The machines considered in our system can have identical as well as different speeds. If the jobs can be divided into arbitrary parts, we show that the minimum-energy schedule can be generated in linear time and give exact scheduling algorithms. For the cases where jobs are non-divisible, we prove that the scheduling problems are NP-hard and also give approximation algorithms for the same along with their bounds.
Exact Sampling from Determinantal Point Processes
Venue: arXiv cs.LG 2018
Year: 2018

Determinantal point processes (DPPs) are an important concept in random matrix theory and combinatorics. They have also recently attracted interest in the study of numerical methods for machine learning, as they offer an elegant "missing link" between independent Monte Carlo sampling and deterministic evaluation on regular grids, applicable to a general set of spaces. This is helpful whenever an algorithm explores to reduce uncertainty, such as in active learning, Bayesian optimization, reinforcement learning, and marginalization in graphical models. To draw samples from a DPP in practice, existing literature focuses on approximate schemes of low cost, or comparably inefficient exact algorithms like rejection sampling. We point out that, for many settings of relevance to machine learning, it is also possible to draw exact samples from DPPs on continuous domains. We start from an intuitive example on the real line, which is then generalized to multivariate real vector spaces. We also compare to previously studied approximations, showing that exact sampling, despite higher cost, can be preferable where precision is needed.
Comparison of Channels: Criteria for Domination by a Symmetric Channel
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies the basic question of whether a given channel $V$ can be dominated (in the precise sense of being more noisy) by a $q$-ary symmetric channel. The concept of "less noisy" relation between channels originated in network information theory (broadcast channels) and is defined in terms of mutual information or Kullback-Leibler divergence. We provide an equivalent characterization in terms of $χ^2$-divergence. Furthermore, we develop a simple criterion for domination by a $q$-ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel $V$. The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev inequality for the original channel.
Organized Complexity: is Big History a Big Computation?
Venue: arXiv cs.OH 2018
Year: 2018

The concept of "logical depth" introduced by Charles H. Bennett (1988) seems to capture, at least partially, the notion of organized complexity, so central in big history. More precisely, the increase in organized complexity refers here to the wealth, variety and intricacy of structures, and should not be confused with the increase of random complexity, formalized by Kolmogorov (1965). If Bennett is right in proposing to assimilate organized complexity with "computational content", then the fundamental cause of the increase of complexity in the universe is the existence of computing mechanisms with memory, and able to cumulatively create and preserve computational contents. In this view, the universe computes, remembers its calculations, and reuses them to conduct further computations. Evolutionary mechanisms are such forms of cumulative computation with memory and we owe them the organized complexity of life. Language, writing, culture, science and technology can also be analyzed as computation mechanisms generating, preserving and accelerating the increase in organized complexity. The main unifying theme for big history is the energy rate density, a metric based on thermodynamics. However useful, this metric does not provide much insight into the role that information and computation play in our universe. The concept of "logical depth" provides a new lens to examine the increase of organized complexity. We argue in this paper that organized complexity is a valid and useful way to make sense of big history. Additionally, logical depth has a rigorous formal definition in theoretical computer science that hints at a broader research program to quantify complexity in the universe. Keywords: organized complexity, Kolmogorov complexity, logical depth, big history, cosmic evolution, evolution, complexity, complexification, computation, artificial life, philosophy of information