OpenRaiser/Intern-Atlas huggingface dataset:
Can Marton Coding Alone Ensure Individual Secrecy?
Venue: arXiv cs.IT 2021
Year: 2021

For communications in the presence of eavesdroppers, random components are often used in code design to camouflage information from eavesdroppers. In broadcast channels without eavesdroppers, Marton error-correcting coding comprises random components which allow correlation between auxiliary random variables representing independent messages. In this paper, we study if Marton coding alone can ensure individual secrecy in the two-receiver discrete memoryless broadcast channel with a passive eavesdropper. Our results show that in accordance to the principle of Wyner secrecy coding, this is possible and Marton coding alone guarantees individual secrecy. However, this comes with a penalty of requiring stricter channel conditions.
Designing Deep Reinforcement Learning for Human Parameter Exploration
Venue: arXiv cs.HC 2021
Year: 2021

Software tools for generating digital sound often present users with high-dimensional, parametric interfaces, that may not facilitate exploration of diverse sound designs. In this paper, we propose to investigate artificial agents using deep reinforcement learning to explore parameter spaces in partnership with users for sound design. We describe a series of user-centred studies to probe the creative benefits of these agents and adapting their design to exploration. Preliminary studies observing users' exploration strategies with parametric interfaces and testing different agent exploration behaviours led to the design of a fully-functioning prototype, called Co-Explorer, that we evaluated in a workshop with professional sound designers. We found that the Co-Explorer enables a novel creative workflow centred on human-machine partnership, which has been positively received by practitioners. We also highlight varied user exploration behaviors throughout partnering with our system. Finally, we frame design guidelines for enabling such co-exploration workflow in creative digital applications.
On the VC-dimension of half-spaces with respect to convex sets
Venue: arXiv cs.CG 2021
Year: 2021

A family S of convex sets in the plane defines a hypergraph H = (S, E) as follows. Every subfamily S' of S defines a hyperedge of H if and only if there exists a halfspace h that fully contains S' , and no other set of S is fully contained in h. In this case, we say that h realizes S'. We say a set S is shattered, if all its subsets are realized. The VC-dimension of a hypergraph H is the size of the largest shattered set. We show that the VC-dimension for pairwise disjoint convex sets in the plane is bounded by 3, and this is tight. In contrast, we show the VC-dimension of convex sets in the plane (not necessarily disjoint) is unbounded. We provide a quadratic lower bound in the number of pairs of intersecting sets in a shattered family of convex sets in the plane. We also show that the VC-dimension is unbounded for pairwise disjoint convex sets in R^d , for d > 2. We focus on, possibly intersecting, segments in the plane and determine that the VC-dimension is always at most 5. And this is tight, as we construct a set of five segments that can be shattered. We give two exemplary applications. One for a geometric set cover problem and one for a range-query data structure problem, to motivate our findings.
Unveiling patterns in xorshift128+ pseudorandom number generators
Venue: arXiv cs.MS 2021
Year: 2021

Xorshift128+ is a newly proposed pseudorandom number generator (PRNG), which is now the standard PRNG on a number of platforms. We demonstrate that three-dimensional plots of the random points generated by the generator have visible structures: they concentrate on particular planes in the cube. We provide a mathematical analysis of this phenomenon.
Lags in the Release, Adoption, and Propagation of npm Vulnerability Fixes
Venue: arXiv cs.SE 2021
Year: 2021

Security vulnerability in third-party dependencies is a growing concern not only for developers of the affected software, but for the risks it poses to an entire software ecosystem, e.g., Heartbleed vulnerability. Recent studies show that developers are slow to respond to the threat of vulnerability, sometimes taking four to eleven months to act. To ensure quick adoption and propagation of a release that contains the fix (fixing release), we conduct an empirical investigation to identify lags that may occur between the vulnerable release and its fixing release (package-side fixing release). Through a preliminary study of 231 package-side fixing release of npm projects on GitHub, we observe that a fixing release is rarely released on its own, with up to 85.72% of the bundled commits being unrelated to a fix. We then compare the package-side fixing release with changes on a client-side (client-side fixing release). Through an empirical study of the adoption and propagation tendencies of 1,290 package-side fixing releases that impact throughout a network of 1,553,325 releases of npm packages, we find that stale clients require additional migration effort, even if the package-side fixing release was quick (i.e., package patch landing). Furthermore, we show the influence of factors such as the branch that the package-side fixing release lands on and the severity of vulnerability on its propagation. In addition to these lags we identify and characterize, this paper lays the groundwork for future research on how to mitigate lags in an ecosystem.
Improving the Performance of the LSTM and HMM Model via Hybridization
Venue: arXiv cs.LG 2021
Year: 2021

Language models based on deep neural networks and traditional stochastic modelling have become both highly functional and effective in recent times. In this work, a general survey into the two types of language modelling is conducted. We investigate the effectiveness of the Hidden Markov Model (HMM), and the Long Short-Term Memory Model (LSTM). We analyze the hidden state structures common to both models, and present an analysis on structural similarity of the hidden states, common to both HMM's and LSTM's. We compare the LSTM's predictive accuracy and hidden state output with respect to the HMM for a varying number of hidden states. In this work, we justify that the less complex HMM can serve as an appropriate approximation of the LSTM model.
Imitation-Projected Programmatic Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

We study the problem of programmatic reinforcement learning, in which policies are represented as short programs in a symbolic language. Programmatic policies can be more interpretable, generalizable, and amenable to formal verification than neural policies; however, designing rigorous learning approaches for such policies remains a challenge. Our approach to this challenge -- a meta-algorithm called PROPEL -- is based on three insights. First, we view our learning task as optimization in policy space, modulo the constraint that the desired policy has a programmatic representation, and solve this optimization problem using a form of mirror descent that takes a gradient step into the unconstrained policy space and then projects back onto the constrained space. Second, we view the unconstrained policy space as mixing neural and programmatic representations, which enables employing state-of-the-art deep policy gradient approaches. Third, we cast the projection step as program synthesis via imitation learning, and exploit contemporary combinatorial methods for this task. We present theoretical convergence results for PROPEL and empirically evaluate the approach in three continuous control domains. The experiments show that PROPEL can significantly outperform state-of-the-art approaches for learning programmatic policies.
The Projection Games Conjecture and the Hardness of Approximation of super-SAT and related problems
Venue: arXiv cs.CC 2021
Year: 2021

The Super-SAT or SSAT problem was introduced by Dinur et al.(2002,2003) to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem(SVP) and Closest Vector Problem(CVP). They conjectured that SSAT is NP-hard to approximate to within a factor of $n^c$ ($c>0$ is constant), where $n$ is the size of the SSAT instance. In this paper we prove this conjecture assuming the Projection Games Conjecture(PGC), given by Moshkovitz (2012). This implies hardness of approximation of SVP and CVP within polynomial factors, assuming PGC. We also reduce SSAT to the Nearest Codeword Problem(NCP) and Learning Halfspace Problem(LHP), as considered by Arora et al.(1997). This proves that both these problems are NP-hard to approximate within a factor of $N^{c'/\log\log n}$($c'>0$ is constant) where $N$ is the size of the instances of the respective problems. Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors.
Reinforcement Learning with Chromatic Networks for Compact Architecture Search
Venue: arXiv cs.NE 2021
Year: 2021

We present a neural architecture search algorithm to construct compact reinforcement learning (RL) policies, by combining ENAS and ES in a highly scalable and intuitive way. By defining the combinatorial search space of NAS to be the set of different edge-partitionings (colorings) into same-weight classes, we represent compact architectures via efficient learned edge-partitionings. For several RL tasks, we manage to learn colorings translating to effective policies parameterized by as few as $17$ weight parameters, providing >90% compression over vanilla policies and 6x compression over state-of-the-art compact policies based on Toeplitz matrices, while still maintaining good reward. We believe that our work is one of the first attempts to propose a rigorous approach to training structured neural network architectures for RL problems that are of interest especially in mobile robotics with limited storage and computational resources.
Data Structures Meet Cryptography: 3SUM with Preprocessing
Venue: arXiv cs.DS 2021
Year: 2021

This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic applications, and data structure lower bounds, as summarized next. First, we apply Fiat--Naor inversion, a technique with cryptographic origins, to obtain a data structure upper bound. In particular, our technique yields a suite of algorithms with space $S$ and (online) time $T$ for a preprocessing version of the $N$-input 3SUM problem where $S^3\cdot T = \widetilde{O}(N^6)$. This disproves a strong conjecture (Goldstein et al., WADS 2017) that there is no data structure that solves this problem for $S=N^{2-δ}$ and $T = N^{1-δ}$ for any constant $δ>0$. Secondly, we show equivalence between lower bounds for a broad class of (static) data structure problems and one-way functions in the random oracle model that resist a very strong form of preprocessing attack. Concretely, given a random function $F: [N] \to [N]$ (accessed as an oracle) we show how to compile it into a function $G^F: [N^2] \to [N^2]$ which resists $S$-bit preprocessing attacks that run in query time $T$ where $ST=O(N^{2-\varepsilon})$ (assuming a corresponding data structure lower bound on 3SUM). In contrast, a classical result of Hellman tells us that $F$ itself can be more easily inverted, say with $N^{2/3}$-bit preprocessing in $N^{2/3}$ time. We also show that much stronger lower bounds follow from the hardness of kSUM. Our results can be equivalently interpreted as security against adversaries that are very non-uniform, or have large auxiliary input, or as security in the face of a powerfully backdoored random oracle. Thirdly, we give non-adaptive lower bounds for 3SUM and a range of geometric problems which match the best known lower bounds for static data structure problems.
A Sufficient Statistic for Influence in Structured Multiagent Environments
Venue: arXiv cs.AI 2021
Year: 2021

Making decisions in complex environments is a key challenge in artificial intelligence (AI). Situations involving multiple decision makers are particularly complex, leading to computational intractability of principled solution methods. A body of work in AI has tried to mitigate this problem by trying to distill interaction to its essence: how does the policy of one agent influence another agent? If we can find more compact representations of such influence, this can help us deal with the complexity, for instance by searching the space of influences rather than the space of policies. However, so far these notions of influence have been restricted in their applicability to special cases of interaction. In this paper we formalize influence-based abstraction (IBA), which facilitates the elimination of latent state factors without any loss in value, for a very general class of problems described as factored partially observable stochastic games (fPOSGs). On the one hand, this generalizes existing descriptions of influence, and thus can serve as the foundation for improvements in scalability and other insights in decision making in complex multiagent settings. On the other hand, since the presence of other agents can be seen as a generalization of single agent settings, our formulation of IBA also provides a sufficient statistic for decision making under abstraction for a single agent. We also give a detailed discussion of the relations to such previous works, identifying new insights and interpretations of these approaches. In these ways, this paper deepens our understanding of abstraction in a wide range of sequential decision making settings, providing the basis for new approaches and algorithms for a large class of problems.
Modeling question asking using neural program generation
Venue: arXiv cs.CL 2021
Year: 2021

People ask questions that are far richer, more informative, and more creative than current AI systems. We propose a neuro-symbolic framework for modeling human question asking, which represents questions as formal programs and generates programs with an encoder-decoder based deep neural network. From extensive experiments using an information-search game, we show that our method can predict which questions humans are likely to ask in unconstrained settings. We also propose a novel grammar-based question generation framework trained with reinforcement learning, which is able to generate creative questions without supervised human data.
The Price of Anarchy in Routing Games as a Function of the Demand
Venue: arXiv cs.GT 2021
Year: 2021

The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.
Observability Analysis for Large-Scale Power Systems Using Factor Graphs
Venue: arXiv cs.IT 2021
Year: 2021

The state estimation algorithm estimates the values of the state variables based on the measurement model described as the system of equations. Prior to applying the state estimation algorithm, the existence and uniqueness of the solution of the underlying system of equations is determined through the observability analysis. If a unique solution does not exist, the observability analysis defines observable islands and further defines an additional set of equations (measurements) needed to determine a unique solution. For the first time, we utilise factor graphs and Gaussian belief propagation algorithm to define a novel observability analysis approach. The observable islands and placement of measurements to restore observability are identified by following the evolution of variances across the iterations of the Gaussian belief propagation algorithm over the factor graph. Due to sparsity of the underlying power network, the resulting method has the linear computational complexity (assuming a constant number of iterations) making it particularly suitable for solving large-scale systems. The method can be flexibly matched to distributed computational resources, allowing for determination of observable islands and observability restoration in a distributed fashion. Finally, we discuss performances of the proposed observability analysis using power systems whose size ranges between 1354 and 70000 buses.
Distributional Analysis of Polysemous Function Words
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we are concerned with the phenomenon of function word polysemy. We adopt the framework of distributional semantics, which characterizes word meaning by observing occurrence contexts in large corpora and which is in principle well situated to model polysemy. Nevertheless, function words were traditionally considered as impossible to analyze distributionally due to their highly flexible usage patterns. We establish that contextualized word embeddings, the most recent generation of distributional methods, offer hope in this regard. Using the German reflexive pronoun 'sich' as an example, we find that contextualized word embeddings capture theoretically motivated word senses for 'sich' to the extent to which these senses are mirrored systematically in linguistic usage.
Fair and Efficient Cake Division with Connected Pieces
Venue: arXiv cs.GT 2021
Year: 2021

The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with distinct preferences. Focusing on a standard formulation of cake cutting, in which each agent must receive a contiguous piece of the cake, this work establishes algorithmic and hardness results for multiple fairness/efficiency measures. First, we consider the well-studied notion of envy-freeness and develop an efficient algorithm that finds a cake division (with connected pieces) wherein the envy is multiplicatively within a factor of 2+o(1). The same algorithm in fact achieves an approximation ratio of 3+o(1) for the problem of finding cake divisions with as large a Nash social welfare (NSW) as possible. NSW is another standard measure of fairness and this work also establishes a connection between envy-freeness and NSW: approximately envy-free cake divisions (with connected pieces) always have near-optimal Nash social welfare. Furthermore, we develop an approximation algorithm for maximizing the $ρ$-mean welfare--this unifying objective, with different values of $ρ$, interpolates between notions of fairness (NSW) and efficiency (average social welfare). Finally, we complement these algorithmic results by proving that maximizing NSW (and, in general, the $ρ$-mean welfare) is APX-hard in the cake-division context.
Confounder-Aware Visualization of ConvNets
Venue: arXiv cs.LG 2021
Year: 2021

With recent advances in deep learning, neuroimaging studies increasingly rely on convolutional networks (ConvNets) to predict diagnosis based on MR images. To gain a better understanding of how a disease impacts the brain, the studies visualize the salience maps of the ConvNet highlighting voxels within the brain majorly contributing to the prediction. However, these salience maps are generally confounded, i.e., some salient regions are more predictive of confounding variables (such as age) than the diagnosis. To avoid such misinterpretation, we propose in this paper an approach that aims to visualize confounder-free saliency maps that only highlight voxels predictive of the diagnosis. The approach incorporates univariate statistical tests to identify confounding effects within the intermediate features learned by ConvNet. The influence from the subset of confounded features is then removed by a novel partial back-propagation procedure. We use this two-step approach to visualize confounder-free saliency maps extracted from synthetic and two real datasets. These experiments reveal the potential of our visualization in producing unbiased model-interpretation.
Compiling With Classical Connectives
Venue: arXiv cs.LO 2021
Year: 2021

The study of polarity in computation has revealed that an "ideal" programming language combines both call-by-value and call-by-name evaluation; the two calling conventions are each ideal for half the types in a programming language. But this binary choice leaves out call-by-need which is used in practice to implement lazy-by-default languages like Haskell. We show how the notion of polarity can be extended beyond the value/name dichotomy to include call-by-need by adding a mechanism for sharing which is enough to compile a Haskell-like functional language with user-defined types. The key to capturing sharing in this mixed-evaluation setting is to generalize the usual notion of polarity "shifts:" rather than just two shifts (between positive and negative) we have a family of four dual shifts. We expand on this idea of logical duality -- "and" is dual to "or;" proof is dual to refutation -- for the purpose of compiling a variety of types. Based on a general notion of data and codata, we show how classical connectives can be used to encode a wide range of built-in and user-defined types. In contrast with an intuitionistic logic corresponding to pure functional programming, these classical connectives bring more of the pleasant symmetries of classical logic to the computationally-relevant, constructive setting. In particular, an involutive pair of negations bridges the gulf between the wide-spread notions of parametric polymorphism and abstract data types in programming languages. To complete the study of duality in compilation, we also consider the dual to call-by-need evaluation, which shares the computation within the control flow of a program instead of computation within the information flow.