OpenRaiser/Intern-Atlas huggingface dataset:
Derandomization from Algebraic Hardness
Venue: arXiv cs.CC 2020
Year: 2020

A hitting-set generator (HSG) is a polynomial map $G:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ G$ is nonzero. In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following over any field of characteristic zero: Let $k\in \mathbb{N}$ and $δ> 0$ be arbitrary constants. Suppose $\{P_d\}_{d\in \mathbb{N}}$ is an explicit family of $k$-variate polynomials such that $\operatorname{deg} P_d = d$ and $P_d$ requires algebraic circuits of size $d^δ$. Then, there are explicit hitting sets of polynomial size for $\mathsf{VP}$. This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. As a direct consequence, we show that even saving a single point from the "trivial" explicit, exponential sized hitting sets for constant-variate polynomials of low individual degree which are computable by small circuits, implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following: Let $k\in \mathbb{N}$ and $δ> 0$ be arbitrary constants. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$-variate polynomials of individual degree $s$ that are computable by size $s^δ$ circuits. Then there is an explicit hitting set of size $\operatorname{poly}(s)$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits. As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $τ$-Conjecture of Shub and Smale is true.
Accurate Energetic Constraints for Passive Grasp Stability Analysis
Venue: arXiv cs.RO 2020
Year: 2020

Passive reaction effects in grasp stability analysis occur when the contact forces and joint torques applied by a grasp change in response to external disturbances applied to the grasped object. For example, nonbackdrivable actuators (e.g. highly geared servos) will passively resist external disturbances without an actively applied command; for numerous robot hands using such motors, these effects can be highly beneficial as they increase grasp resistance without requiring active control. We introduce a grasp stability analysis method that can model these effects, and, for a given grasp, distinguish between disturbances that will be passively resisted and those that will not. We find that, in order to achieve this, the grasp model must include accurate energetic constraints. One way to achieve this is to consider the Maximum Dissipation Principle (MDP), a part of the Coulomb friction model that is rarely used in grasp stability analysis. However, the MDP constraints are non-convex, and difficult to solve efficiently. We thus introduce a convex relaxation method, along with an algorithm that successively refines this relaxation locally in order to obtain solutions to arbitrary accuracy efficiently. Our resulting algorithm can determine if a grasp is passively stable, solve for equilibrium contact forces and compute optimal actuator commands for stability. Its implementation is publicly available as part of the open-source GraspIt! simulator.
Matching for the Israeli "Mechinot" Gap-Year Programs: Handling Rich Diversity Requirements
Venue: arXiv cs.GT 2020
Year: 2020

We describe our experience with designing and running a matching market for the Israeli "Mechinot" gap-year programs. The main conceptual challenge in the design of this market was the rich set of diversity considerations, which necessitated the development of an appropriate preference-specification language along with corresponding choice-function semantics, which we also theoretically analyze. Our contribution extends the existing toolbox for two-sided matching with soft constraints. This market was run for the first time in January 2018 and matched 1,607 candidates (out of a total of 3,120 candidates) to 35 different programs, has been run twice more since, and has been adopted by the Joint Council of the "Mechinot" gap-year programs for the foreseeable future.
Differential privacy with partial knowledge
Venue: arXiv cs.CR 2020
Year: 2020

Differential privacy offers formal quantitative guarantees for algorithms over datasets, but it assumes attackers that know and can influence all but one record in the database. This assumption often vastly overapproximates the attackers' actual strength, resulting in unnecessarily poor utility. Recent work has made significant steps towards privacy in the presence of partial background knowledge, which can model a realistic attacker's uncertainty. Prior work, however, has definitional problems for correlated data and does not precisely characterize the underlying attacker model. We propose a practical criterion to prevent problems due to correlations, and we show how to characterize attackers with limited influence or only partial background knowledge over the dataset. We use these foundations to analyze practical scenarios: we significantly improve known results about the privacy of counting queries under partial knowledge, and we show that thresholding can provide formal guarantees against such weak attackers, even with little entropy in the data. These results allow us to draw novel links between k-anonymity and differential privacy under partial knowledge. Finally, we prove composition results on differential privacy with partial knowledge, which quantifies the privacy leakage of complex mechanisms. Our work provides a basis for formally quantifying the privacy of many widely-used mechanisms, e.g. publishing the result of surveys, elections or referendums, and releasing usage statistics of online services.
Internet of Intelligence: The Collective Advantage for Advancing Communications and Intelligence
Venue: arXiv cs.AI 2020
Year: 2020

The fifth-generation cellular networks (5G) has boosted the unprecedented convergence between the information world and physical world. On the other hand, empowered with the enormous amount of data and information, artificial intelligence (AI) has been universally applied and pervasive AI is believed to be an integral part of the six-generation cellular networks (6G). Consequently, benefiting from the advancement in communication technology and AI, we boldly argue that the conditions for collective intelligence (CI) will be mature in the 6G era and CI will emerge among the widely connected beings and things. Afterwards, we highlight the potential huge impact of CI on both communications and intelligence. In particular, we introduce a regular language (i.e., the information economy metalanguage) supporting the future collective communications to augment human intelligence and explain its potential applications in naming Internet information and pushing information centric networks forward. Meanwhile, we propose a stigmergy-based federated collective intelligence and demonstrate its achievement in a simulated scenario where the agents collectively work together to form a pattern through simple indirect communications. In a word, CI could advance both communications and intelligence.
Static Pricing: Universal Guarantees for Reusable Resources
Venue: arXiv cs.DS 2020
Year: 2020

We consider a fundamental pricing model in which a fixed number of units of a reusable resource are used to serve customers. Customers arrive to the system according to a stochastic process and upon arrival decide whether or not to purchase the service, depending on their willingness-to-pay and the current price. The service time during which the resource is used by the customer is stochastic and the firm may incur a service cost. This model represents various markets for reusable resources such as cloud computing, shared vehicles, rotable parts, and hotel rooms. In the present paper, we analyze this pricing problem when the firm attempts to maximize a weighted combination of three central metrics: profit, market share, and service level. Under Poisson arrivals, exponential service times, and standard assumptions on the willingness-to-pay distribution, we establish a series of results that characterize the performance of static pricing in such environments. In particular, while an optimal policy is fully dynamic in such a context, we prove that a static pricing policy simultaneously guarantees 78.9% of the profit, market share, and service level from the optimal policy. Notably, this result holds for any service rate and number of units the firm operates. Our proof technique relies on a judicious construction of a static price that is derived directly from the optimal dynamic pricing policy. In the special case where there are two units and the induced demand is linear, we also prove that the static policy guarantees 95.5% of the profit from the optimal policy. Our numerical findings on a large testbed of instances suggest that the latter result is quite indicative of the profit obtained by the static pricing policy across all parameters.
On the smoothness of nonlinear system identification
Venue: arXiv cs.SY 2020
Year: 2020

We shed new light on the \textit{smoothness} of optimization problems arising in prediction error parameter estimation of linear and nonlinear systems. We show that for regions of the parameter space where the model is not contractive, the Lipschitz constant and $β$-smoothness of the objective function might blow up exponentially with the simulation length, making it hard to numerically find minima within those regions or, even, to escape from them. In addition to providing theoretical understanding of this problem, this paper also proposes the use of multiple shooting as a viable solution. The proposed method minimizes the error between a prediction model and the observed values. Rather than running the prediction model over the entire dataset, multiple shooting splits the data into smaller subsets and runs the prediction model over each subset, making the simulation length a design parameter and making it possible to solve problems that would be infeasible using a standard approach. The equivalence to the original problem is obtained by including constraints in the optimization. The new method is illustrated by estimating the parameters of nonlinear systems with chaotic or unstable behavior, as well as neural networks. We also present a comparative analysis of the proposed method with multi-step-ahead prediction error minimization.
Capacity Limits of Full-Duplex Cellular Network
Venue: arXiv cs.IT 2020
Year: 2020

This paper aims to characterize the capacity limits of a wireless cellular network with a full-duplex (FD) base-station (BS) and half-duplex user terminals, in which three independent messages are communicated: the uplink message $m_1$ from the uplink user to the BS, the downlink message $m_2$ from the BS to the downlink user, and the device-to-device (D2D) message $m_3$ from the uplink user to the downlink user. From an information theoretical perspective, the overall network can be viewed as a generalization of the FD relay broadcast channel with a side message transmitted from the relay to the destination. We begin with a simpler case that involves the uplink and downlink transmissions of $(m_1,m_2)$ only, and propose an achievable rate region based on a novel strategy that uses the BS as a FD relay to facilitate the interference cancellation at the downlink user. We also prove a new converse, which is strictly tighter than the cut-set bound, and characterize the capacity region of the scalar Gaussian FD network without a D2D message to within a constant gap. This paper further studies a general setup wherein $(m_1,m_2,m_3)$ are communicated simultaneously. To account for the D2D message, we incorporate Marton's broadcast coding into the previous scheme to obtain a larger achievable rate region than the existing ones in the literature. We also improve the cut-set bound by means of genie and show that by using one of the two simple rate-splitting schemes, the capacity region of the scalar Gaussian FD network with a D2D message can already be reached to within a constant gap. Finally, a generalization to the vector Gaussian channel case is discussed. Simulation results demonstrate the advantage of using the BS as relay in enhancing the throughput of the FD cellular network.
Disentangling Factors of Variation Using Few Labels
Venue: arXiv cs.LG 2020
Year: 2020

Learning disentangled representations is considered a cornerstone problem in representation learning. Recently, Locatello et al. (2019) demonstrated that unsupervised disentanglement learning without inductive biases is theoretically impossible and that existing inductive biases and unsupervised methods do not allow to consistently learn disentangled representations. However, in many practical settings, one might have access to a limited amount of supervision, for example through manual labeling of (some) factors of variation in a few training examples. In this paper, we investigate the impact of such supervision on state-of-the-art disentanglement methods and perform a large scale study, training over 52000 models under well-defined and reproducible experimental conditions. We observe that a small number of labeled examples (0.01--0.5\% of the data set), with potentially imprecise and incomplete labels, is sufficient to perform model selection on state-of-the-art unsupervised models. Further, we investigate the benefit of incorporating supervision into the training process. Overall, we empirically validate that with little and imprecise supervision it is possible to reliably learn disentangled representations.
Convolution, attention and structure embedding
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks are composed of layers of parametrised linear operations intertwined with non linear activations. In basic models, such as the multi-layer perceptron, a linear layer operates on a simple input vector embedding of the instance being processed, and produces an output vector embedding by straight multiplication by a matrix parameter. In more complex models, the input and output are structured and their embeddings are higher order tensors. The parameter of each linear operation must then be controlled so as not to explode with the complexity of the structures involved. This is essentially the role of convolution models, which exist in many flavours dependent on the type of structure they deal with (grids, networks, time series etc.). We present here a unified framework which aims at capturing the essence of these diverse models, allowing a systematic analysis of their properties and their mutual enrichment. We also show that attention models naturally fit in the same framework: attention is convolution in which the structure itself is adaptive, and learnt, instead of being given a priori.
A categorical construction for the computational definition of vector spaces
Venue: arXiv cs.LO 2020
Year: 2020

Lambda-S is an extension to first-order lambda calculus unifying two approaches of non-cloning in quantum lambda-calculi. One is to forbid duplication of variables, while the other is to consider all lambda-terms as algebraic linear functions. The type system of Lambda-S has a constructor S such that a type A is considered as the base of a vector space while S(A) is its span. Lambda-S can also be seen as a language for the computational manipulation of vector spaces: The vector spaces axioms are given as a rewrite system, describing the computational steps to be performed. In this paper we give an abstract categorical semantics of Lambda-S* (a fragment of Lambda-S), showing that S can be interpreted as the composition of two functors in an adjunction relation between a Cartesian category and an additive symmetric monoidal category. The right adjoint is a forgetful functor U, which is hidden in the language, and plays a central role in the computational reasoning.
New reduction rules for the tree bisection and reconnection distance
Venue: arXiv cs.DS 2020
Year: 2020

Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most 15k-9 taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees, and that this bound is tight. Here we propose five new reduction rules and show that these further reduce the bound to 11k-9. The new rules combine the ``unrooted generator'' approach introduced in [Kelk and Linz 2018] with a careful analysis of agreement forests to identify (i) situations when chains of length 3 can be further shortened without reducing the TBR distance, and (ii) situations when small subtrees can be identified whose deletion is guaranteed to reduce the TBR distance by 1. To the best of our knowledge these are the first reduction rules that strictly enhance the reductive power of the subtree and chain reduction rules.
Automatic 4D Facial Expression Recognition via Collaborative Cross-domain Dynamic Image Network
Venue: arXiv cs.CV 2020
Year: 2020

This paper proposes a novel 4D Facial Expression Recognition (FER) method using Collaborative Cross-domain Dynamic Image Network (CCDN). Given a 4D data of face scans, we first compute its geometrical images, and then combine their correlated information in the proposed cross-domain image representations. The acquired set is then used to generate cross-domain dynamic images (CDI) via rank pooling that encapsulates facial deformations over time in terms of a single image. For the training phase, these CDIs are fed into an end-to-end deep learning model, and the resultant predictions collaborate over multi-views for performance gain in expression classification. Furthermore, we propose a 4D augmentation scheme that not only expands the training data scale but also introduces significant facial muscle movement patterns to improve the FER performance. Results from extensive experiments on the commonly used BU-4DFE dataset under widely adopted settings show that our proposed method outperforms the state-of-the-art 4D FER methods by achieving an accuracy of 96.5% indicating its effectiveness.
Evaluating Cascading Impact of Attacks on Resilience of Industrial Control Systems: A Design-Centric Modeling Approach
Venue: arXiv cs.CR 2020
Year: 2020

A design-centric modeling approach was proposed to model the behaviour of the physical processes controlled by Industrial Control Systems (ICS) and study the cascading impact of data-oriented attacks. A threat model was used as input to guide the construction of the CPS model where control components which are within the adversary's intent and capabilities are extracted. The relevant control components are subsequently modeled together with their control dependencies and operational design specifications. The approach was demonstrated and validated on a water treatment testbed. Attacks were simulated on the testbed model where its resilience to attacks was evaluated using proposed metrics such as Impact Ratio and Time-to-Critical-State. From the analysis of the attacks, design strengths and weaknesses were identified and design improvements were recommended to increase the testbed's resilience to attacks.
PerceptNet: Learning Perceptual Similarity of Haptic Textures in Presence of Unorderable Triplets
Venue: arXiv cs.LG 2020
Year: 2020

In order to design haptic icons or build a haptic vocabulary, we require a set of easily distinguishable haptic signals to avoid perceptual ambiguity, which in turn requires a way to accurately estimate the perceptual (dis)similarity of such signals. In this work, we present a novel method to learn such a perceptual metric based on data from human studies. Our method is based on a deep neural network that projects signals to an embedding space where the natural Euclidean distance accurately models the degree of dissimilarity between two signals. The network is trained only on non-numerical comparisons of triplets of signals, using a novel triplet loss that considers both types of triplets that are easy to order (inequality constraints), as well as those that are unorderable/ambiguous (equality constraints). Unlike prior MDS-based non-parametric approaches, our method can be trained on a partial set of comparisons and can embed new haptic signals without retraining the model from scratch. Extensive experimental evaluations show that our method is significantly more effective at modeling perceptual dissimilarity than alternatives.
Prioritized Inverse Kinematics: Nonsmoothness, Trajectory Existence, Task Convergence, Stability
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, we study various theoretical properties of a class of prioritized inverse kinematics (PIK) solutions that can be considered as a class of (output regulation or tracking) control laws of a dynamical system with prioritized multiple outputs. We first develop tools to investigate nonsmoothness of PIK solutions and find a sufficient condition for nonsmoothness. It implies that existence and uniqueness of a joint trajectory satisfying a PIK solution cannot be guaranteed by the classical theorems. So, we construct an alternative existence and uniqueness theorem that uses structural information of PIK solutions. Then, we narrow the class of PIK solutions down to the case that all tasks are designed to follow some desired task trajectories and discover a few properties related to task convergence. The study goes further to analyze stability of equilibrium points of the differential equation whose right hand side is a PIK solution when all tasks are designed to reach some desired task positions. Finally, we furnish an example with a two-link manipulator that shows how our findings can be used to analyze the behavior of a joint trajectory generated from a PIK solution.
Fundamental Limits of Identification System With Secret Binding Under Noisy Enrollment
Venue: arXiv cs.IT 2020
Year: 2020

We study the fundamental limits of biometric identification systems with chosen secret from an information theoretic perspective. Ignatenko and Willems (2015) characterized the capacity region of identification, secrecy, and privacy-leakage rates of the system provided that the enrollment channel is noiseless. In the enrollment process, however, it is highly considered that noise occurs when bio-data is scanned. Recently, Yachongka and Yagi (2019) characterized the capacity region of the system with generated secret considering noisy enrollment and template constraint. In this paper, we are interested in characterizing the capacity region of identification, secrecy, template, and privacy-leakage rates of the system with chosen secret under the same settings as Yachongka and Yagi (2019). As special cases, the obtained result shows that the characterization reduces to the one given by Ignatenko and Willems (2015) where the enrollment channel is noiseless and there is no constraint on the template rate, and it also coincides with the result derived by Günlü and Kramer (2018) where there is only one individual.