cssi/SciSciGPT-SciSciNet huggingface dataset:
Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution

We study adversarial perturbations when the instances are uniformly distributed over {0,1}^n. We study both "inherent" bounds that apply to any problem and any classifier for such a problem as well as bounds that apply to specific problems and specific hypothesis classes. As the current literature contains multiple definitions of adversarial risk and robustness, we start by giving a taxonomy for these definitions based on their direct goals; we identify one of them as the one guaranteeing misclassification by pushing the instances to the error region. We then study some classic algorithms for learning monotone conjunctions and compare their adversarial risk and robustness under different definitions by attacking the hypotheses using instances drawn from the uniform distribution. We observe that sometimes these definitions lead to significantly different bounds. Thus, this study advocates for the use of the error-region definition, even though other definitions, in other contexts with context-dependent assumptions, may coincide with the error-region definition. Using the error-region definition of adversarial perturbations, we then study inherent bounds on risk and robustness of any classifier for any classification problem whose instances are uniformly distributed over {0,1}^n. Using the isoperimetric inequality for the Boolean hypercube, we show that for initial error 0.01, there always exists an adversarial perturbation that changes O(√n) bits of the instances to increase the risk to 0.5, making classifier's decisions meaningless. Furthermore, by also using the central limit theorem we show that when n→∞, at most c√n bits of perturbations, for a universal constant c<1.17, suffice for increasing the risk to 0.5, and the same c√n bits of perturbations on average suffice to increase the risk to 1, hence bounding the robustness by c√n.
On the extremizers of an adjoint Fourier restriction inequality

Abstract The adjoint Fourier restriction inequality for the sphere S 2 states that if f ∈ L 2 ( S 2 , σ ) then f σ ∈ L 4 ( R 3 ) . We prove that all critical points f of the functional ‖ f σ ‖ L 4 / ‖ f ‖ L 2 are smooth, any complex-valued extremizer for the inequality is a nonnegative extremizer multiplied by the character e i x ⋅ ξ for some ξ , and complex-valued extremizing sequences for the inequality are precompact modulo multiplication by characters.
Effective equidistribution of shears and applications

A “shear” is a unipotent translate of a cuspidal geodesic ray in the quotient of the hyperbolic plane by a non-uniform discrete subgroup of $${\text {PSL}}(2,\mathbb {R})$$ , possibly of infinite co-volume. We prove the regularized equidistribution of shears under large translates with effective (that is, power saving) rates. We also give applications to weighted second moments of GL(2) automorphic L-functions, and to counting lattice points on locally affine symmetric spaces.
Knot homology and sheaves on the Hilbert scheme of points on the plane

For each braid $$\beta \in \mathfrak {Br}_n$$ we construct a 2-periodic complex $$\mathbb {S}_\beta $$ of quasi-coherent $$\mathbb {C}^*\times \mathbb {C}^*$$ -equivariant sheaves on the non-commutative nested Hilbert scheme $${\mathrm {Hilb}}_{1,n}^{\textit{free}}$$ . We show that the triply graded vector space of the hypercohomology $$ \mathbb {H}( \mathbb {S}_{\beta }\otimes \wedge ^\bullet (\mathcal {B}))$$ with $$\mathcal {B}$$ being tautological vector bundle, is an isotopy invariant of the knot obtained by the closure of $$\beta $$ . We also show that the support of cohomology of the complex $$\mathbb {S}_\beta $$ is supported on the ordinary nested Hilbert scheme $${\mathrm {Hilb}}_{1,n}\subset {\mathrm {Hilb}}_{1,n}^{\textit{free}}$$ , that allows us to relate the triply graded knot homology to the sheaves on $${\mathrm {Hilb}}_{1,n}$$ .
A monotone isomorphism theorem

In the simple case of a Bernoulli shift on two symbols, zero and one, by permuting the symbols, it is obvious that any two equal entropy shifts are isomorphic. We show that the isomorphism can be realized by a factor that maps a binary sequence to another that is coordinatewise smaller than or equal to the original sequence.
Optimizing Gershgorin for Symmetric Matrices

Abstract The Gershgorin Circle Theorem is a well-known and efficient method for bounding the eigenvalues of a matrix in terms of its entries. If A is a symmetric matrix, by writing A = B + x 1 , where 1 is the matrix with unit entries, we consider the problem of choosing x to give the optimal Gershgorin bound on the eigenvalues of B, which then leads to one-sided bounds on the eigenvalues of A. We show that this x can be found by an efficient linear program (whose solution can in may cases be written in closed form), and we show that for large classes of matrices, this shifting method beats all existing piecewise linear or quadratic bounds on the eigenvalues. We also apply this shifting paradigm to some nonlinear estimators and show that under certain symmetries this also gives rise to a tractable linear program. As an application, we give a novel bound on the lowest eigenvalue of a adjacency matrix in terms of the “top two” or “bottom two” degrees of the corresponding graph, and study the efficacy of this method in obtaining sharp eigenvalue estimates for certain classes of matrices.
Non-convex rank minimization via an empirical Bayesian approach

In many applications that require matrix solutions of minimal rank, the underlying cost function is non-convex leading to an intractable, NP-hard optimization problem. Consequently, the convex nuclear norm is frequently used as a surrogate penalty term for matrix rank. The problem is that in many practical scenarios there is no longer any guarantee that we can correctly estimate generative low-rank matrices of interest, theoretical special cases notwithstanding. Consequently, this paper proposes an alternative empirical Bayesian procedure build upon a variational approximation that, unlike the nuclear norm, retains the same globally minimizing point estimate as the rank function under many useful constraints. However, locally minimizing solutions are largely smoothed away via marginalization, allowing the algorithm to succeed when standard convex relaxations completely fail. While the proposed methodology is generally applicable to a wide range of low-rank applications, we focus our attention on the robust principal component analysis problem (RPCA), which involves estimating an unknown low-rank matrix with unknown sparse corruptions. Theoretical and empirical evidence are presented to show that our method is potentially superior to related MAP-based approaches, for which the convex principle component pursuit (PCP) algorithm (Candes et al., 2011) can be viewed as a special case.
Counting dominating sets and related structures in graphs

We first consider some problems related to the maximum number of dominating (or total dominating) sets in a regular graph. Our techniques, centered around Shearer's entropy lemma, extend to a reasonably broad class of graph parameters enumerating vertex colorings that satisfy conditions on the multiset of colors appearing in neighborhoods (either open or closed). Dominating sets and total dominating sets are examples, as are graph colorings in which each vertex's neighborhood is not monochromatic (or rainbow). In the final section, we think about a generalization of dominating sets in a slightly different direction. Just as independent sets are homomorphisms into K 2 with one vertex looped, we think of dominating sets as an example of what we call an existence homomorphism. Here our results are substantially less complete, though we do solve some natural problems.
Robust Influence Maximization

Uncertainty about models and data is ubiquitous in the computational social sciences, and it creates a need for robust social network algorithms, which can simultaneously provide guarantees across a spectrum of models and parameter settings. We begin an investigation into this broad domain by studying robust algorithms for the Influence Maximization problem, in which the goal is to identify a set of k nodes in a social network whose joint influence on the network is maximized. We define a Robust Influence Maximization framework wherein an algorithm is presented with a set of influence functions, typically derived from different influence models or different parameter settings for the same model. The different parameter settings could be derived from observed cascades on different topics, under different conditions, or at different times. The algorithm's goal is to identify a set of k nodes who are simultaneously influential for all influence functions, compared to the (function-specific) optimum solutions. We show strong approximation hardness results for this problem unless the algorithm gets to select at least a logarithmic factor more seeds than the optimum solution. However, when enough extra seeds may be selected, we show that techniques of Krause et al. can be used to approximate the optimum robust influence to within a factor of 1-1/e. We evaluate this bicriteria approximation algorithm against natural heuristics on several real-world data sets. Our experiments indicate that the worst-case hardness does not necessarily translate into bad performance on real-world data sets; all algorithms perform fairly well.
WELL-POSEDNESS FOR THE MASSIVE WAVE EQUATION ON ASYMPTOTICALLY ANTI-DE SITTER SPACETIMES

In this paper, we prove a well-posedness theorem for the massive wave equation (with the mass satisfying the Breitenlohner–Freedman bound) on asymptotically anti-de Sitter spaces. The solution is constructed as a limit of solutions to an initial boundary value problem with boundary at a finite location in spacetime by finally pushing the boundary out to infinity. The solution obtained is unique within the energy class (but non-unique if the decay at infinity is weakened).
OPTIMAL LIQUIDATION UNDER STOCHASTIC PRICE IMPACT

We assume a continuous-time price impact model similar to that of Almgren–Chriss but with the added assumption that the price impact parameters are stochastic processes modeled as correlated scalar...
Projections over quantum homogeneous odd-dimensional spheres

Abstract We give a complete classification of isomorphism classes of finitely generated projective modules, or equivalently, unitary equivalence classes of projections, over the C*-algebra C ( S q 2 n + 1 ) of the quantum homogeneous sphere S q 2 n + 1 . Then we explicitly identify as concrete elementary projections the quantum line bundles L k over the quantum complex projective space C P q n associated with the quantum Hopf principal U ( 1 ) -bundle S q 2 n + 1 → C P q n .
Glass-Box Program Synthesis: A Machine Learning Approach.

Recently proposed models which learn to write computer programs from data use either input/output examples or rich execution traces. Instead, we argue that a novel alternative is to use a glass-box scoring function, given as a program itself that can be directly inspected. Glass-box optimization covers a wide range of problems, from computing the greatest common divisor of two integers, to learning-to-learn problems. In this paper, we present an intelligent search system which learns, given the partial program and the glass-box problem, the probabilities over the space of programs. We empirically demonstrate that our informed search procedure leads to significant improvements compared to brute-force program search, both in terms of accuracy and time. For our experiments we use rich context free grammars inspired by number theory, text processing, and algebra. Our results show that (i) running our framework iteratively can considerably increase the number of problems solved, (ii) our framework can improve itself even in domain agnostic scenarios, and (iii) it can solve problems that would be otherwise too slow to solve with brute-force search.
Greedy Galois Games

We show that two duelers with similar, lousy shooting skills (a.k.a. Galois duelers) will choose to take turns firing in accordance with the famous Thue-Morse sequence if they greedily demand their chances to fire as soon as the other's a priori probability of winning exceeds their own. This contrasts with a result from the approximation theory of complex functions, which says what more patient duelers would do, if they really cared about being as fair as possible. We note a consequent interpretation of the Thue-Morse sequence in terms of certain expansions in fractional bases close to, but greater than, 1.
Asymptotic convergence of constrained primal-dual dynamics

This paper studies the asymptotic convergence properties of the primal–dual dynamics designed for solving constrained concave optimization problems using classical notions from stability analysis. We motivate the need for this study by providing an example that rules out the possibility of employing the invariance principle for hybrid automata to study asymptotic convergence. We understand the solutions of the primal–dual dynamics in the Caratheodory sense and characterize their existence, uniqueness, and continuity with respect to the initial condition. We use the invariance principle for discontinuous Caratheodory systems to establish that the primal–dual optimizers are globally asymptotically stable under the primal–dual dynamics and that each solution of the dynamics converges to an optimizer.
Fast stochastic hierarchical Bayesian map for tomographic imaging

Any image recovery algorithm attempts to achieve the highest quality reconstruction in a timely manner. The former can be achieved in several ways, among which are by incorporating Bayesian priors that exploit natural image tendencies to cue in on relevant phenomena. The Hierarchical Bayesian MAP (HB-MAP) is one such approach [1] which is known to produce compelling results albeit at a substantial computational cost. We look to provide further analysis and insights into what makes the HB-MAP work. While retaining the proficient nature of HB-MAP's Type-I estimation, we propose a stochastic approximation-based approach to Type-II estimation. The resulting algorithm, fast stochastic HB-MAP (fsHBMAP), takes dramatically fewer operations while retaining high reconstruction quality. We employ our fsHBMAP scheme towards the problem of tomographic imaging and demonstrate that fsHBMAP furnishes promising results when compared to many competing methods.
Convergence analysis and error estimates for a second order accurate finite element method for the Cahn–Hilliard–Navier–Stokes system

In this paper, we present a novel second order in time mixed finite element scheme for the Cahn–Hilliard–Navier–Stokes equations with matched densities. The scheme combines a standard second order Crank–Nicolson method for the Navier–Stokes equations and a modification to the Crank–Nicolson method for the Cahn–Hilliard equation. In particular, a second order Adams-Bashforth extrapolation and a trapezoidal rule are included to help preserve the energy stability natural to the Cahn–Hilliard equation. We show that our scheme is unconditionally energy stable with respect to a modification of the continuous free energy of the PDE system. Specifically, the discrete phase variable is shown to be bounded in $$\ell ^\infty \left( 0,T;L^\infty \right) $$ and the discrete chemical potential bounded in $$\ell ^\infty \left( 0,T;L^2\right) $$ , for any time and space step sizes, in two and three dimensions, and for any finite final time T. We subsequently prove that these variables along with the fluid velocity converge with optimal rates in the appropriate energy norms in both two and three dimensions.
On optimal policy in the group testing with incomplete identification

Abstract Consider a very large (infinite) population of items, where each item independent from the others is defective with probability p , or good with probability q = 1 − p . The goal is to identify N good items as quickly as possible. The following group testing policy (policy A) is considered: test items together in the groups, if the test outcome of group i of size n i is negative, then accept all items in this group as good, otherwise discard the group. Then, move to the next group and continue until exact N good items are found. The goal is to find an optimal testing configuration, i.e., group sizes, under policy A, such that the expected waiting time to obtain N good items is minimal. Recently, Gusev (2012) found an optimal group testing configuration under the assumptions of constant group size and N = ∞ . In this note, an optimal solution under policy A for finite N is provided.
Efficient test selection in active diagnosis via entropy approximation

We consider the problem of diagnosing faults in a system represented by a Bayesian network, where diagnosis corresponds to recovering the most likely state of unobserved nodes given the outcomes of tests (observed nodes). Finding an optimal subset of tests in this setting is intractable in general. We show that it is difficult even to compute the next most-informative test using greedy test selection, as it involves several entropy terms whose exact computation is intractable. We propose an approximate approach that utilizes the loopy belief propagation infrastructure to simultaneously compute approximations of marginal and conditional entropies on multiple subsets of nodes. We apply our method to fault diagnosis in computer networks, and show the algorithm to be very effective on realistic Internet-like topologies. We also provide theoretical justification for the greedy test selection approach, along with some performance guarantees.
Multi-frequency vector diffusion maps

We introduce multi-frequency vector diffusion maps (MFVDM), a new framework for organizing and analyzing high dimensional datasets. The new method is a mathematical and algorithmic generalization of vector diffusion maps (VDM) and other non-linear dimensionality reduction methods. MFVDM combines different nonlinear embeddings of the data points defined with multiple unitary irreducible representations of the alignment group that connect two nodes in the graph. We illustrate the efficacy of MFVDM on synthetic data generated according to a random graph model and cryo-electron microscopy image dataset. The new method achieves better nearest neighbor search and alignment estimation than the state-of-the-arts VDM and diffusion maps (DM) on extremely noisy data.
Upper and Lower Semimodularity of the Supercharacter Theory Lattices of Cyclic Groups

We consider the lattice of supercharacter theories, in the sense of Diaconis and Isaacs [5], of the cyclic group of order n. We find necessary and sufficient conditions on n for that lattice to be upper or lower semimodular.
A note on the eightfold way

Assuming the existence of a Mahlo cardinal, we construct a model in which there exists an $\omega_2$-Aronszajn tree, the $\omega_1$-approachability property fails, and every stationary subset of $\omega_2 \cap \mathrm{cof}(\omega)$ reflects.
Restricted Isometry Property for General p-Norms

The restricted isometry property (RIP) is a fundamental property of a matrix, which enables sparse recovery. Informally, an $m \times n$ matrix satisfies RIP of order $k$ for the $\ell _{p}$ norm, if $\|Ax\|_{p} \approx \|x\|_{p}$ for every vector $x$ with at most $k$ non-zero coordinates. For every $1 \leq p , we obtain almost tight bounds on the minimum number of rows $m$ necessary for the RIP property to hold. Prior to this paper, only the cases $p = 1$ , $1 + 1 / \log n$ , and 2 were studied. Interestingly, our results show that the case $p = 2$ is a singularity point: the optimal number of rows $m$ is $\widetilde {\Theta }(k^{p})$ for all $p\in [1,\infty )\setminus \{2\}$ , as opposed to $\widetilde {\Theta }(k)$ for $p=2$ . We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss the implications of our results for the stable sparse recovery problem as defined by Candes et al.
Policy Evaluation and Optimization with Continuous Treatments

We study the problem of policy evaluation and learning from batched contextual bandit data when treatments are continuous, going beyond previous work on discrete treatments. Previous work for discrete treatment/action spaces focuses on inverse probability weighting (IPW) and doubly robust (DR) methods that use a rejection sampling approach for evaluation and the equivalent weighted classification problem for learning. In the continuous setting, this reduction fails as we would almost surely reject all observations. To tackle the case of continuous treatments, we extend the IPW and DR approaches to the continuous setting using a kernel function that leverages treatment proximity to attenuate discrete rejection. Our policy estimator is consistent and we characterize the optimal bandwidth. The resulting continuous policy optimizer (CPO) approach using our estimator achieves convergent regret and approaches the best-in-class policy for learnable policy classes. We demonstrate that the estimator performs well and, in particular, outperforms a discretization-based benchmark. We further study the performance of our policy optimizer in a case study on personalized dosing based on a dataset of Warfarin patients, their covariates, and final therapeutic doses. Our learned policy outperforms benchmarks and nears the oracle-best linear policy.
Endomorphism rings of reductions of elliptic curves and abelian varieties

Let $E$ be an elliptic curve without CM that is defined over a number field $K$. For all but finitely many nonarchimedean places $v$ of $K$ there is the reduction $E(v)$ of $E$ at $v$ that is an elliptic curve over the residue field $k(v)$ at $v$. The set of $v$'s with ordinary $E(v)$ has density 1 (Serre). For such $v$ the endomorphism ring $End(E(v))$ of $E(v)$ is an order in an imaginary quadratic field. We prove that for any pair of relatively prime positive integers $N$ and $M$ there are infinitely many nonarchimedean places $v$ of $K$ such that the discriminant $\Delta(v)$ of $End(E(v))$ is divisible by $N$ and the ratio $\Delta(v)/N$ is relatively prime to $NM$. We also discuss similar questions for reductions of abelian varieties. The subject of this paper was inspired by an exercise in Serre's "Abelian $\ell$-adic representations and elliptic curves" and questions of Mihran Papikian and Alina Cojocaru.
Predicting Organic Reaction Outcomes with Weisfeiler-Lehman Network

The prediction of organic reaction outcomes is a fundamental problem in computational chemistry. Since a reaction may involve hundreds of atoms, fully exploring the space of possible transformations is intractable. The current solution utilizes reaction templates to limit the space, but it suffers from coverage and efficiency issues. In this paper, we propose a template-free approach to efficiently explore the space of product molecules by first pinpointing the reaction center -- the set of nodes and edges where graph edits occur. Since only a small number of atoms contribute to reaction center, we can directly enumerate candidate products. The generated candidates are scored by a Weisfeiler-Lehman Difference Network that models high-order interactions between changes occurring at nodes across the molecule. Our framework outperforms the top-performing template-based approach with a 10% margin, while running orders of magnitude faster. Finally, we demonstrate that the model accuracy rivals the performance of domain experts.
Online learning via sequential complexities

We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning with i.i.d. data. Our proposed sequential complexities can be seen as extensions of these measures to the sequential setting. The developed theory is shown to yield precise learning guarantees for the problem of sequential prediction. In particular, we show necessary and sufficient conditions for online learnability in the setting of supervised learning. Several examples show the utility of our framework: we can establish learnability without having to exhibit an explicit online learning algorithm.
Parameter Estimation in Softmax Decision-Making Models With Linear Objective Functions

We contribute to the development of a systematic means to infer features of human decision-making from behavioral data. Motivated by the common use of softmax selection in models of human decision-making, we study the maximum-likelihood (ML) parameter estimation problem for softmax decision-making models with linear objective functions. We present conditions under which the likelihood function is convex. These allow us to provide sufficient conditions for convergence of the resulting ML estimator and to construct its asymptotic distribution. In the case of models with nonlinear objective functions, we show how the estimator can be applied by linearizing about a nominal parameter value. We apply the estimator to fit the stochastic Upper Credible Limit (UCL) model of human decision-making to human subject data. The fits show statistically significant differences in behavior across related, but distinct, tasks.
Autonomous racing using learning Model Predictive Control

A novel learning Model Predictive Control technique is applied to the autonomous racing problem. The goal of the controller is to minimize the time to complete a lap. The proposed control strategy uses the data from previous laps to improve its performance while satisfying safety requirements. A system identification technique is proposed to estimate the vehicle dynamics. Simulation results with the high fidelity simulator software CarSim show the effectiveness of the proposed control scheme.
Multicast with Prioritized Delivery: How Fresh is Your Data?

We consider a multicast network in which real-time status updates generated by a source are replicated and sent to multiple interested receiving nodes through independent links. The receiving nodes are divided into two groups: one priority group consists of k nodes that require the reception of every update packet, the other non-priority group consists of all other nodes without the delivery requirement. Using age of information as a freshness metric, we analyze the time-averaged age at both priority and non-priority nodes. For shifted-exponential link delay distributions, the average age at a priority node is lower than that at a non-priority node due to the delivery guarantee. However, this advantage for priority nodes disappears if the link delay is exponential distributed. Both groups of nodes have the same time-averaged age, which implies that the guaranteed delivery of updates has no effect the time-averaged freshness.
Faster CNNs with Direct Sparse Convolutions and Guided Pruning

Phenomenally successful in practical inference problems, convolutional neural networks (CNN) are widely deployed in mobile devices, data centers, and even supercomputers. The number of parameters needed in CNNs, however, are often large and undesirable. Consequently, various methods have been developed to prune a CNN once it is trained. Nevertheless, the resulting CNNs offer limited benefits. While pruning the fully connected layers reduces a CNN's size considerably, it does not improve inference speed noticeably as the compute heavy parts lie in convolutions. Pruning CNNs in a way that increase inference speed often imposes specific sparsity structures, thus limiting the achievable sparsity levels. We present a method to realize simultaneously size economy and speed improvement while pruning CNNs. Paramount to our success is an efficient general sparse-with-dense matrix multiplication implementation that is applicable to convolution of feature maps with kernels of arbitrary sparsity patterns. Complementing this, we developed a performance model that predicts sweet spots of sparsity levels for different layers and on different computer architectures. Together, these two allow us to demonstrate 3.1--7.3$\times$ convolution speedups over dense convolution in AlexNet, on Intel Atom, Xeon, and Xeon Phi processors, spanning the spectrum from mobile devices to supercomputers. We also open source our project at this https URL.
Verhulst's Logistic Curve

Students tend to regard the elongated “S-shaped” logistic curve of population dynamics (Figure 1) as somewhat exotic. It is typically derived by applying the method of partial fractions to a separable differential equation. My purpose here is to show how the logistic curve may be derived more directly as a simple consequence of the more familiar differential equation model for exponential decay, and that the curve itself is nothing more than a familiar friend in disguise. The disguise is removed by abandoning our fixation on the reference point (0, P0), representing the initial population at time zero, in favor of a more natural choice. This illustrates an important principle, namely that one should always adapt the coordinates to the problem at hand. In this case, a great deal is simplified by relocating the origin more appropriately. Textbooks typically begin the discussion of population growth with the exponential model
Interior nodal sets of Steklov eigenfunctions on surfaces

We investigate the interior nodal sets $\mathcal{N}_\lambda$ of Steklov eigenfunctions on connected and compact surfaces with boundary. The optimal vanishing order of Steklov eigenfunctions is shown be $C\lambda$. The singular sets $\mathcal{S}_\lambda$ are finite points on the nodal sets. We are able to prove that the Hausdorff measure $H^0(\mathcal{S}_\lambda)\leq C\lambda^2$. Furthermore, we obtain an upper bound for the measure of interior nodal sets $H^1(\mathcal{N}_\lambda)\leq C\lambda^{\frac{3}{2}}$. Here those positive constants $C$ depend only on the surfaces.
Bousfield lattices of non-Noetherian rings: some quotients and products

In the context of a well generated tensor triangulated category, Section 3 investigates the relationship between the Bousfield lattice of a quotient and quotients of the Bousfield lattice. In Section 4 we develop a general framework to study the Bousfield lattice of the derived category of a commutative or graded-commutative ring, using derived functors induced by extension of scalars. Section 5 applies this work to extend results of Dwyer and Palmieri [DP08] to new non-Noetherian rings.
Convolution Kernels of 2D Fourier Multipliers Based on Real Analytic Functions

In this paper, estimates are proven for convolution kernels associated to multipliers from a reasonably general class of compactly supported two-dimensional functions constructed out of real analytic functions. These estimates are both for overall decay rate and decay rate in specific directions. The estimates are sharp for a certain range of exponents appearing in the theorems.
Latency analysis of coded computation schemes over wireless networks

Large-scale distributed computing systems face two major bottlenecks that limit their scalability: straggler delay caused by the variability of computation times at different worker nodes and communication bottlenecks caused by shuffling data across many nodes in the network. Recently, it has been shown that codes can provide significant gains in overcoming these bottlenecks. In particular, optimal coding schemes for minimizing latency in distributed computation of linear functions and mitigating the effect of stragglers was proposed in [1] for a wired network, where the workers can simultaneously transmit messages to a master node without interference. In this paper, we focus on the problem of coded computation over a wireless master-worker setup with straggling workers, where only one worker can transmit the result of its local computation back to the master at a time. We consider three asymptotic regimes (determined by how the communication and computation times are scaled with the number of workers) and precisely characterize the expected total run-time of the distributed algorithm and optimum coding strategy in each regime. In particular, for the regime of practical interest where the computation and communication times of the distributed computing algorithm are comparable, we show that the total run-time approaches a simple lower bound that decouples computation and communication, and demonstrate that coded schemes are Θ(logn) times faster than uncoded schemes.
Certifying solutions to overdetermined and singular polynomial systems over Q

Abstract This paper is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a continuous property. Our certification is based on hybrid symbolic-numeric methods to compute an exact rational univariate representation (RUR) of a component of the input system from approximate roots. For overdetermined polynomial systems with simple roots, we compute an initial RUR from approximate roots. The accuracy of the RUR is increased via Newton iterations until the exact RUR is found, which we certify using exact arithmetic. Since the RUR is well-constrained, we can use it to certify the given approximate roots using α -theory. To certify isolated singular roots, we use a determinantal form of the isosingular deflation , which adds new polynomials to the original system without introducing new variables. The resulting polynomial system is overdetermined, but the roots are now simple, thereby reducing the problem to the overdetermined case. We prove that our algorithms have complexity that are polynomial in the input plus the output size upon successful convergence, and we use worst case upper bounds for termination when our iteration does not converge to an exact RUR. Examples are included to demonstrate the approach.
Approximate Ranking from Pairwise Comparisons

A common problem in machine learning is to rank a set of n items based on pairwise comparisons. Here ranking refers to partitioning the items into sets of pre-specified sizes according to their scores, which includes identification of the top-k items as the most prominent special case. The score of a given item is defined as the probability that it beats a randomly chosen other item. Finding an exact ranking typically requires a prohibitively large number of comparisons, but in practice, approximate rankings are often adequate. Accordingly, we study the problem of finding approximate rankings from pairwise comparisons. We analyze an active ranking algorithm that counts the number of comparisons won, and decides whether to stop or which pair of items to compare next, based on confidence intervals computed from the data collected in previous steps. We show that this algorithm succeeds in recovering approximate rankings using a number of comparisons that is close to optimal up to logarithmic factors. We also present numerical results, showing that in practice, approximation can drastically reduce the number of comparisons required to estimate a ranking.
Joint Modeling of Content and Discourse Relations in Dialogues

We present a joint modeling approach to identify salient discussion points in spoken meetings as well as to label the discourse relations between speaker turns. A variation of our model is also discussed when discourse relations are treated as latent variables. Experimental results on two popular meeting corpora show that our joint model can outperform state-of-the-art approaches for both phrase-based content selection and discourse relation prediction tasks. We also evaluate our model on predicting the consistency among team members’ understanding of their group decisions. Classifiers trained with features constructed from our model achieve significant better predictive performance than the state-of-the-art.
Towards Scalable Network Delay Minimization

Reduction of end-to-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NP-hard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling that are targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.
Large deviation principle for dynamical systems coupled with diffusion–transmutation processes

Abstract In this paper, we introduce a mathematical apparatus that is relevant for understanding a dynamical system with small random perturbations and coupled with the so-called transmutation process — where the latter jumps from one mode to another, and thus modifying the dynamics of the system. In particular, we study the exit problem, i.e., an asymptotic estimate for the exit probabilities with which the corresponding processes exit from a given bounded open domain, and then formally prove a large deviation principle for the exit position joint with the type occupation times as the random perturbation vanishes. Moreover, under certain conditions, we also determine the exit place and the type of distribution at the exit time and, as a consequence of this, such information also give the limit of the Dirichlet problem for the corresponding partial differential equation systems with a vanishing small parameter.
Transfer learning for named-entity recognition with neural networks

Recent approaches based on artificial neural networks (ANNs) have shown promising results for named-entity recognition (NER). In order to achieve high performances, ANNs need to be trained on a large labeled dataset. However, labels might be difficult to obtain for the dataset on which the user wants to perform NER: label scarcity is particularly pronounced for patient note de-identification, which is an instance of NER. In this work, we analyze to what extent transfer learning may address this issue. In particular, we demonstrate that transferring an ANN model trained on a large labeled dataset to another dataset with a limited number of labels improves upon the state-of-the-art results on two different datasets for patient note de-identification.
Continuous symmetrization via polarization

This is a joint work with F. Brock. We will discuss a one-parameter family of transformations which transforms in a continuous way sets and functions into their (k, n)-Steiner symmetrizations. Our construction consists of two stages. On the first stage we employ a continuous symmetrization introduced in our paper in 1990 to transform sets and functions into their one-dimensional Steiner symmetrization. On this step some of our proofs depend on polarization. On the second stage we use Blaschke-Sarvas approximation theorem, which says that every k-dimensional Steiner symmetrization with 2 ≤ k ≤ n can be approximated by a sequence of (k−1)-dimensional Steiner symmetrizations. Using this result we give an inductive definition of a continuous (k, n)-Steiner symmetrization for any 2 ≤ k ≤ n. This transformation gives the desired continuous path along which all basic characteristics of sets and functions change monotonically. The latter leads to continuous versions of several convolution type inequalities and Dirichlet’s type inequalities and to continuous versions of comparison theorems for solutions of some elliptic and parabolic equations.
Computing Segre classes in arbitrary projective varieties

Abstract We give an algorithm for computing Segre classes of subschemes of arbitrary projective varieties by computing degrees of a sequence of linear projections. Based on the fact that Segre classes of projective varieties commute with intersections by general effective Cartier divisors, we can compile a system of linear equations which determine the coefficients for the Segre class pushed forward to projective space. The algorithm presented here comes after several others which solve the problem in special cases, where the ambient variety is for instance projective space; to our knowledge, this is the first algorithm to be able to compute Segre classes in projective varieties with arbitrary singularities.
Early Turn-Taking Prediction with Spiking Neural Networks for Human Robot Collaboration

Turn-taking is essential to the structure of human teamwork. Humans are typically aware of team members' intention to keep or relinquish their turn before a turn switch, where the responsibility of working on a shared task is shifted. Future co-robots are also expected to provide such competence. To that end, this paper proposes the Cognitive Turn-taking Model (CTTM), which leverages cognitive models (i.e., Spiking Neural Network) to achieve early turn-taking prediction. The CTTM framework can process multimodal human communication cues (both implicit and explicit) and predict human turn-taking intentions in an early stage. The proposed framework is tested on a simulated surgical procedure, where a robotic scrub nurse predicts the surgeon's turn-taking intention. It was found that the proposed CTTM framework outperforms the state-of-the-art turn-taking prediction algorithms by a large margin. It also outperforms humans when presented with partial observations of communication cues (i.e., less than 40 % of full actions). This early prediction capability enables robots to initiate turn-taking actions at an early stage, which facilitates collaboration and increases overall efficiency.
Homological stability for topological chiral homology of completions

Abstract By proving that several new complexes of embedded disks are highly connected, we obtain several new homological stability results. Our main result is homological stability for topological chiral homology on an open manifold with coefficients in certain partial framed E n -algebras. Using this, we prove a special case of a conjecture of Vakil and Wood on homological stability for complements of closures of particular strata in the symmetric powers of an open manifold and we prove that the bounded symmetric powers of closed manifolds satisfy homological stability rationally.
A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs

Cyber security is one of the most significant technical challenges in current times. Detecting adversarial activities, prevention of theft of intellectual properties and customer data is a high priority for corporations and government agencies around the world. Cyber defenders need to analyze massive-scale, high-resolution network flows to identify, categorize, and mitigate attacks involving networks spanning institutional and national boundaries. Many of the cyber attacks can be described as subgraph patterns, with prominent examples being insider infiltrations (path queries), denial of service (parallel paths) and malicious spreads (tree queries). This motivates us to explore subgraph matching on streaming graphs in a continuous setting. The novelty of our work lies in using the subgraph distributional statistics collected from the streaming graph to determine the query processingstrategy. Weintroducea“Lazy Search"algorithmwhere the search strategy is decided on a vertex-to-vertex basis depending on the likelihood of a match in the vertex neighborhood. We also propose a metric named “Relative Selectivity" that is used to select between different query processing strategies. Our experiments performed on real online news, network traffic stream and a synthetic social network benchmark demonstrate 10-100x speedups over selectivity agnostic approaches.
Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints

Given a constraint satisfaction problem (CSP) on n variables, x1, x2, . . . , xn ∈ {±1}, and m constraints, a global cardinality constraint has the form of Σni = 1xi = (1 − 2p)n, where p ∈ (Ω(1), 1 − Ω(1)) and pn is an integer. Let AV G be the expected number of constraints satisfied by randomly choosing an assignment to x1, x2, . . . , xn, complying with the global cardinality constraint. The CSP above average with the global cardinality constraint problem asks whether there is an assignment (complying with the cardinality constraint) that satisfies more than (AV G + t) constraints, where t is an input parameter.In this paper, we present an algorithm that finds a valid assignment satisfying more than (AV G + t) constraints (if there exists one) in time (2o(t2) + no(d)). Therefore, the CSP above average with the global cardinality constraint problem is fixed-parameter tractable.
Coping with Large Traffic Volumes in Schedule-Driven Traffic Signal Control

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to significantly improve traffic flow efficiency in complex urban road networks. However, in situations where vehicle volumes increase to the point that the physical capacity of a road network reaches or exceeds saturation, it has been observed that the effectiveness of a schedule-driven approach begins to degrade, leading to progressively higher network congestion. In essence, the traffic control problem becomes less of a scheduling problem and more of a queue management problem in this circumstance. In this paper we propose a composite approach to real-time traffic control that uses sensed information on queue lengths to influence scheduling decisions and gracefully shift the signal control strategy to queue management in high volume/high congestion settings. Specifically, queue-length information is used to establish weights for the sensed vehicle clusters that must be scheduled through a given intersection at any point, and hence bias the wait time minimization calculation. To compute these weights, we develop a model in which successive movement phases are viewed as different states of an Ising model, and parameters quantify strength of interactions. To ensure scalability, queue information is only exchanged between direct neighbors and the asynchronous nature of local intersection scheduling is preserved. We demonstrate the potential of the approach through microscopic traffic simulation of a real-world road network, showing a 60% reduction in average wait times over the baseline schedule-driven approach in heavy traffic scenarios. We also report initial field test results, which show the ability to reduce queues during heavy traffic periods.
How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery

When the linear measurements of an instance of low-rank matrix recovery satisfy a restricted isometry property (RIP) --- i.e. they are approximately norm-preserving --- the problem is known to contain no spurious local minima, so exact recovery is guaranteed. In this paper, we show that moderate RIP is not enough to eliminate spurious local minima, so existing results can only hold for near-perfect RIP. In fact, counterexamples are ubiquitous: every $x$ is the spurious local minimum of a rank-1 instance of matrix recovery that satisfies RIP. One specific counterexample has RIP constant $\delta=1/2$, but causes randomly initialized stochastic gradient descent (SGD) to fail 12\% of the time. SGD is frequently able to avoid and escape spurious local minima, but this empirical result shows that it can occasionally be defeated by their existence. Hence, while exact recovery guarantees will likely require a proof of no spurious local minima, arguments based solely on norm preservation will only be applicable to a narrow set of nearly-isotropic instances.