cssi/SciSciGPT-SciSciNet huggingface dataset:
Geometric complexity theory V: Efficient algorithms for Noether normalization

We study a basic algorithmic problem in algebraic geometry, which we call NNL, of constructing a normalizing map as per Noether's Normalization Lemma. For general explicit varieties, as formally defined in this paper, we give a randomized polynomial-time Monte Carlo algorithm for this problem. For some interesting cases of explicit varieties, we give deterministic quasi-polynomial time algorithms. These may be contrasted with the standard EXPSPACE-algorithms for these problems in computational algebraic geometry. In particular, we show that: (1) The categorical quotient for any finite dimensional representation $V$ of $SL_m$, with constant $m$, is explicit in characteristic zero. (2) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in the dimension of $V$. (3) The categorical quotient of the space of $r$-tuples of $m \times m$ matrices by the simultaneous conjugation action of $SL_m$ is explicit in any characteristic. (4) NNL for this categorical quotient can be solved deterministically in time quasi-polynomial in $m$ and $r$ in any characteristic $p$ not in $[2,\ m/2]$. (5) NNL for every explicit variety in zero or large enough characteristic can be solved deterministically in quasi-polynomial time, assuming the hardness hypothesis for the permanent in geometric complexity theory. The last result leads to a geometric complexity theory approach to put NNL for every explicit variety in P.
Asymptotics for the Fourier coefficients of eta-quotients

Abstract We study the asymptotics for the Fourier coefficients of a broad class of eta-quotients, ∏ r = 1 R ( ∏ k ≥ 1 ( 1 − q m r k ) ) δ r , where m 1 , … , m R are R distinct positive integers and δ 1 , … , δ R are R non-zero integers with ∑ r = 1 R δ r ≥ 0 .
Performance Bounds for Nash Equilibria in Submodular Utility Systems with User Groups

It is shown that for a valid non-cooperative utility system, if the social utility function is submodular, then any Nash equilibrium achieves at least 1 / 2 of the optimal social utility, subject to a function-dependent additive term. Moreover, if the social utility function is nondecreasing and submodular, then any Nash equilibrium achieves at least of the optimal social utility, where c is the curvature of the social utility function. In this paper, we consider variations of the utility system considered by Vetta, in which users are grouped together. Our aim is to establish how grouping and cooperation among users affect performance bounds. We consider two types of grouping. The first type is from a previous paper, where each user belongs to a group of users having social ties with it. For this type of utility system, each user’s strategy maximises its social group utility function, giving rise to the notion of social-aware Nash equilibrium. We prove that this social utility system yields to the boundin...
Semi-log canonical vs F-pure singularities

Abstract If X is Frobenius split, then so is its normalization and we explore conditions which imply the converse. To do this, we recall that given an O X -linear map ϕ : F ⁎ O X → O X , it always extends to a map ϕ ¯ on the normalization of X. In this paper, we study when the surjectivity of ϕ ¯ implies the surjectivity of ϕ. While this doesnʼt occur generally, we show it always happens if certain tameness conditions are satisfied for the normalization map. Our result has geometric consequences including a connection between F-pure singularities and semi-log canonical singularities, and a more familiar version of the (F-)inversion of adjunction formula.
Simplicity of eigenvalues and non-vanishing of eigenfunctions of a quantum graph

We prove that after an arbitrarily small adjustment of edge lengths, the spectrum of a compact quantum graph with δ-type vertex conditions can be simple. We also show that the eigenfunctions, with the exception of those living entirely on a looping edge, can be made to be non-vanishing on all vertices of the graph. As an application of the above result, we establish that the secular manifold (also called “determinant manifold”) of a large family of graphs has exactly two smooth connected components.
Unpaired Image-to-Image Translation Using Cycle-Consistent Adversarial Networks

Image-to-image translation is a class of vision and graphics problems where the goal is to learn the mapping between an input image and an output image using a training set of aligned image pairs. However, for many tasks, paired training data will not be available. We present an approach for learning to translate an image from a source domain X to a target domain Y in the absence of paired examples. Our goal is to learn a mapping G : X → Y such that the distribution of images from G(X) is indistinguishable from the distribution Y using an adversarial loss. Because this mapping is highly under-constrained, we couple it with an inverse mapping F : Y → X and introduce a cycle consistency loss to push F(G(X)) ≈ X (and vice versa). Qualitative results are presented on several tasks where paired training data does not exist, including collection style transfer, object transfiguration, season transfer, photo enhancement, etc. Quantitative comparisons against several prior methods demonstrate the superiority of our approach.
Matching Anonymized and Obfuscated Time Series to Users’ Profiles

Many popular applications use traces of user data to offer various services to their users. However, even if user data are anonymized and obfuscated, a user’s privacy can be compromised through the use of statistical matching techniques that match a user trace to prior user behavior. In this paper, we derive the theoretical bounds on the privacy of users in such a scenario. We build on our recent study in the area of location privacy, in which we introduced formal notions of location privacy for anonymization-based location privacy-protection mechanisms. Here, we derive the fundamental limits of user privacy when both anonymization and obfuscation-based protection mechanisms are applied to users’ time series of data. We investigate the impact of such mechanisms on the tradeoff between privacy protection and user utility. We first study achievability results for the case where the time-series of users are governed by an independent and identically distributed (i.i.d.) process. The converse results are proved both for the i.i.d. case as well as the more general Markov chain model. We demonstrate that as the number of users in the network grows, the obfuscation-anonymization plane can be divided into two regions: in the first region, all users have perfect privacy; and, in the second region, no user has privacy.
Studentized Sensitivity Analysis for the Sample Average Treatment Effect in Paired Observational Studies

AbstractA fundamental limitation of causal inference in observational studies is that perceived evidence for an effect might instead be explained by factors not accounted for in the primary analysi...
The Third Workshop on Extremely Precise Radial Velocities: The New Instruments

The Third Workshop on Extremely Precise Radial Velocities was held at the Penn Stater Conference Center and Hotel in State College, Pennsylvania, USA from 2016 August 14 to 17, and featured over 120 registrants from around the world. Here we provide a brief description of the conference, its format, and its session topics and chairs. 23 instrument teams were represented in plenary talks, and we present a table containing the basic characteristics of their new precise Doppler velocimeters.
Commutative pseudo-equality algebras

Pseudo-equality algebras were initially introduced by Jenei and Korodi as a possible algebraic semantic for fuzzy-type theory, and they have been revised by Dvurecenskij and Zahiri under the name of JK-algebras. In this paper, we define and study the commutative pseudo-equality algebras. We give a characterization of commutative pseudo-equality algebras, and we prove that an invariant pseudo-equality algebra is commutative if and only if its corresponding pseudo-BCK(pC)-meet-semilattice is commutative. Other results consist of proving that every commutative pseudo-equality algebra is a distributive lattice and every finite invariant commutative pseudo-equality algebra is a symmetric pseudo-equality algebra. We introduce the notion of a commutative deductive system of a pseudo-equality algebra, and we give equivalent conditions for this notion. As applications of these notions and results, we define and study the measures and measure morphisms on pseudo-equality algebras, we prove new properties of state pseudo-equality algebras, and we introduce and investigate the pseudo-valuations on pseudo-equality algebras. We prove that any measure morphism on a pseudo-equality algebra is a measure on it, and the kernel of a measure is a commutative deductive system. We show that the quotient pseudo-equality algebra over the kernel of a measure is a commutative pseudo-equality algebra. It is also proved that a pseudo-equality algebra possessing an order-determining system is commutative. We prove that the two types of internal states on a pseudo-equality algebra coincide if and only if it is a commutative pseudo-equality algebra. Given a pseudo-equality algebra A, it is proved that the kernel of a commutative pseudo-valuation on A is a commutative deductive system of A. If, moreover, A is commutative, then we prove that any pseudo-valuation on A is commutative.
Understanding and Detecting Supporting Arguments of Diverse Types

We investigate the problem of sentence-level supporting argument detection from relevant documents for user-specified claims. A dataset containing claims and associated citation articles is collected from online debate website idebate.org. We then manually label sentence-level supporting arguments from the documents along with their types as study, factual, opinion, or reasoning. We further characterize arguments of different types, and explore whether leveraging type information can facilitate the supporting arguments detection task. Experimental results show that LambdaMART (Burges, 2010) ranker that uses features informed by argument types yields better performance than the same ranker trained without type information.
Strong minimality and the j-function

We show that the order three algebraic differential equation over ${\mathbb Q}$ satisfied by the analytic $j$-function defines a non-$\aleph_0$-categorical strongly minimal set with trivial forking geometry relative to the theory of differentially closed fields of characteristic zero answering a long-standing open problem about the existence of such sets. The theorem follows from Pila's modular Ax-Lindemann-Weierstrass with derivatives theorem using Seidenberg's embedding theorem and a theorem of Nishioka on the differential equations satisfied by automorphic functions. As a by product of this analysis, we obtain a more general version of the modular Ax-Lindemann-Weierstrass theorem, which, in particular, applies to automorphic functions for arbitrary arithmetic subgroups of $SL_2 ({\mathbb Z})$. We then apply the results to prove effective finiteness results for intersections of subvarieties of products of modular curves with isogeny classes. For example, we show that if $\psi:{\mathbb P}^1 \to {\mathbb P}^1$ is any non-identity automorphism of the projective line and $t \in {\mathbb A}^1({\mathbb C}) \smallsetminus {\mathbb A}^1({\mathbb Q}^\text{alg})$, then the set of $s \in {\mathbb A}^1({\mathbb C})$ for which the elliptic curve with $j$-invariant $s$ is isogenous to the elliptic curve with $j$-invariant $t$ and the elliptic curve with $j$-invariant $\psi(s)$ is isogenous to the elliptic curve with $j$-invariant $\psi(t)$ has size at most $36^7$. In general, we prove that if $V$ is a Kolchin-closed subset of ${\mathbb A}^n$, then the Zariski closure of the intersection of $V$ with the isogeny class of a tuple of transcendental elements is a finite union of weakly special subvarieties. We bound the sum of the degrees of the irreducible components of this union by a function of the degree and order of $V$.
Small generalized breathers with exponentially small tails for Klein–Gordon equations

Abstract We consider a class of nonlinear Klein–Gordon equation u t t = u x x − u + f ( u ) and show that generically there exist small breathers with exponentially small tails.
Distinct partial sums in cyclic groups: polynomial method and constructive approaches

Let $(G,+)$ be an abelian group and consider a subset $A \subseteq G$ with $|A|=k$. Given an ordering $(a_1, \ldots, a_k)$ of the elements of $A$, define its {\em partial sums} by $s_0 = 0$ and $s_j = \sum_{i=1}^j a_i$ for $1 \leq j \leq k$. We consider the following conjecture of Alspach: For any cyclic group $\Z_n$ and any subset $A \subseteq \Z_n \setminus \{0\}$ with $s_k \neq 0$, it is possible to find an ordering of the elements of $A$ such that no two of its partial sums $s_i$ and $s_j$ are equal for $0 \leq i < j \leq k$. We show that Alspach's Conjecture holds for prime $n$ when $k \geq n-3$ and when $k \leq 10$. The former result is by direct construction, the latter is non-constructive and uses the polynomial method. We also use the polynomial method to show that for prime $n$ a sequence of length $k$ having distinct partial sums exists in any subset of $\Z_n \setminus \{0\}$ of size at least $2k- \sqrt{8k}$ in all but at most a bounded number of cases.
Infinite dimensional generalizations of Choi’s Theorem

In this paper we give a simple sequence of necessary and sufficient finite dimensional conditions for a positive map between certain subspaces of bounded linear operators on separable Hilbert spaces to be completely positive. These criterions are natural generalization of Choi's characterization for completely positive maps between pairs of linear operators on finite dimensional Hilbert spaces. We apply our conditions to a completely positive map between two trace class operators on separable Hilbert spaces. A map $\mu$ is called a quantum channel, if it is trace preserving, and $\mu$ is called a quantum subchannel if it decreases the trace of a positive operator. We give simple neccesary and sufficient condtions for $\mu$ to be a quantum subchannel. We show that $\mu$ is a quantum subchannel if and only if it has Hellwig-Kraus representation. The last result extends the classical results of Kraus and the recent result of Holevo for characterization of a quantum channel.
Sparse-GEV: Sparse Latent Space Model for Multivariate Extreme Value Time Serie Modeling

In many applications of time series models, such as climate analysis and social media analysis, we are often interested in extreme events, such as heatwave, wind gust, and burst of topics. These time series data usually exhibit a heavy-tailed distribution rather than a Gaussian distribution. This poses great challenges to existing approaches due to the significantly different assumptions on the data distributions and the lack of sufficient past data on extreme events. In this paper, we propose the Sparse-GEV model, a latent state model based on the theory of extreme value modeling to automatically learn sparse temporal dependence and make predictions. Our model is theoretically significant because it is among the first models to learn sparse temporal dependencies among multivariate extreme value time series. We demonstrate the superior performance of our algorithm to the state-of-art methods, including Granger causality, copula approach, and transfer entropy, on one synthetic dataset, one climate dataset and two Twitter datasets.
Selections and their absolutely continuous invariant measures

Abstract Let I = [ 0 , 1 ] and let P be a partition of I into a finite number of intervals. Let τ 1 , τ 2 ; I → I be two piecewise expanding maps on P. Let G ⊂ I × I be the region between the boundaries of the graphs of τ 1 and τ 2 . Any map τ : I → I that takes values in G is called a selection of the multivalued map defined by G. There are many results devoted to the study of the existence of selections with specified topological properties. However, there are no results concerning the existence of selection with measure-theoretic properties. In this paper we prove the existence of selections which have absolutely continuous invariant measures (acim). By our assumptions we know that τ 1 and τ 2 possess acims preserving the distribution functions F ( 1 ) and F ( 2 ) . The main result shows that for any convex combination F of F ( 1 ) and F ( 2 ) we can find a map η with values between the graphs of τ 1 and τ 2 (that is, a selection) such that F is the η-invariant distribution function. Examples are presented. We also study the relationship of the dynamics of our multivalued maps to random maps.
Non-slice linear combinations of algebraic knots

We show that the subgroup of the knot concordance group generated by links of isolated complex singularities intersects the subgroup of algebraically slice knots in an infinite rank subgroup.
Tensor representations of $\mathfrak q(\infty)$

We introduce a symmetric monoidal category of modules over the direct limit queer superalgebra ${\mathfrak{q}}(\infty )$. This category can be defined in two equivalent ways with the aid of the large annihilator condition. Tensor products of copies of the natural and the conatural representations are injective objects in this category. We obtain the socle filtrations and formulas for the tensor products of the indecomposable injectives. In addition, it is proven that the category is Koszul self-dual.
Coalgebraic models for combinatorial model categories

We show that the category of algebraically cofibrant objects in a combinatorial and simplicial model category A has a model structure that is left-induced from that on A. In particular it follows that any presentable model category is Quillen equivalent (via a single Quillen equivalence) to one in which all objects are cofibrant.
Location Privacy in Spatial Crowdsourcing

Spatial crowdsourcing (SC) is a new platform that engages individuals in collecting and analyzing environmental, social and other spatiotemporal information. With SC, requesters outsource their spatiotemporal tasks (tasks associated with location and time) to a set of workers, who will perform the tasks by physically traveling to the tasks’ locations. However, current solutions require the locations of the workers and/or the tasks to be disclosed to untrusted entities (SC server) for effective assignments of tasks to workers.
Completion time in multi-access channel: An information theoretic perspective

In a multi-access channel, completion time refers to the number of channel uses required for users, each with some given fixed bit pool, to complete the transmission of all their data bits. In this paper, the characterization of the completion time region is based on the concept of constrained rates, where users' rates are defined over possibly different number of channel uses. An information theoretic formulation of completion time is given and the completion time region is then established for two-user Gaussian multi-access channel, which, analogous to capacity region, characterizes all possible trade-offs between users' completion times.
Millimeter-Wave Beamformed Full-Dimensional MIMO Channel Estimation Based on Atomic Norm Minimization

The millimeter-wave (mmWave) full-dimensional (FD) MIMO system employs planar arrays at both the base station and the user equipment and can simultaneously support both azimuth and elevation beamforming. In this paper, we propose atomic-norm-based methods for mm-wave FD-MIMO channel estimation under both uniform planar arrays (UPA) and non-uniform planar arrays (NUPA). Unlike existing algorithms, such as compressive sensing (CS) or subspace methods, the atomic-norm-based algorithms do not require to discretize the angle spaces of the angle of arrival and angle of departure into grids, thus provide much better accuracy in estimation. In the UPA case, to reduce the computational complexity, the original large-scale atomic norm minimization problem is approximately reformulated as a semi-definite program (SDP) containing two decoupled two-level Toeplitz matrices. The SDP is then solved via the alternating direction method of multipliers where each iteration involves only closed-form computations. In the NUPA case, the atomic-norm-based formulation for channel estimation becomes nonconvex and a gradient-decent-based algorithm is proposed to solve the problem. Simulation results show that the proposed algorithms achieve better performance than the CS-based and subspace-based algorithms.
On the Conformal Scalar Curvature Equation and Related Problems

A fundamental result in two-dimensional Riemannian geometry is the uniformization theorem, which asserts that any Riemannian metric on a compact surface is conformally related to a metric of constant curvature. There are two ways of generalizing this result to higher dimensions. One problem, proposed by E. Calabi, is concerned with the existence of KahlerEinstein metrics (or, more generally, extremal Kahler metrics). The other one was proposed in 1960 by H. Yamabe [38]. Yamabe claimed the following theorem:
Combining Plane Wave Expansion and Variational Techniques for Fast Phononic Computations

AbstractIn this paper, the salient features of the plane wave expansion (PWE) method and the mixed variational technique are combined for the fast eigenvalue computations of arbitrarily complex pho...
Sweeping Out 3-Manifold of Positive Ricci Curvature by Short 1-Cycles Via Estimates of Min–Max Surfaces

We prove that given a three manifold with an arbitrary metric $(M^3, g)$ of positive Ricci curvature, there exists a sweepout of $M$ by surfaces of genus $\leq 3$ and areas bounded by $C vol(M^3, g)^{2/3}$. We use this result to construct a sweepout of $M$ by 1-cycles of length at most $C vol(M^3, g)^{1/3}$. The sweepout of surfaces is generated from a min-max minimal surface. If further assuming a positive scalar curvature lower bound, we can get a diameter upper bound for the min-max surface.
UPAL: Unbiased Pool Based Active Learning

In this paper we address the problem of pool based active learning, and provide an algorithm, called UPAL, that works by minimizing the unbiased estimator of the risk of a hypothesis in a given hypothesis space. For the space of linear classifiers and the squared loss we show that UPAL is equivalent to an exponentially weighted average forecaster. Exploiting some recent results regarding the spectra of random matrices allows us to analyze UPAL with squared losses for the noiseless setting. Empirical comparison with an active learner implementation in Vowpal Wabbit, and a previously proposed pool based active learner implementation show good empirical performance and better scalability.
On the distribution of the number of points on a family of curves over finite fields

Abstract Let p be a large prime, l ⩾ 2 be a positive integer, m ⩾ 2 be an integer relatively prime to l and P ( x ) ∈ F p [ x ] be a polynomial which is not a complete l ′ -th power for any l ′ for which GCD ( l ′ , l ) = 1 . Let C be the curve defined by the equation y l = P ( x ) , and take the points on C to lie in the rectangle [ 0 , p − 1 ] 2 . In this paper, we study the distribution of the number of points on C inside small rectangles among residue classes modulo m when we move the rectangle around in [ 0 , p − 1 ] 2 .
A Harnack inequality for the parabolic Allen–Cahn equation

We prove a differential Harnack inequality for the solution of the parabolic Allen–Cahn equation $$ \frac{\partial f}{\partial t}=\triangle f-(f^3-f)$$ on a closed n-dimensional manifold. As a corollary, we find a classical Harnack inequality. We also formally compare the standing wave solution to a gradient estimate of Modica from the 1980s for the elliptic equation.
Quantum enhancements of involutory birack counting invariants

The involutory birack counting invariant is an integer-valued invariant of unoriented tangles defined by counting homomorphisms from the fundamental involutory birack of the tangle to a finite involutory birack over a set of framings modulo the birack rank of the labeling birack. In this first of an anticipated series of several papers, we enhance the involutory birack counting invariant with quantum weights, which may be understood as tangle functors of involutory birack-labeled unoriented tangles.
Bell inequalities from group actions: Three parties and non-Abelian groups

In a previous publication, we showed how group actions can be used to generate Bell inequalities. The group action yields a set of measurement probabilities whose sum is the basic element in the inequality. The sum has an upper bound if the probabilities are a result of a local, realistic theory, but this bound can be violated if the probabilities come from quantum mechanics. In our previous paper, we considered the case of only two parties making the measurements and single-generator groups. Here we show that the method can be extended to three parties, and it can also be extended to non-Abelian groups. We discuss the resulting inequalities in terms of nonlocal games.
Large-Scale Distributed Algorithms for Facility Location with Outliers

This paper presents fast, distributed, $O(1)$-approximation algorithms for metric facility location problems with outliers in the Congested Clique model, Massively Parallel Computation (MPC) model, and in the $k$-machine model. The paper considers Robust Facility Location and Facility Location with Penalties, two versions of the facility location problem with outliers proposed by Charikar et al. (SODA 2001). The paper also considers two alternatives for specifying the input: the input metric can be provided explicitly (as an $n \times n$ matrix distributed among the machines) or implicitly as the shortest path metric of a given edge-weighted graph. The results in the paper are: - Implicit metric: For both problems, $O(1)$-approximation algorithms running in $O(\mbox{poly}(\log n))$ rounds in the Congested Clique and the MPC model and $O(1)$-approximation algorithms running in $\tilde{O}(n/k)$ rounds in the $k$-machine model. - Explicit metric: For both problems, $O(1)$-approximation algorithms running in $O(\log\log\log n)$ rounds in the Congested Clique and the MPC model and $O(1)$-approximation algorithms running in $\tilde{O}(n/k)$ rounds in the $k$-machine model. Our main contribution is to show the existence of Mettu-Plaxton-style $O(1)$-approximation algorithms for both Facility Location with outlier problems. As shown in our previous work (Berns et al., ICALP 2012, Bandyapadhyay et al., ICDCN 2018) Mettu-Plaxton style algorithms are more easily amenable to being implemented efficiently in distributed and large-scale models of computation.
Hyperoctahedral Eulerian Idempotents, Hodge Decompositions, and Signed Graph Coloring Complexes

Phil Hanlon proved that the coefficients of the chromatic polynomial of a graph $G$ are equal (up to sign) to the dimensions of the summands in a Hodge-type decomposition of the top homology of the coloring complex for $G$. We prove a type B analogue of this result for chromatic polynomials of signed graphs using hyperoctahedral Eulerian idempotents.
DNS study on physics of late boundary layer transition

This paper serves as a review of our recent new DNS study on physics of late boundary layer transition. This includes mechanism of the large coherent vortex structure formation, small length scale generation and flow randomization. The widely spread concept “vortex breakdown to turbulence”, which was considered as the last stage of flow transition, is not observed and is found theoretically incorrect. The classical theory on boundary layer transition is challenged and we proposed a new theory with five steps, i.e. receptivity, linear instability, large vortex formation, small length scale generation, loss of symmetry and randomization to turbulence. We have also proposed a new theory about turbulence generation. The new theory shows that all small length scales (turbulence) are generated by shear layer instability which is produced by large vortex structure with multiple level vortex rings, multiple level sweeps and ejections, and multiple level negative and positive spikes near the laminar sub-layers. Therefore, “turbulence” is not generated by “vortex breakdown” but rather positive and negative spikes and consequent high shear layers. “Shear layer instability” is considered as the “mother of turbulence”. This new theory may give a universal mechanism for turbulence generation and sustenance – the energy is brought by large vortex structure through multiple level sweeps not by “vortex breakdown”. The ring-like vortex with or without legs is found the only form existing inside the flow field. The first ring-like vortex shape, which is perfectly circular and perpendicularly standing, is the result of the interaction between two pairs of counter-rotating primary and secondary streamwise vortices. Multiple rings are consequences of shear layer instability produced by momentum deficit which is formed by vortex ejections. The U-shaped vortices are not new but existing coherent large vortex structure. Actually, the Ushaped vortex, which is not a secondary but tertiary vortex, serves as an additional channel to support the multiple ring structure. The loss of symmetry and randomization are caused by internal property of the boundary layer. The loss of symmetry starts from the second level ring cycle in the middle of the flow field and spreads to the bottom of the boundary layer and then the whole field. More other new physics have also been discussed. Finally, classical theory such as “Richardson energy cascade” and “Kolmogorov small length scale” is revisited and challenged.
The Landscape of Domain Name Typosquatting: Techniques and Countermeasures

With more than 294 million registered domain names as of late 2015, the domain name ecosystem has evolved to become a cornerstone for the operation of the Internet. Domain names today serve everyone, from individuals for their online presence to big brands for their business operations. Such ecosystem that facilitated legitimate business and personal uses has also fostered "creative" cases of misuse, including phishing, spam, hit and traffic stealing, online scams, among others. As a first step towards this misuse, the registration of a legitimately-looking domain is often required. For that, domain typosquatting provides a great avenue to cybercriminals to conduct their crimes. In this paper, we review the landscape of domain name typosquatting, highlighting models and advanced techniques for typosquatted domain names generation, models for their monetization, and the existing literature on countermeasures. We further highlight potential fruitful directions on technical countermeasures that are lacking in the literature.
Hygienic Source-Code Generation Using Functors

Existing source-code-generating tools such as Lex and Yacc suffer from practical inconveniences because they use disembodied code to implement actions. To prevent this problem, such tools could generate closed functors that are then instantiated by the programmer with appropriate action code. This results in all code being type checked in its appropriate context, and it assists the type checker in localizing errors correctly. We have implemented a lexer generator and parser generator based on this technique for both Standard ML and Haskell.
An ADMM-Based Universal Framework for Adversarial Attacks on Deep Neural Networks

Deep neural networks (DNNs) are known vulnerable to adversarial attacks. That is, adversarial examples, obtained by adding delicately crafted distortions onto original legal inputs, can mislead a DNN to classify them as any target labels. In a successful adversarial attack, the targeted mis-classification should be achieved with the minimal distortion added. In the literature, the added distortions are usually measured by $L_0$, $L_1$, $L_2$, and $L_\infty $ norms, namely, L_0, L_1, L_2, and L_∞ attacks, respectively. However, there lacks a versatile framework for all types of adversarial attacks. This work for the first time unifies the methods of generating adversarial examples by leveraging ADMM (Alternating Direction Method of Multipliers), an operator splitting optimization approach, such that $L_0$, $L_1$, $L_2$, and $L_\infty $ attacks can be effectively implemented by this general framework with little modifications. Comparing with the state-of-the-art attacks in each category, our ADMM-based attacks are so far the strongest, achieving both the 100% attack success rate and the minimal distortion.
Testing the manifold hypothesis

The hypothesis that high dimensional data tend to lie in the vicinity of a low dimensional manifold is the basis of manifold learning. The goal of this paper is to develop an algorithm (with accompanying complexity guarantees) for fitting a manifold to an unknown probability distribution supported in a separable Hilbert space, only using i.i.d samples from that distribution. More precisely, our setting is the following. Suppose that data are drawn independently at random from a probability distribution $P$ supported on the unit ball of a separable Hilbert space $H$. Let $G(d, V, \tau)$ be the set of submanifolds of the unit ball of $H$ whose volume is at most $V$ and reach (which is the supremum of all $r$ such that any point at a distance less than $r$ has a unique nearest point on the manifold) is at least $\tau$. Let $L(M, P)$ denote mean-squared distance of a random point from the probability distribution $P$ to $M$. We obtain an algorithm that tests the manifold hypothesis in the following sense. The algorithm takes i.i.d random samples from $P$ as input, and determines which of the following two is true (at least one must be): (a) There exists $M \in G(d, CV, \frac{\tau}{C})$ such that $L(M, P) \leq C \epsilon.$ (b) There exists no $M \in G(d, V/C, C\tau)$ such that $L(M, P) \leq \frac{\epsilon}{C}.$ The answer is correct with probability at least $1-\delta$.
Random monomial ideals

Abstract Inspired by the study of random graphs and simplicial complexes, and motivated by the need to understand average behavior of ideals, we propose and study probabilistic models of random monomial ideals. We prove theorems about the probability distributions, expectations and thresholds for events involving monomial ideals with given Hilbert function, Krull dimension, and first graded Betti numbers, and show that our models generalize several well-known random simplicial complex models. Finally we present several experimentally-backed conjectures about regularity, projective dimension, strong genericity, and Cohen–Macaulayness of random monomial ideals.
Critical sets of random smooth functions on compact manifolds

Given a compact, connected Riemann manifold without boundary (M, g) of dimension m and a large positive constant L we denote byUL the subspace of C∞(M) spanned by eigenfunctions of the Laplacian corresponding to eigenvalues≤ L. We equipUL with the standard Gaussian probability measure induced by the L-metric onUL, and we denote by NL the expected number of critical points of a random function in UL. We prove that NL ∼ Cm dimUL as L → ∞, where Cm is an explicit positive constant that depends only on the dimension m of M and satisfying the asymptotic estimate logCm ∼ m2 logm as m→∞. CONTENTS
A KERNEL-BASED NONPARAMETRIC TEST FOR ANOMALY DETECTION OVER LINE NETWORKS

The nonparametric problem of detecting existence of an anomalous interval over a onedimensional line network is studied. Nodes corresponding to an anomalous interval (if exists) receive samples generated by a distribution q, which is different from the distribution p that generates samples for other nodes. If anomalous interval does not exist, then all nodes receive samples generated by p. It is assumed that the distributions p and q are arbitrary, and are unknown. In order to detect whether an anomalous interval exists, a test is built based on mean embeddings of distributions into a reproducing kernel Hilbert space (RKHS) and the metric of maximum mean discrepancy (MMD). It is shown that as the network size n goes to infinity, if the minimum length of candidate anomalous intervals is larger than a threshold which has the order O(logn), the proposed test is asymptotically successful, i.e., the probability of detection error approaches zero asymptotically. An efficient algorithm to perform the test with substantial computational complexity reduction is proposed, and is shown to be asymptotically successful if the condition on the minimum length of candidate anomalous interval is satisfied. Numerical results are provided, which are consistent with the theoretical results.
Game of power allocation on networks

This paper develops a distributed resource allocation game to study countries' pursuit of targets such as self-survival in the networked international environment. The contributions are two. First, the game formalizes countries' power allocation behaviors which fall into the broad category of humans resource allocation behaviors. Second, the game presents a new technical problem, and establishes pure strategy Nash equilibrium existence.
Open-ended learning in symmetric zero-sum games

Zero-sum games such as chess and poker are, abstractly, functions that evaluate pairs of agents, for example labeling them ‘winner’ and ‘loser’. If the game is approximately transitive, then self-play generates sequences of agents of increasing strength. However, nontransitive games, such as rock-paper-scissors, can exhibit strategic cycles, and there is no longer a clear objective – we want agents to increase in strength, but against whom is unclear. In this paper, we introduce a geometric framework for formulating agent objectives in zero-sum games, in order to construct adaptive sequences of objectives that yield open-ended learning. The framework allows us to reason about population performance in nontransitive games, and enables the development of a new algorithm (rectified Nash response, PSRO_rN) that uses game-theoretic niching to construct diverse populations of effective agents, producing a stronger set of agents than existing algorithms. We apply PSRO_rN to two highly nontransitive resource allocation games and find that PSRO_rN consistently outperforms the existing alternatives.
Interlayer Coupling in Magnetic/Pd Multilayers

The Anderson model of local-state conduction electron mixing is applied to the problem of interlayer magnetic coupling in metallic multilayered structures with palladium (Pd) spacer layers. An oscillation period of 5 spacer monolayers and the tendency towards ferromagnetic bias of the interlayer magnetic coupling that we obtain are consistent with the experimental data.
Simple error bounds for regularized noisy linear inverse problems

Consider estimating a structured signal x_0 from linear, underdetermined and noisy measurements y = Ax_0+z, via solving a variant of the lasso algorithm: x = arg min_x{∥y-Ax∥+2 + λf(x)}. Here, f is a convex function aiming to promote the structure of x_0, say l_1-norm to promote sparsity or nuclear norm to promote low-rankness. We assume that the entries of A are independent and normally distributed and make no assumptions on the noise vector z, other than it being independent of A. Under this generic setup, we derive a general, non-asymptotic and rather tight upper bound on the l_2-norm of the estimation error ∥x - x0∥2. Our bound is geometric in nature and obeys a simple formula; the roles of λ, f and x_0 are all captured by a single summary parameter δ(λ∂f(x_0)), termed the Gaussian squared distance to the scaled subdifferential. We connect our result to the literature and verify its validity through simulations.
A flag variety for the Delta Conjecture

The Delta Conjecture of Haglund, Remmel, and Wilson predicts the monomial expansion of the symmetric function $\Delta'_{e_{k-1}} e_n$, where $k \leq n$ are positive integers and $\Delta'_{e_{k-1}}$ is a Macdonald eigenoperator. When $k = n$, the specialization $\Delta'_{e_{n-1}} e_n|_{t = 0}$ is the Frobenius image of the graded $S_n$-module afforded by the cohomology ring of the {\em flag variety} consisting of complete flags in $\mathbb{C}^n$. We define and study a variety $X_{n,k}$ which carries an action of $S_n$ whose cohomology ring $H^{\bullet}(X_{n,k})$ has Frobenius image given by $\Delta'_{e_{k-1}} e_n|_{t = 0}$, up to a minor twist. The variety $X_{n,k}$ has a cellular decomposition with cells $C_w$ indexed by length $n$ words $w = w_1 \dots w_n$ in the alphabet $\{1, 2, \dots, k\}$ in which each letter appears at least once. When $k = n$, the variety $X_{n,k}$ is homotopy equivalent to the flag variety. We give a presentation for the cohomology ring $H^{\bullet}(X_{n,k})$ as a quotient of the polynomial ring $\mathbb{Z}[x_1, \dots, x_n]$ and describe polynomial representatives for the classes $[ \overline{C}_w]$ of the closures of the cells $C_w$; these representatives generalize the classical Schubert polynomials.
A counterexample to a conjecture of Ding

Abstract We give a counterexample to a conjecture posed by S. Ding in [4] regarding the index of a Gorenstein local ring by exhibiting several examples of one dimensional local complete intersections of embedding dimension three with index 5 and generalized Loewy length 6.
Stochastic homogenization of certain nonconvex Hamilton–Jacobi equations

Abstract In this paper, we prove the stochastic homogenization of certain nonconvex Hamilton–Jacobi equations. The nonconvex Hamiltonians, which are generally uneven and inseparable, are generated by a sequence of quasiconvex Hamiltonians and a sequence of quasiconcave Hamiltonians through the min-max formula. We provide a monotonicity assumption on the contact values between those stably paired Hamiltonians so as to guarantee the stochastic homogenization.
Interior Penalty Discontinuous Galerkin Methods for Second Order Linear Non-Divergence Form Elliptic PDEs

This paper develops interior penalty discontinuous Galerkin (IP-DG) methods to approximate $$W^{2,p}$$ strong solutions of second order linear elliptic partial differential equations (PDEs) in non-divergence form with continuous coefficients. The proposed IP-DG methods are closely related to the IP-DG methods for advection-diffusion equations, and they are easy to implement on existing standard IP-DG software platforms. It is proved that the proposed IP-DG methods have unique solutions and converge with optimal rate to the $$W^{2,p}$$ strong solution in a discrete $$W^{2,p}$$ -norm. The crux of the analysis is to establish a DG discrete counterpart of the Calderon–Zygmund estimate and to adapt a freezing coefficient technique used for the PDE analysis at the discrete level. To obtain such a crucial estimate, we need to establish broken $$W^{1,p}$$ -norm error estimates for IP-DG approximations of constant coefficient elliptic PDEs, which is also of independent interest. Numerical experiments are provided to gauge the performance of the proposed IP-DG methods and to validate the theoretical convergence results.
Reduced rank vector generalized linear models for feature extraction

Supervised linear feature extraction can be achieved by fitting a reduced rank multivariate model. This paper studies rank penalized and rank constrained vector generalized linear models. From the perspective of thresholding rules, we build a framework for fitting singular value penalized models and use it for feature extraction. Through solving the rank constraint form of the problem, we propose progressive feature space reduction for fast computation in high dimensions with little performance loss. A novel projective cross-validation is proposed for parameter tuning in such nonconvex setups. Real data applications are given to show the power of the methodology in supervised dimension reduction and feature extraction.
Phase uniqueness for the Mallows measure on permutations

For a positive number q, the Mallows measure on the symmetric group is the probability measure on Sn such that Pn,q(π) is proportional to q-to-the-power-inv(π) where inv(π) equals the number of inversions: inv(π) equals the number of pairs i πj. One may consider this as a mean-field model from statistical mechanics. The weak large deviation principle may replace the Gibbs variational principle for characterizing equilibrium measures. In this sense, we prove the absence of phase transition, i.e., phase uniqueness.
Multimodal Content Analysis for Effective Advertisements on YouTube

The recent advancement of web-scale digital advertising saw a paradigm shift from the conventional focus of digital advertisement distribution towards integrating digital processes and methodologies and forming a seamless workflow of advertisement design, production, distribution, and effectiveness monitoring. In this work, we implemented a computational framework for the predictive analysis of the content-based features extracted from advertisement video files and various effectiveness metrics to aid the design and production processes of commercial advertisements. Our proposed predictive analysis framework extracts multi-dimensional temporal patterns from the content of advertisement videos using multimedia signal processing and natural language processing tools. The pattern analysis part employs an architecture of cross modality feature learning where data streams from different feature dimensions are employed to train separate neural network models and then these models are fused together to learn a shared representation. Subsequently, a neural network model trained on this joint representation is utilized as a classifier for predicting advertisement effectiveness. Based on the predictive patterns identified between the content features and the effectiveness metrics of advertisements, we have elicited a useful set of auditory, visual and textual patterns that is strongly correlated with the proposed effectiveness metrics while can be readily implemented in the design and production processes of commercial advertisements. We validate our approach using subjective ratings from a dedicated user study, the text sentiment strength of online viewer comments, and a viewer opinion metric of the likes/views ratio of each advertisement from YouTube video-sharing website.
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication

We study the problem of estimating $k$-ary distributions under $\eps$-local differential privacy. $n$ samples are distributed across users who send privatized versions of their sample to a central server. All previously known sample optimal algorithms require linear (in $k$) communication from each user in the high privacy regime $(\eps=O(1))$, and run in time that grows as $n\cdot k$, which can be prohibitive for large domain size $k$. We propose Hadamard Response (HR), a local privatization scheme that requires no shared randomness and is symmetric with respect to the users. Our scheme has order optimal sample complexity for all $\eps$, a communication of at most $\log k+2$ bits per user, and nearly linear running time of $\tilde{O}(n + k)$. Our encoding and decoding are based on Hadamard matrices and are simple to implement. The statistical performance relies on the coding theoretic aspects of Hadamard matrices, ie, the large Hamming distance between the rows. An efficient implementation of the algorithm using the Fast Walsh-Hadamard transform gives the computational gains. We compare our approach with Randomized Response (RR), RAPPOR, and subset-selection mechanisms (SS), both theoretically, and experimentally. For $k=10000$, our algorithm runs about 100x faster than SS, and RAPPOR.