cssi/SciSciGPT-SciSciNet huggingface dataset:
Complexity classes as mathematical axioms

Treating a conjecture, P #P 6 NP, on the separation of complex- ity classes as an axiom, an implication is found in three manifold topology with little obvious connection to complexity theory. This is reminiscent of Harvey Friedman's work on finitistic interpretations of large cardinal axioms. This short paper introduces a new subject with a simple example. The theory of computation defines a plethora of complexity classes. While the techniques of diagonalization and oracle relativization have produced important separation results, for nearly forty years the most interesting (absolute) separation conjectures, such as P 6 NP remain unproven, and with the invention of ever more complexity classes, analogous separation conjectures have multiplied in number. With no prospect in sight for proving these conjectures (within ZFC), we pro- pose considering them instead as potential axioms and looking for what implications they might have in mathematics as a whole. This program is analogous to the search for interesting "finitistic" consequences of large cardinal axioms, an area explored by Harvey Friedman and collaborators ((4)). (Although, in the latter case, the large cardinal axioms are actually known to be independent of ZFC.) What would be the best possible theorem in this subject? It would be to postu- late a very weak separation "axiom," say P 6 PSPACE, and prove the Riemann hypothesis, i.e. an important mathematical result apparently far removed from complexity theory. Of course, we should be more modest. We will assume a more technical but well accepted separation "axiom" P #P 6 NP, which we call Axiom A, and prove a theorem, Theorem A, in knot theory. The theorem is easily and briefly expressed in terms of classical notions such as "girth" and "Dehn surgery" and appears to be as close to current research topics in knot theory as the known finitistic implications of the large cardinal axioms are to research in Ramsey theory, to continue that analogy. Theorem A is extremely believable but seems to exist in a "technique vacuum." What makes the theorem interesting is that it sounds both "very plausible" and "impossible to prove."
Analysis of Orbit Accumulation Points and The Greene–Krantz Conjecture

In \({\mathbb {C}}^2\), we classify the domains for which \({\mathrm{Aut}}(\Omega )\) is noncompact and describe these domains by their defining functions. This note is based on the technique of the scaling method introduced by Frankel (Bounded convex domains with compact quotients are symmetric spaces in complex dimension two (symmetric, manifold, automorphisms, affine geometry), 1986) and Kim (Trans Am Math Soc 319:139–153, 1990). One feature of this article is that we are able to analyze the defining functions of infinite type boundary. As a corollary, we also prove a result that under some conditions, \({\mathrm{Aut}}(\Omega )\) contains \({\mathbb {R}}\), which is an extension of (1986).
Multi-sensor conflict measurement and information fusion

In sensing applications where multiple sensors observe the same scene, fusing sensor outputs can provide improved results. However, if some of the sensors are providing lower quality outputs, e.g. when one or more sensors has a poor signal-to-noise ratio (SNR) and therefore provides very noisy data, the fused results can be degraded. In this work, a multi-sensor conflict measure is proposed which estimates multi-sensor conflict by representing each sensor output as interval-valued information and examines the sensor output overlaps on all possible n-tuple sensor combinations. The conflict is based on the sizes of the intervals and how many sensors output values lie in these intervals. In this work, conflict is defined in terms of how little the output from multiple sensors overlap. That is, high degrees of overlap mean low sensor conflict, while low degrees of overlap mean high conflict. This work is a preliminary step towards a robust conflict and sensor fusion framework. In addition, a sensor fusion algorithm is proposed based on a weighted sum of sensor outputs, where the weights for each sensor diminish as the conflict measure increases. The proposed methods can be utilized to (1) assess a measure of multi-sensor conflict, and (2) improve sensor output fusion by lessening weighting for sensors with high conflict. Using this measure, a simulated example is given to explain the mechanics of calculating the conflict measure, and stereo camera 3D outputs are analyzed and fused. In the stereo camera case, the sensor output is corrupted by additive impulse noise, DC offset, and Gaussian noise. Impulse noise is common in sensors due to intermittent interference, a DC offset a sensor bias or registration error, and Gaussian noise represents a sensor output with low SNR. The results show that sensor output fusion based on the conflict measure shows improved accuracy over a simple averaging fusion strategy.
KAZHDAN'S PROPERTY T FOR DISCRETE QUANTUM GROUPS

We give a simple definition of property T for discrete quantum groups, and prove the basic expected properties: discrete quantum groups with property T are finitely generated and unimodular. Moreover we show that, for "I.C.C." discrete quantum groups, property T is equivalent to Connes' property T for the dual von Neumann algebra. This allows us to give the first example of a property T discrete quantum group which is not a group using the twisting construction.
A tensor approach to learning mixed membership community models

Community detection is the task of detecting hidden communities from observed interactions. Guaranteed community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and provide guaranteed community detection for a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced by Airoldi et al. (2008). This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. Moreover, it contains the stochastic block model as a special case. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebraic operations, e.g., singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. As an important special case, our results match the best known scaling requirements for the (homogeneous) stochastic block model.
Orthogonal units of the bifree double Burnside ring

Abstract The bifree double Burnside ring B Δ ( G , G ) of a finite group G has a natural anti-involution. We study the group B ∘ Δ ( G , G ) of orthogonal units in B Δ ( G , G ) . It is shown that this group is always finite and contains a subgroup isomorphic to B ( G ) × ⋊ Out ( G ) , where B ( G ) × denotes the unit group of the Burnside ring of G and Out ( G ) denotes the outer automorphism group of G. Moreover it is shown that if G is nilpotent then B ∘ Δ ( G , G ) ≅ B ( G ) × ⋊ Out ( G ) . The results can be interpreted as positive answers to questions on equivalences of p-blocks of group algebras in the case that the block is the group algebra of a p-group.
Scheduling Jobs with Random Resource Requirements in Computing Clusters

We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource requirements (e.g. memory requirements) arrive over time and must be served by a cluster of servers, each with a finite resource capacity. To improve throughput and delay, the scheduler can pack as many jobs as possible in the servers subject to their capacity constraints. Motivated by the ever-increasing complexity of workloads in shared clusters, we consider a setting where the jobs’ resource requirements belong to a very large number of diverse types or, in the extreme, even infinitely many types, e.g. when resource requirements are drawn from an unknown distribution over a continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) dimensional setting. We first characterize a fundamental limit on the maximum throughput in such setting, and then develop oblivious scheduling algorithms that have tow complexity and can achieve at least 1/2 and 2/3 of the maximum throughput, without the knowledge of traffic or resource requirement distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms.
Finite, Fiber- and Orientation-Preserving Group Actions on Totally Orientable Seifert Manifolds

In this paper we consider the finite groups that act fiber- and orientation-preservingly on closed, compact, and orientable Seifert manifolds that fiber over an orientable base space. We establish a method of constructing such group actions and then show that if an action satisfies a condition on the obstruction class of the Seifert manifold, it can be derived from the given construction. The obstruction condition is refined and the general structure of the finite groups that act via the construction is provided.
On the Network Topology Dependent Solution Count of the Algebraic Load Flow Equations

Active research activity in power systems areas has focused on developing computational methods to solve load flow equations where a key question is the maximum number of solutions. Although several upper bounds exist, recent studies have hinted that much sharper upper bounds that depend on the topology of underlying power networks may exist. This paper provides a significant refinement of these observations. We also develop a geometric construction called adjacency polytope that accurately captures the topology of a power network and is immensely useful in the computation of the solution bound. Finally, we highlight the significant implications of the development of such solution bounds in numerically solving load flow equations.
Force-field functor theory: classical force-fields which reproduce equilibrium quantum distributions

Feynman and Hibbs were the first to variationally determine an effective potential whose associated classical canonical ensemble approximates the exact quantum partition function. We examine the existence of a map between the local potential and an effective classical potential which matches the exact quantum equilibrium density and partition function. The usefulness of such a mapping rests in its ability to readily improve Born-Oppenheimer potentials for use with classical sampling. We show that such a map is unique and must exist. To explore the feasibility of using this result to improve classical molecular mechanics, we numerically produce a map from a library of randomly generated one-dimensional potential/effective potential pairs then evaluate its performance on independent test problems. We also apply the map to simulate liquid para-hydrogen, finding that the resulting radial pair distribution functions agree well with path integral Monte Carlo simulations. The surprising accessibility and transferability of the technique suggest a quantitative route to adapting Born-Oppenheimer potentials, with a motivation similar in spirit to the powerful ideas and approximations of density functional theory.
Towards the locality of Vizing’s theorem

Vizing showed that it suffices to color the edges of a simple graph using Δ + 1 colors, where Δ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Δ + Θ(√Δ))-edge-coloring algorithm that runs in (n) rounds by Chang et al. [SODA 2018] and the deterministic (Δ + (n))-edge-coloring algorithm that runs in (Δ, logn) rounds by Ghaffari et al. [STOC 2018]. We present two distributed edge-coloring algorithms that run in (Δ,logn) rounds. The first algorithm, with randomization, uses only Δ+2 colors. The second algorithm is a deterministic algorithm that uses Δ+ O(logn/ loglogn) colors. Our approach is to reduce the distributed edge-coloring problem into an online and restricted version of balls-into-bins problem. If l is the maximum load of the bins, our algorithm uses Δ + 2l − 1 colors. We show how to achieve l = 1 with randomization and l = O(logn / loglogn) without randomization.
Inversion of diffraction data for amorphous materials.

The general and practical inversion of diffraction data–producing a computer model correctly representing the material explored–is an important unsolved problem for disordered materials. Such modeling should proceed by using our full knowledge base, both from experiment and theory. In this paper, we describe a robust method to jointly exploit the power of ab initio atomistic simulation along with the information carried by diffraction data. The method is applied to two very different systems: amorphous silicon and two compositions of a solid electrolyte memory material silver-doped GeSe3. The technique is easy to implement, is faster and yields results much improved over conventional simulation methods for the materials explored. By direct calculation, we show that the method works for both poor and excellent glass forming materials. It offers a means to add a priori information in first-principles modeling of materials and represents a significant step toward the computational design of non-crystalline materials using accurate interatomic interactions and experimental information.
Rapidly computing sparse Legendre expansions via sparse Fourier transforms

In this paper, we propose a general strategy for rapidly computing sparse Legendre expansions. The resulting methods yield a new class of fast algorithms capable of approximating a given function f : [ź1, 1] ź ź with a near-optimal linear combination of s Legendre polynomials of degree ≤ N in just (slogN)O(1)$(s \log N)^{\mathcal {O}(1)}$-time. When s ź N, these algorithms exhibit sublinear runtime complexities in N, as opposed to traditional Ω(NlogN)-time methods for computing all of the first N Legendre coefficients of f. Theoretical as well as numerical results demonstrate the effectiveness of the proposed methods.
Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor

We investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries, for finite completability of a low-rank tensor given some components of its Tucker rank. In order to find the deterministic necessary and sufficient conditions, we propose an algebraic geometric analysis on the Tucker manifold, which allows us to incorporate multiple rank components in the proposed analysis in contrast with the conventional geometric approaches on the Grassmannian manifold. This analysis characterizes the algebraic independence of a set of polynomials defined based on the sampling pattern, which is closely related to finite completability of the sampled tensor, where finite completability simply means that the number of possible completions of the sampled tensor is finite. Probabilistic conditions are then studied and a lower bound on the sampling probability is given, which guarantees that the proposed deterministic conditions on the sampling patterns for finite completability hold with high probability. Furthermore, using the proposed geometric approach for finite completability, we propose a sufficient condition on the sampling pattern that ensures there exists exactly one completion of the sampled tensor.
Electric Vehicle Charging Station Placement Method for Urban Areas

For accommodating more electric vehicles (EVs) to battle against fossil fuel emission, the problem of charging station placement is inevitable and could be costly if done improperly. Research considers a general setup using conditions such as driving ranges for planning. However, most of the EV growths in the next decades will happen in urban areas where driving range is not the biggest concern. For such a need, we consider several practical aspects of urban systems, such as voltage regulation cost and protection device upgrade resulting from the large integration of EVs. Notably, our diversified objective can reveal the trade-off between different factors in different cities worldwide. To understand the global optimum of large-scale analysis, we studied each feature to preserve the problem convexity. Our sensitivity analysis before and after convexification shows that our approach is not only universally applicable but also has a small approximation error for prioritizing the most urgent constraint in a specific setup. Finally, numerical results demonstrate the trade-off, the relationship between different factors and the global objective, and the small approximation error. A unique observation in this paper shows the importance of incorporating the protection device upgrade in urban system planning on charging stations.
Sterile Neutrino Production Through a Matter Effect Enhancement at Long Baselines

If sterile neutrinos have a neutral coupling to standard model fermions, matter effect resonant transitions to sterile neutrinos and excess neutral-current events could manifest at long baseline experiments. Assuming a single sterile neutrino with a neutral coupling to fermionic matter, we re-examine bounds on sterile neutrino production at long baselines from the MINOS result Pνμ →νs < 0.22 (90% CL). We demonstrate that sterile neutrinos with a neutral vector coupling to fermionic matter could evade the MINOS limit, allowing a higher fraction of active to sterile neutrino conversion at long baselines. Scanning the parameter space of sterile neutrino matter effect fits of the LSND and MiniBooNe data, we show that in the case of a vector singlet coupling of sterile neutrinos to matter, some favored parametrizations of these fits would create neutral-current event excesses above standard model predictions at long baseline experiments (e.g. MINOS and OPERA).
On the local k-elasticities of Puiseux monoids

If M is an atomic monoid and x is a nonzero non-unit element of M, then the set of lengths L(x) of x is the set of all possible lengths of factorizations of x, where the length of a factorization i...
Homogenization of dissipative, noisy, Hamiltonian dynamics

Abstract We study the dynamics of a class of Hamiltonian systems with dissipation, coupled to noise, in a singular (small mass) limit. We derive the homogenized equation for the position degrees of freedom in the limit, including the presence of a noise-induced drift term. We prove convergence to the solution of the homogenized equation in probability and, under stronger assumptions, in an L p -norm. Applications cover the overdamped limit of particle motion in a time-dependent electromagnetic field, on a manifold with time-dependent metric, and the dynamics of nuclear matter.
Smooth metric measure spaces with non-negative curvature

We study both function theoretic and spectral properties on complete noncompact smooth metric measure space $(M,g,e^{-f}dv)$ with nonnegative Bakry-\'{E}mery Ricci curvature. Among other things, we derive a gradient estimate for positive $f$-harmonic functions and obtain as a consequence the strong Liouville property under the optimal sublinear growth assumption on $f.$ We also establish a sharp upper bound of the bottom spectrum of the $f$-Laplacian in terms of the linear growth rate of $f.$ Moreover, we show that if equality holds and $M$ is not connected at infinity, then $M$ must be a cylinder. As an application, we conclude steady Ricci solitons must be connected at infinity.
WAVE FIELD CORRELATIONS IN WEAKLY MISMATCHED RANDOM MEDIA

This paper concerns the derivation of a Fokker–Planck equation for the correlation of two high frequency wave fields propagating in two different random media. The mismatch between the random media needs be small, on the order of the wavelength, and their correlation length needs be large relative to the wavelength. The loss of correlation caused by the mismatch in the random media is quantified and the limit process for the phase difference is obtained. The derivation is based on a random Liouville equation to model high frequency correlations and on the method of characteristics to characterize mixing in the random Liouville equation. Applications of such correlation loss include the monitoring in time of random media and the analysis of time reversed waves in changing heterogeneous domains.
Human‐centered artificial intelligence and machine learning

Humans are increasingly coming into contact with artificial intelligence and machine learning systems. Human-centered artificial intelligence is a perspective on AI and ML that algorithms must be designed with awareness that they are part of a larger system consisting of humans. We lay forth an argument that human-centered artificial intelligence can be broken down into two aspects: (1) AI systems that understand humans from a sociocultural perspective, and (2) AI systems that help humans understand them. We further argue that issues of social responsibility such as fairness, accountability, interpretability, and transparency.
Interplay of minimax estimation and minimax support recovery under sparsity.

In this paper, we study a new notion of scaled minimaxity for sparse estimation in high-dimensional linear regression model. We present more optimistic lower bounds than the one given by the classical minimax theory and hence improve on existing results. We recover sharp results for the global minimaxity as a consequence of our study. Fixing the scale of the signal-to-noise ratio, we prove that the estimation error can be much smaller than the global minimax error. We construct a new optimal estimator for the scaled minimax sparse estimation. An optimal adaptive procedure is also described.
On distributed cooperative decision-making in multiarmed bandits

We study the explore-exploit tradeoff in distributed cooperative decision-making using the context of the multiarmed bandit (MAB) problem. For the distributed cooperative MAB problem, we design the cooperative UCB algorithm that comprises two interleaved distributed processes: (i) running consensus algorithms for estimation of rewards, and (ii) upper-confidence-bound-based heuristics for selection of arms. We rigorously analyze the performance of the cooperative UCB algorithm and characterize the influence of communication graph structure on the decision-making performance of the group.
Curvature bounds via an isoperimetric comparison for Ricci flow on surfaces

A comparison theorem for the isoperimetric profile on the universal cover of surfaces evolving by normalised Ricci flow is proven. For any initial metric, a model comparison is constructed that initially lies below the profile of the initial metric and which converges to the pro- file of the constant curvature metric. The comparison theorem implies that the evolving metric is bounded below by the model comparison for all time and hence converges to the constant curvature profile. This yields a curvature bound and a bound on the isoperimetric constant, leading to a direct proof that the metric converges to the constant cur- vature metric.
Short Proof of a Conjecture Concerning Split-By-Nilpotent Extensions

Let C be a finite dimensional algebra with B a split extension by a nilpotent bimodule E. We provide a short proof to a conjecture by Assem and Zacharia concerning properties of $$\mathop {\text {mod}}B$$ inherited by $$\mathop {\text {mod}}C$$ . We show if B is a tilted algebra, then C is a tilted algebra.
Feedback Solution to Optimal Switching Problems With Switching Cost

The problem of optimal switching between nonlinear autonomous subsystems is investigated in this paper where the objective is not only bringing the states to close to the desired point, but also adjusting the switching pattern, in the sense of penalizing switching occurrences and assigning different preferences to utilization of different modes. The mode sequence is unspecified and a switching cost term is used in the cost function for penalizing each switching. It is shown that once a switching cost is incorporated, the optimal cost-to-go function depends on the subsystem which was active at the previous time step. Afterward, an approximate dynamic programming-based method is developed, which provides an approximation of the optimal solution to the problem in a feedback form and for different initial conditions . Finally, the performance of the method is analyzed through numerical examples.
The Hidden Subgroup Problem and Post-quantum Group-Based Cryptography

In this paper we discuss the Hidden Subgroup Problem (HSP) in relation to post-quantum cryptography. We review the relationship between HSP and other computational problems, discuss an optimal solution method, and review results about the quantum complexity of HSP. We also overview some platforms for group-based cryptosystems. Notably, efficient algorithms for solving HSP in the proposed infinite group platforms are not yet known.
Integrals Involving Rudin–Shapiro Polynomials and Sketch of a Proof of Saffari’s Conjecture

The Rudin–Shapiro polynomials \(P_k(z)\), are defined by a certain linear functional recurrence equation and are of interest in signal processing due to their special autocorrelation properties. An algorithmic approach to computation of the moments of these polynomials is given. A proof sketch is given of Saffari’s Conjecture for the asymptotic growth of these moments.
A comparative study of fairness-enhancing interventions in machine learning

Computers are increasingly used to make decisions that have significant impact on people's lives. Often, these predictions can affect different population subgroups disproportionately. As a result, the issue of fairness has received much recent interest, and a number of fairness-enhanced classifiers have appeared in the literature. This paper seeks to study the following questions: how do these different techniques fundamentally compare to one another, and what accounts for the differences? Specifically, we seek to bring attention to many under-appreciated aspects of such fairness-enhancing interventions that require investigation for these algorithms to receive broad adoption. We present the results of an open benchmark we have developed that lets us compare a number of different algorithms under a variety of fairness measures and existing datasets. We find that although different algorithms tend to prefer specific formulations of fairness preservations, many of these measures strongly correlate with one another. In addition, we find that fairness-preserving algorithms tend to be sensitive to fluctuations in dataset composition (simulated in our benchmark by varying training-test splits) and to different forms of preprocessing, indicating that fairness interventions might be more brittle than previously thought.
Stability Theory of Stochastic Models in Opinion Dynamics

We consider a certain class of nonlinear maps that preserve the probability simplex, i.e., stochastic maps, which are inspired by the DeGroot–Friedkin model of belief/opinion propagation over influence networks. The corresponding dynamical models describe the evolution of the probability distribution of interacting species. Such models where the probability transition mechanism depends nonlinearly on the current state are often referred to as nonlinear Markov chains . In this paper, we develop stability results and study the behavior of representative opinion models. The stability certificates are based on the contractivity of the nonlinear evolution in the $\ell _1$ -metric. We apply the theory to two types of opinion models where the adaptation of the transition probabilities to the current state is exponential and linear—both of these can display a wide range of behaviors. We discuss continuous-time and other generalizations.
Deception in Optimal Control

In this paper, we consider an adversarial scenario where one agent seeks to achieve an objective, and its adversary seeks to learn the agent’s intentions and prevent the agent from achieving its objective. Thus, the agent has an incentive to try to deceive the adversary about its intentions, while at the same time working to achieve its objective. The primary contribution of this paper is to introduce a mathematically rigorous framework for the notion of deception within the context of optimal control. The central notion introduced in the paper is that of a belief-induced reward: a reward dependent not only on the agent’s state and action, but also adversary’s beliefs. While the paper focuses on the setting of Markov decision processes, the proposed framework allows for deception to be defined in an arbitrary control system endowed with a reward function. Furthermore, we discuss design of optimal deceptive strategies, under possible additional specifications on agent’s behavior or uncertainty in agent’s knowledge about the adversary’s learning process, and show that such design reduces to known problems in control design on partially observable or uncertain Markov decision processes. The notion of deception is illustrated on a running example of “cops and deceptive robbers”. We show that an optimal deceptive strategy of this example, designed using the theory introduced in the paper, follows the intuitive idea of how to deceive an adversary in such a scenario.
Phase retrieval in infinite-dimensional Hilbert spaces

The main result of this paper states that phase retrieval in infinite-dimensional Hilbert spaces is never uniformly stable, in sharp contrast to the finite dimensional setting in which phase retrieval is always stable. This leads us to derive stability results for signals depending on how well they are approximated by finite expansions.
On Closeness to k-Wise Uniformity.

A probability distribution over {-1, 1}^n is (eps, k)-wise uniform if, roughly, it is eps-close to the uniform distribution when restricted to any k coordinates. We consider the problem of how far an (eps, k)-wise uniform distribution can be from any globally k-wise uniform distribution. We show that every (eps, k)-wise uniform distribution is O(n^(k/2) eps)-close to a k-wise uniform distribution in total variation distance. In addition, we show that this bound is optimal for all even k: we find an (eps, k)-wise uniform distribution that is Omega(n^(k/2) eps)-far from any k-wise uniform distribution in total variation distance. For k = 1, we get a better upper bound of O(eps), which is also optimal. One application of our closeness result is to the sample complexity of testing whether a distribution is k-wise uniform or delta-far from k-wise uniform. We give an upper bound of O(n^k/delta^2) (or O(log n/delta^2) when k = 1) on the required samples. We show an improved upper bound of O~(n^(k/2)/delta^2) for the special case of testing fully uniform vs. delta-far from k-wise uniform. Finally, we complement this with a matching lower bound of Omega(n/delta^2) when k = 2. Our results improve upon the best known bounds from [AAK+07], and have simpler proofs.
Black-Box Reductions for Parameter-free Online Learning in Banach Spaces

We introduce several new black-box reductions that significantly improve the design of adaptive and parameter-free online learning algorithms by simplifying analysis, improving regret guarantees, and sometimes even improving runtime. We reduce parameter-free online learning to online exp-concave optimization, we reduce optimization in a Banach space to one-dimensional optimization, and we reduce optimization over a constrained domain to unconstrained optimization. All of our reductions run as fast as online gradient descent. We use our new techniques to improve upon the previously best regret bounds for parameter-free learning, and do so for arbitrary norms.
The non-Euclidean Euclidean algorithm

In this paper we demonstrate how the geometrically motivated algorithm to determine whether a two-generator real Mobius group acting on the Poincare plane is or is not discrete can be interpreted as a non-Euclidean Euclidean algorithm. That is, the algorithm can be viewed as an application of the Euclidean division algorithm to real numbers that represent hyperbolic distances. In the case that the group is discrete and free, the algorithmic procedure also gives a non-Euclidean Euclidean algorithm to find the three shortest curves on the corresponding quotient surface.
A greedy algorithm for the analysis transform domain

Many image processing applications benefited remarkably from the theory of sparsity. One model of sparsity is the cosparse analysis one. It was shown that using 1-minimization one might stably recover a cosparse signal from a small set of random linear measurements if the operator is a frame. Another effort has provided guarantee for dictionaries that have a near optimal projection procedure using greedy-like algorithms. However, no claims have been given for frames. A common drawback of all these existing techniques is their high computational cost for large dimensional problems.In this work we propose a new greedy-like technique with theoretical recovery guarantees for frames as the analysis operator, closing the gap between greedy and relaxation techniques. Our results cover both the case of bounded adversarial noise, where we show that the algorithm provides us with a stable reconstruction, and the one of random Gaussian noise, for which we prove that it has a denoising effect, closing another gap in the analysis framework. Our proposed program, unlike the previous greedy-like ones that solely act in the signal domain, operates mainly in the analysis operators transform domain. Besides the theoretical benefit, the main advantage of this strategy is its computational efficiency that makes it easily applicable to visually big data. We demonstrate its performance on several high dimensional images.
A portable, 3D-printing enabled multi-vehicle platform for robotics research and education

microMVP is an affordable, portable, and open source micro-scale mobile robot platform designed for robotics research and education. As a complete and unique multi-vehicle platform enabled by 3D printing and the maker culture, microMVP can be easily reproduced and requires little maintenance: a set of six micro vehicles, each measuring 8 × 5 × 6 cubic centimeters and weighing under 100 grams, and the accompanying tracking platform can be fully assembled in under two hours, all from readily available components. In this paper, we describe microMVP's hardware and software architecture, and the design thoughts that go into the making of the platform. The capabilities of microMVP APIs are then demonstrated with several single- and multi-robot path and motion planning algorithms. microMVP supports all common operation systems.
Fine-grained Entity Typing through Increased Discourse Context and Adaptive Classification Thresholds

Fine-grained entity typing is the task of assigning fine-grained semantic types to entity mentions. We propose a neural architecture which learns a distributional semantic representation that leverages a greater amount of semantic context – both document and sentence level information – than prior work. We find that additional context improves performance, with further improvements gained by utilizing adaptive classification thresholds. Experiments show that our approach without reliance on hand-crafted features achieves the state-of-the-art results on three benchmark datasets.
Optimal Filter Design for Consensus on Random Directed Graphs

Optimal design of consensus acceleration graph filters relates closely to the eigenvalues of the consensus iteration matrix. This task is complicated by random networks with uncertain iteration matrix eigenvalues. Filter design methods based on the spectral asymptotics of consensus iteration matrices for large-scale, random undirected networks have been previously developed both for constant and for time-varying network topologies. This work builds upon these results by extending analysis to large-scale, constant, random directed networks. The proposed approach uses theorems by Girko that analytically produce deterministic approximations of the empirical spectral distribution for suitable non-Hermitian random matrices. The approximate empirical spectral distribution defines filtering regions in the proposed filter optimization problem, which must be modified to accommodate complex-valued eigenvalues. Presented numerical simulations demonstrate good results. Additionally, limitations of the proposed method are discussed.
A relatively small turing machine whose behavior is independent of set theory

Since the definition of the Busy Beaver function by Rado in 1962, an interesting open question has been what the smallest value of n for which BB(n) is independent of ZFC set theory. Is this n approximately 10, or closer to 1,000,000, or is it even larger? In this paper, we show that it is at most 7,918 by presenting an explicit description of a 7,918-state Turing machine Z with 1 tape and a 2-symbol alphabet that cannot be proved to run forever in ZFC (even though it presumably does), assuming ZFC is consistent. The machine is based on work of Harvey Friedman on independent statements involving order-invariant graphs. In doing so, we give the first known upper bound on the highest provable Busy Beaver number in ZFC. We also present a 4,888-state Turing machine G that halts if and only if there is a counterexample to Goldbach’s conjecture, and a 5,372-state Turing machine R that halts if and only if the Riemann hypothesis is false. To create G, R, and Z, we develop and use a higher-level language, Laconic, which is much more convenient than direct state manipulation.
Soft Layer-Specific Multi-Task Summarization with Entailment and Question Generation

An accurate abstractive summary of a document should contain all its salient information and should be logically entailed by the input document. We improve these important aspects of abstractive summarization via multi-task learning with the auxiliary tasks of question generation and entailment generation, where the former teaches the summarization model how to look for salient questioning-worthy details, and the latter teaches the model how to rewrite a summary which is a directed-logical subset of the input document. We also propose novel multi-task architectures with high-level (semantic) layer-specific sharing across multiple encoder and decoder layers of the three tasks, as well as soft-sharing mechanisms (and show performance ablations and analysis examples of each contribution). Overall, we achieve statistically significant improvements over the state-of-the-art on both the CNN/DailyMail and Gigaword datasets, as well as on the DUC-2002 transfer setup. We also present several quantitative and qualitative analysis studies of our model’s learned saliency and entailment skills.
CASI: A Convolutional Neural Network Approach for Shell Identification

We utilize techniques from deep learning to identify signatures of stellar feedback in simulated molecular clouds. Specifically, we implement a deep neural network with an architecture similar to U-Net and apply it to the problem of identifying wind-driven shells and bubbles using data from magneto-hydrodynamic simulations of turbulent molecular clouds with embedded stellar sources. The network is applied to two tasks, dense regression and segmentation, on two varieties of data, simulated density and synthetic 12 CO observations. Our Convolutional Approach for Shell Identification (CASI) is able to obtain a true positive rate greater than 90\%, while maintaining a false positive rate of 1\%, on two segmentation tasks and also performs well on related regression tasks. The source code for CASI is available on GitLab.
Ultrathin Ceramic Piezoelectric Films via Room-Temperature Electrospray Deposition of ZnO Nanoparticles for Printed GHz Devices.

High-frequency devices are key enablers of state-of-the-art electronics used in a wide and diverse range of exciting applications such as inertial navigation, communications, power conversion, medi...
Flexible Representative Democracy: An Introduction with Binary Issues.

We introduce Flexible Representative Democracy (FRD), a novel hybrid of Representative Democracy (RD) and direct democracy (DD), in which voters can alter the issue-dependent weights of a set of elected representatives. In line with the literature on Interactive Democracy, our model allows the voters to actively determine the degree to which the system is direct versus representative. However, unlike Liquid Democracy, FRD uses strictly non-transitive delegations, making delegation cycles impossible, and maintains a fixed set of accountable elected representatives. We present FRD and analyze it using a computational approach with issues that are binary and symmetric; we compare the outcomes of various democratic systems using Direct Democracy with majority voting as an ideal baseline. First, we demonstrate the shortcomings of Representative Democracy in our model. We provide NP-Hardness results for electing an ideal set of representatives, discuss pathologies, and demonstrate empirically that common multi-winner election rules for selecting representatives do not perform well in expectation. To analyze the behavior of FRD, we begin by providing theoretical results on how issue-specific delegations determine outcomes. Finally, we provide empirical results comparing the outcomes of RD with fixed sets of proxies across issues versus FRD with issue-specific delegations. Our results show that variants of Proxy Voting yield no discernible benefit over RD and reveal the potential for FRD to improve outcomes as voter participation increases, further motivating the use of issue-specific delegations.
Multi-view Community Detection in Facebook Public Pages

Community detection in social networks is widely studied because of its importance in uncovering how people connect and interact. However, little attention has been given to community structure in Facebook public pages. In this study, we investigate the community detection problem in Facebook newsgroup pages. In particular, to deal with the diversity of user activities, we apply multi-view clustering to integrate different views, for example, likes on posts and likes on comments. In this study, we explore the community structure in Facebook public pages. The results show that our method can effectively reduce isolates and improve the quality of community structure.
A Fast Distributed Asynchronous Newton-Based Optimization Algorithm

One of the most important problems in the field of distributed optimization is the problem of minimizing a sum of local convex objective functions over a networked system. Most of the existing work in this area focuses on developing distributed algorithms in a synchronous setting under the presence of a central clock, where the agents need to wait for the slowest one to finish the update, before proceeding to the next iterate. Asynchronous distributed algorithms remove the need for a central coordinator, reduce the synchronization wait, and allow some agents to compute faster and execute more iterations. In the asynchronous setting, the only known algorithms for solving this problem could achieve an either linear or sublinear rate of convergence. In this paper, we build upon the existing literature to develop and analyze an asynchronous Newton-based method to solve a penalized version of the problem. We show that this algorithm guarantees almost sure convergence with a global linear and local quadratic rate in expectation. Numerical studies confirm the superior performance of our algorithm against other asynchronous methods.
Public and elite opinion on international human rights law: Completing the causal chain of the domestic compliance mechanism

AbstractWhy do states comply with international human rights law? Scholars have looked to domestic politics to suggest a constituency-driven domestic compliance mechanism. However, it is unclear if...
Kernel Transformer Networks for Compact Spherical Convolution

Ideally, 360° imagery could inherit the deep convolutional neural networks (CNNs) already trained with great success on perspective projection images. However, existing methods to transfer CNNs from perspective to spherical images introduce significant computational costs and/or degradations in accuracy. We present the Kernel Transformer Network (KTN) to efficiently transfer convolution kernels from perspective images to the equirectangular projection of 360° images. Given a source CNN for perspective images as input, the KTN produces a function parameterized by a polar angle and kernel as output. Given a novel 360° image, that function in turn can compute convolutions for arbitrary layers and kernels as would the source CNN on the corresponding tangent plane projections. Distinct from all existing methods, KTNs allow model transfer: the same model can be applied to different source CNNs with the same base architecture. This enables application to multiple recognition tasks without re-training the KTN. Validating our approach with multiple source CNNs and datasets, we show that KTNs improve the state of the art for spherical convolution. KTNs successfully preserve the source CNN’s accuracy, while offering transferability, scalability to typical image resolutions, and, in many cases, a substantially lower memory footprint.
Efficiency Analysis of Health Insurers’ Scale of Operations and Group Affiliation with a Perspective Toward Health Insurers’ Mergers and Acquisitions Effects

This research uses an indirect methodology to examine the effects of health insurance mergers and acquisitions by analyzing the impact of insurers’ scale of operations and group affiliation status ...
The Parallel Auditory Brainstem Response

The frequency-specific tone-evoked auditory brainstem response (ABR) is an indispensable tool in both the audiology clinic and research laboratory. Most frequently, the toneburst ABR is used to estimate hearing thresholds in infants, toddlers, and other patients for whom behavioral testing is not feasible. Therefore, results of the ABR exam form the basis for decisions regarding interventions and hearing habilitation with implications extending far into the child's future. Currently, responses are elicited by periodic sequences of toneburst stimuli presented serially to one ear at a time, which take a long time to measure multiple frequencies and intensities, and provide incomplete information if the infant wakes up early. Here, we describe a new method, the parallel ABR (pABR), which uses randomly timed toneburst stimuli to simultaneously acquire ABR waveforms to five frequencies in both ears. Here, we describe the pABR and quantify its effectiveness in addressing the greatest drawback of current methods: test duration. We show that in adults with normal hearing the pABR yields high-quality waveforms over a range of intensities, with similar morphology to the standard ABR in a fraction of the recording time. Furthermore, longer latencies and smaller amplitudes for low frequencies at a high intensity evoked by the pABR versus serial ABR suggest that responses may have better place specificity due to the masking provided by the other simultaneous toneburst sequences. Thus, the pABR has substantial potential for facilitating faster accumulation of more diagnostic information that is important for timely identification and treatment of hearing loss.