cssi/SciSciGPT-SciSciNet huggingface dataset:
Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph G with (G)(G)1 has a maximum matching M such that any two M-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan etal. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for k-regular graphs with 4k6. All counterexamples for k-regular graphs (k7) given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all k-regular simple graphs and also k-regular multigraphs with k4.
Guarding against spurious discoveries in high dimensions

Many data mining and statistical machine learning algorithms have been developed to select a subset of covariates to associate with a response variable. Spurious discoveries can easily arise in high-dimensional data analysis due to enormous possibilities of such selections. How can we know statistically our discoveries better than those by chance? In this paper, we define a measure of goodness of spurious fit, which shows how good a response variable can be fitted by an optimally selected subset of covariates under the null model, and propose a simple and effective LAMM algorithm to compute it. It coincides with the maximum spurious correlation for linear models and can be regarded as a generalized maximum spurious correlation. We derive the asymptotic distribution of such goodness of spurious fit for generalized linear models and L1 regression. Such an asymptotic distribution depends on the sample size, ambient dimension, the number of variables used in the fit, and the covariance information. It can be consistently estimated by multiplier bootstrapping and used as a benchmark to guard against spurious discoveries. It can also be applied to model selection, which considers only candidate models with goodness of fits better than those by spurious fits. The theory and method are convincingly illustrated by simulated examples and an application to the binary outcomes from German Neuroblastoma Trials.
Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev

Logarithmic Sobolev inequalities are a powerful way to estimate the rate of convergence of Markov chains and to derive concentration inequalities on distributions. We prove that the log-Sobolev constant of any isotropic logconcave density in Rn with support of diameter D is Ω(1/D), resolving a question posed by Frieze and Kannan in 1997. This is asymptotically the best possible estimate and improves on the previous bound of Ω(1/D2) by Kannan-Lovasz-Montenegro. It follows that for any isotropic logconcave density, the ball walk with step size δ=Θ(1/√n) mixes in O*(n2D) proper steps from any starting point. This improves on the previous best bound of O*(n2D2) and is also asymptotically tight. The new bound leads to the following refined large deviation inequality for an L-Lipschitz function g over an isotropic logconcave density p: for any t>0, [complex formula not displayed] where ḡ is the median or mean of g for x∼ p; this improves on previous bounds by Paouris and by Guedon-Milman. Our main proof is based on stochastic localization together with a Stieltjes-type barrier function.
Geometric Schur Duality of Classical Type

This is a generalization of the classic work of Beilinson, Lusztig and MacPherson. In this paper (and an Appendix) we show that the quantum algebras obtained via a BLM-type stabilization procedure in the setting of partial Flag varieties of type B/C are two (modified) coideal subalgebras of the quantum general linear Lie algebra, $$ \overset{.}{\mathbf{U}} $$ ℐ and $$ \overset{.}{\mathbf{U}} $$ ʅ . We provide a geometric realization of the Schur-type duality of Bao–Wang between such a coideal algebra and Iwahori–Hecke algebra of type B. The monomial bases and canonical bases of the Schur algebras and the modified coideal algebra $$ \overset{.}{\mathbf{U}} $$ ℐ are constructed. In an Appendix by three authors, a more subtle 2-step stabilization procedure leading to $$ \overset{.}{\mathbf{U}} $$ ʅ is developed, and then monomial and canonical bases of $$ \overset{.}{\mathbf{U}} $$ ʅ are constructed. It is shown that $$ \overset{.}{\mathbf{U}} $$ ʅ is a subquotient of $$ \overset{.}{\mathbf{U}} $$ ℐ with compatible canonical bases. Moreover, a compatibility between canonical bases for modified coideal algebras and Schur algebras is established.
Effect of the thickness on the fracturing behavior of discontinuous fiber composite structures

Abstract In this study, we investigate experimentally and numerically the mode I intra-laminar fracture and size effect of Discontinuous Fiber Composites (DFCs) as a function of the structure thickness. Fracture tests on geometrically-scaled Single Edge Notch Tension (SENT) specimens show a notable size effect on the nominal strength of DFCs. By integrating equivalent fracture mechanics and stochastic finite element modeling we estimate, for the first time, the fracture energy and the effective size of the Fracture Process Zone (FPZ) as a function of the thickness of the DFC structure. From the integrated analysis, it is found that the fracture energy depends significantly on the structure thickness. It is shown to increase gradually with increasing thickness, t, and to saturate for t ⩾ 3 mm to a value of 57.77 N/mm, which is 4.81 times larger than a typical aluminum alloy. For thicknesses lower than 1.1 mm, corresponding to an average number of platelets through the thickness of roughly 8, it was found that the fracturing process can often be triggered by weak spots in the structure rather than the stress-free notch.
Implementing a concept network model

The same concept can mean different things or be instantiated in different forms, depending on context, suggesting a degree of flexibility within the conceptual system. We propose that a feature-based network model can be used to capture and predict this flexibility. We modeled individual concepts (e.g., BANANA, BOTTLE) as graph-theoretical networks, in which properties (e.g., YELLOW, SWEET) were represented as nodes and their associations as edges. In this framework, networks capture within-concept statistics that reflect how properties relate to one another across instances of a concept. We extracted formal measures of these networks that capture different aspects of network structure, and explored whether a concept's network structure relates to its flexibility of use. To do so, we compared network measures to a text-based measure of semantic diversity, as well as to empirical data from a figurative-language task and an alternative-uses task. We found that network-based measures were predictive of the text-based and empirical measures of flexible concept use, highlighting the ability of this approach to formally capture relevant characteristics of conceptual structure. Conceptual flexibility is a fundamental attribute of the cognitive and semantic systems, and in this proof of concept we reveal that variations in concept representation and use can be formally understood in terms of the informational content and topology of concept networks.
Strongly Secure and Efficient Data Shuffle on Hardware Enclaves

Mitigating memory-access attacks on the Intel SGX architecture is an important and open research problem. A natural notion of the mitigation is cache-miss obliviousness which requires the cache-misses emitted during an enclave execution are oblivious to sensitive data. This work realizes the cache-miss obliviousness for the computation of data shuffling. The proposed approach is to software-engineer the oblivious algorithm of Melbourne shuffle [22] on the Intel SGX/TSX architecture, where the Transaction Synchronization eXtension (TSX) is (ab)used to detect the occurrence of cache misses. In the system building, we propose software techniques to prefetch memory data prior to the TSX transaction to defend the physical bus-tapping attacks. Our evaluation based on real implementation shows that our system achieves superior performance and lower transaction abort rate than the related work in the existing literature.
An evasion and counter-evasion study in malicious websites detection

Malicious websites are a major cyber attack vector, and effective detection of them is an important cyber defense task. The main defense paradigm in this regard is that the defender uses some kind of machine learning algorithms to train a detection model, which is then used to classify websites in question. Unlike other settings, the following issue is inherent to the problem of malicious websites detection: the attacker essentially has access to the same data that the defender uses to train his/her detection models. This ‘symmetry’ can be exploited by the attacker, at least in principle, to evade the defender’s detection models. In this paper, we present a framework for characterizing the evasion and counter-evasion interactions between the attacker and the defender, where the attacker attempts to evade the defender’s detection models by taking advantage of this symmetry. Within this framework, we show that an adaptive attacker can make malicious websites evade powerful detection models, but proactive training can be an effective counter-evasion defense mechanism. The framework is geared toward the popular detection model of decision tree, but can be adapted to accommodate other classifiers.
Modulational Instability in the Whitham Equation for Water Waves

We show that periodic traveling waves with sufficiently small amplitudes of the Whitham equation, which incorporates the dispersion relation of surface water waves and the nonlinearity of the shallow water equations, are spectrally unstable to long-wavelengths perturbations if the wave number is greater than a critical value, bearing out the Benjamin–Feir instability of Stokes waves; they are spectrally stable to square integrable perturbations otherwise. The proof involves a spectral perturbation of the associated linearized operator with respect to the Floquet exponent and the small-amplitude parameter. We extend the result to related, nonlinear dispersive equations.
Whole Genome Sequencing: Innovation Dream or Privacy Nightmare?

Over the past several years, DNA sequencing has emerged as one of the driving forces in life-sciences, paving the way for affordable and accurate whole genome sequencing. As genomes represent the entirety of an organism’s hereditary information, the availability of complete human genomes prompts a wide range of revolutionary applications. The hope for improving modern healthcare and better understanding the human genome propels many interesting and challenging research frontiers. Unfortunately, however, the proliferation of human genomes amplifies worrisome privacy concerns, since a genome represents a treasure trove of highly personal and sensitive information. In this article, we provide an overview of positive results and biomedical advances in the field, and discuss privacy issues associated with human genomic information. Finally, we survey available privacy-enhancing technologies and list a number of open research challenges.
In Search of Exomoons

Two decades ago, astronomers began detecting planets orbiting stars other than our Sun, so-called exoplanets. Since that time, the rate of detections and the sensitivity to ever-smaller planets has improved dramatically with several Earth-sized planets now known. As our sensitivity dives into the terrestrial regime, increasingly the community has wondered if the moons of exoplanets may also be detectable, so-called “exomoons”. Their detection represents an outstanding challenge in modern astronomy and would provide deep insights into the uniqueness of our Solar System and perhaps even expand the definition of habitability. Here, I will briefly review theoretical studies exploring the formation and evolution of exomoons, which serve to guide observational searches and provide testable hypotheses. Next, I will outline the different methods which have been proposed to accomplish this challenging feat and their respective merits. Finally, initial results from observational efforts will be summarized with a view to future prospects as well.
A random flight process associated to a Lorentz gas with variable density in a gravitational field

Abstract We investigate a random flight process approximation to a random scatterer Lorentz gas with variable scatterer density in a gravitational field. For power function densities we show how the parameters of the model determine recurrence or transience of the vertical component of the trajectory. Finally, our methods show that, with appropriate scaling of space, time and the density of obstacles, the trajectory of the particle converges to a diffusion with explicitly given parameters.
Information Theoretic Learning with Infinitely Divisible Kernels

Abstract: In this paper, we develop a framework for information theoretic learning based on infinitely divisible matrices. We formulate an entropy-like functional on positive definite matrices based on Renyi's axiomatic definition of entropy and examine some key properties of this functional that lead to the concept of infinite divisibility. The proposed formulation avoids the plug in estimation of density and brings along the representation power of reproducing kernel Hilbert spaces. As an application example, we derive a supervised metric learning algorithm using a matrix based analogue to conditional entropy achieving results comparable with the state of the art.
Distributed Coordination of DERs With Storage for Dynamic Economic Dispatch

This paper considers the dynamic economic dispatch problem for a group of distributed energy resources (DERs) with storage that communicate over a weight-balanced strongly connected digraph. The objective is to collectively meet a certain load profile over a finite time horizon while minimizing the aggregate cost. At each time slot, each DER decides on the amount of generated power, the amount sent to/drawn from the storage unit, and the amount injected into the grid to satisfy the load. Additional constraints include bounds on the amount of generated power, ramp constraints on the difference in generation across successive time slots, and bounds on the amount of power in storage. We synthesize a provably correct distributed algorithm that solves the resulting finite-horizon optimization problem starting from any initial condition. Our design consists of two interconnected systems, one estimating the mismatch between the injection and the total load at each time slot, and another using this estimate to reduce the mismatch and optimize the total cost of generation while meeting the constraints.
Measuring Sample Quality with Kernels

Approximate Markov chain Monte Carlo (MCMC) offers the promise of more rapid sampling at the cost of more biased inference. Since standard MCMC diagnostics fail to detect these biases, researchers have developed computable Stein discrepancy measures that provably determine the convergence of a sample to its target distribution. This approach was recently combined with the theory of reproducing kernels to define a closed-form kernel Stein discrepancy (KSD) computable by summing kernel evaluations across pairs of sample points. We develop a theory of weak convergence for KSDs based on Stein’s method, demonstrate that commonly used KSDs fail to detect non-convergence even for Gaussian targets, and show that kernels with slowly decaying tails provably determine convergence for a large class of target distributions. The resulting convergence-determining KSDs are suitable for comparing biased, exact, and deterministic sample sequences and simpler to compute and parallelize than alternative Stein discrepancies. We use our tools to compare biased samplers, select sampler hyperparameters, and improve upon existing KSD approaches to one-sample hypothesis testing and sample quality improvement.
Comparing numerical dimensions

The numerical dimension is a numerical measure of the positivity of a pseudoeffective divisor L. There are several proposed definitions of the numerical dimension due to Nakayama and Boucksom et al. We prove the equality of these notions and give several additional characterizations. We also prove some new properties of the numerical dimension.
Detecting change points in the large-scale structure of evolving networks

Interactions among people or objects are often dynamic in nature and can be represented as a sequence of networks, each providing a snapshot of the interactions over a brief period of time. An important task in analyzing such evolving networks is change-point detection, in which we both identify the times at which the large-scale pattern of interactions changes fundamentally and quantify how large and what kind of change occurred. Here, we formalize for the first time the network change-point detection problem within an online probabilistic learning framework and introduce a method that can reliably solve it. This method combines a generalized hierarchical random graph model with a Bayesian hypothesis test to quantitatively determine if, when, and precisely how a change point has occurred. We analyze the detectability of our method using synthetic data with known change points of different types and magnitudes, and show that this method is more accurate than several previously used alternatives. Applied to two high-resolution evolving social networks, this method identifies a sequence of change points that align with known external "shocks" to these networks.
Automorphism groups of N=2 superconformal super-Riemann spheres

We determine the automorphism groups for the countably infinite family of N=2 superconformal equivalence classes of DeWitt N=2 superconformal super-Riemann surfaces with closed, genus-zero body. We then analyze the Lie structure of these groups. Under the correspondence between N=2 superconformal and N=1 superanalytic structures, the results extend to the determination of automorphism groups of N=1 superanalytic DeWitt super-Riemann surfaces with closed, genus-zero body.
The long-term effects of childhood exposure to the earned income tax credit on health outcomes

Abstract The Earned Income Tax Credit (EITC) is a central component of the U.S. safety net, benefiting about 25 million families. Using variation in the federal and state EITC, this paper evaluates the long-term impact of EITC exposure during childhood on the health of young adults. We find that an additional $100, or a 3% increase, in the average annual EITC exposure between birth and age 18 increases the likelihood of reporting very good or excellent health by 2.6% and decreases the likelihood of being obese by 4.1% between ages 22 and 27. The effects of EITC exposure are stronger for children raised in a single-parent household and for children with lower-educated parents.
Multi-Resolution Data Fusion for Super-Resolution Electron Microscopy

Perhaps surprisingly, all electron microscopy (EM) data collected to date is less than a cubic millimeter – presenting a huge demand in the materials and biological sciences to image at greater speed and lower dosage, while maintaining resolution. Traditional EM imaging based on homogeneous raster scanning severely limits the volume of high-resolution data that can be collected, and presents a fundamental limitation to understanding physical processes such as material deformation and crack propagation.,,,,,, We introduce a multi-resolution data fusion (MDF) method for super-resolution computational EM. Our method combines innovative data acquisition with novel algorithmic techniques to dramatically improve the resolution/ volume/speed trade-off. The key to our approach is to collect the entire sample at low resolution, while simultaneously collecting a small fraction of data at high resolution. The high-resolution measurements are then used to create a material-specific model that is used within the “plug-andplay” framework to dramatically improve resolution of the low-resolution data. We present results using FEI electron microscope data that demonstrate super-resolution factors of 4x-16x, while substantially maintaining high image quality and reducing dosage.
Throughput Analysis for Full-Duplex Wireless Networks With Imperfect Self-Interference Cancellation

This paper investigates the throughput for wireless network with full-duplex radios using stochastic geometry. Full-duplex (FD) radios can exchange data simultaneously with each other. On the other hand, the downside of FD transmission is that it will inevitably cause extra interference to the network compared to half-duplex (HD) transmission. Moreover, the residual self-interference has negative effects on the network throughput. In this paper, we focus on a wireless network of nodes with both HD and FD capabilities and derive and optimize the throughput in such a network. Our analytical result shows that if the network is adopting an ALOHA protocol, the maximal throughput is achieved by scheduling all concurrently transmitting nodes to work in either FD mode or HD mode depending on one simple condition. Moreover, the effects of imperfect self-interference cancellation on the signal-to-interference ratio (SIR) loss and throughput are also analyzed based on our mathematical model. We rigorously quantify the impact of imperfect self-interference cancellation on the throughput gain, transmission range, and other metrics, and we establish the minimum amount of self-interference suppression needed for FD to be beneficial.
A generalization of Aztec diamond theorem, part II

The author gave a proof of a generalization of the Aztec diamond theorem for a family of 4-vertex regions on the square lattice with southwest-to-northeast diagonals drawn in Lai (2014) by using a bijection between tilings and non-intersecting lattice paths. In this paper, we use Kuo graphical condensation to give a new proof.
HEAT KERNEL EXPANSIONS, AMBIENT METRICS AND CONFORMAL INVARIANTS

Abstract The conformal powers of the Laplacian of a Riemannian metric which are known as the GJMS-operators admit a combinatorial description in terms of the Taylor coefficients of a natural second-order one-parameter family H ( r ; g ) of self-adjoint elliptic differential operators. H ( r ; g ) is a non-Laplace-type perturbation of the conformal Laplacian P 2 ( g ) = H ( 0 ; g ) . It is defined in terms of the metric g and covariant derivatives of the curvature of g. We study the heat kernel coefficients a 2 k ( r ; g ) of H ( r ; g ) on closed manifolds. We prove general structural results for the heat kernel coefficients a 2 k ( r ; g ) and derive explicit formulas for a 0 ( r ; g ) and a 2 ( r ; g ) in terms of renormalized volume coefficients. The Taylor coefficients of a 2 k ( r ; g ) (as functions of r) interpolate between the renormalized volume coefficients of a metric g ( k = 0 ) and the heat kernel coefficients of the conformal Laplacian of g ( r = 0 ). Although H ( r ; g ) is not conformally covariant, there is a beautiful formula for the conformal variation of the trace of its heat kernel. Its proof rests on the combinatorial relations between Taylor coefficients of H ( r ; g ) and GJMS-operators. As a consequence, we give a heat equation proof of the conformal transformation law of the integrated renormalized volume coefficients. By refining these arguments, we also give a heat equation proof of the conformal transformation law of the renormalized volume coefficients itself. The Taylor coefficients of a 2 ( r ) define a sequence of higher-order Riemannian curvature functionals with extremal properties at Einstein metrics which are analogous to those of integrated renormalized volume coefficients. Among the various additional results the reader finds a Polyakov-type formula for the renormalized volume of a Poincare–Einstein metric in terms of Q-curvature of its conformal infinity and additional holographic terms. The present study of relations between spectral theoretic heat kernel coefficients and geometric quantities like renormalized volume coefficients is stimulated by the holographic perspective of the AdS/CFT-duality (proposing relations between functional determinants and renormalized volumes).
Hodge Structures of Type (n, 0, …, 0, n)

Hodge structures of type (n, 0, . . . , 0, n) Burt Totaro Completing earlier work by Albert, Shimura found all the possible endomor- phism algebras (tensored with the rationals) for complex abelian varieties of a given dimension [12, Theorem 5]. In five exceptional cases, every abelian variety on which a certain algebra acts has “extra endomorphisms”, so that the full endomorphism algebra is bigger than expected. Complex abelian varieties X up to isogeny are equivalent to polarizable Q-Hodge structures of weight 1, with Hodge numbers (n, n) (where n is the dimension of X). In this paper, we generalize Shimura’s classification to determine all the possible endomorphism algebras for polarizable Q-Hodge structures with Hodge numbers (n, 0, . . . , 0, n). For Hodge structures of odd weight, the answer is the same as for abelian varieties. For Hodge structures of even weight, the answer is similar but not identical. The proof combines ideas from Shimura with Green-Griffiths-Kerr’s approach to computing Mumford-Tate groups [4, Proposition VI.A.5]. As with abelian varieties, the most interesting feature of the classification is that in certain cases, every Hodge structure on which a given algebra acts must have extra endomorphisms. (Throughout this discussion, we only consider polarizable Hodge structures.) One known case (pointed out to me by Beauville) is that every Q- Hodge structure with Hodge numbers (1, 0, 1) has endomorphisms by an imaginary quadratic field and hence is of complex multiplication (CM) type, meaning that its Mumford-Tate group is commutative. More generally, every Q-Hodge structure with Hodge numbers (n, 0, n) that has endomorphisms by a totally real field F of degree n has endomorphisms by a totally imaginary quadratic extension field of F , and hence is of CM type. Another case, which seems to be new, is that a Q-Hodge structure V with Hodge numbers (2, 0, 2) that has endomorphisms by an imaginary quadratic field F 0 must have endomorphisms by a quaternion algebra over Q. In this case, V need not be of CM type; there is a period space isomorphic to CP 1 of Hodge structures of this type, whereas there are only countably many Hodge structures of CM type. To motivate the results of this paper on endomorphism algebras, consider the geometric origin of Hodge structures. A Hodge structure comes from geometry if it is a summand of the cohomology of a smooth complex projective variety defined by an algebraic correspondence. Griffiths found (“Griffiths transversality”) that a family of Hodge structures coming from geometry can vary only in certain directions, expressed by the notion of a variation of Hodge structures [15, Theorem 10.2]. In particular, any variation of Hodge structures of weight at least 2 with Hodge numbers (n, 0, . . . , 0, n) (so there is at least one 0) is locally constant; more generally, this holds whenever there are no two adjacent nonzero Hodge numbers. This has the remarkable consequence that only countably many Hodge structures of weight at least 2 with Hodge numbers (n, 0, . . . , 0, n) come from geometry. Very little is
j-MULTIPLICITY AND DEPTH OF ASSOCIATED GRADED MODULES

Abstract Let R be a Noetherian local ring. We define the minimal j-multiplicity and almost minimal j-multiplicity of an arbitrary R-ideal on any finite R-module. For any ideal I with minimal j-multiplicity or almost minimal j-multiplicity on a Cohen–Macaulay module M, we prove that under some residual conditions, the associated graded module gr I ( M ) is Cohen–Macaulay or almost Cohen–Macaulay, respectively. Our work generalizes the results for minimal multiplicity and almost minimal multiplicity obtained by Sally, Rossi, Valla, Wang, Huckaba, Elias, Corso, Polini, and Vaz Pinto.
Successive local and successive global omniscience

This paper considers two generalizations of the cooperative data exchange problem, referred to as the successive local omniscience (SLO) and the successive global omniscience (SGO). The users are divided into l nested sub-groups. Each user initially knows a subset of packets in a ground set X of size k, and all users wish to learn all packets in X. The users exchange their packets by broadcasting coded or uncoded packets. In SLO or SGO, in the lth (1≤ l ≤ l) round of transmissions, the lth smallest ub-group of users need to learn all packets they collectively hold or all packets in X, respectively. The problem is to find the minimum sum-rate (i.e., the total transmission rate by all users) for each round, subject to minimizing the sum-rate for the previous round. To solve this problem, we use a linear-programming approach. For the cases in which the packets are randomly distributed among users, we construct a system of linear equations whose solution characterizes the minimum sum-rate for each round with high probability as k tends to infinity. Moreover, for the special case of two nested groups, we derive closed-form expressions, which hold with high probability as k tends to infinity, for the minimum sum-rate for each round.
Collaboratively learning preferences from ordinal data

In personalized recommendation systems, it is important to predict preferences of a user on items that have not been seen by that user yet. Similarly, in revenue management, it is important to predict outcomes of comparisons among those items that have never been compared so far. The MultiNomial Logit model, a popular discrete choice model, captures the structure of the hidden preferences with a low-rank matrix. In order to predict the preferences, we want to learn the underlying model from noisy observations of the low-rank matrix, collected as revealed preferences in various forms of ordinal data. A natural approach to learn such a model is to solve a convex relaxation of nuclear norm minimization. We present the convex relaxation approach in two contexts of interest: collaborative ranking and bundled choice modeling. In both cases, we show that the convex relaxation is minimax optimal. We prove an upper bound on the resulting error with finite samples, and provide a matching information-theoretic lower bound.
Combinatorial Assortment Optimization

Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a choice model in which each consumer selects a utility-maximizing bundle subject to a private valuation function, and study the complexity of the resulting optimization problem. Our main result is an exact algorithm for additive k-demand valuations, under a model of vertical differentiation in which customers agree on the relative value of each pair of items but differ in their absolute willingness to pay. For valuations that are vertically differentiated but not necessarily additive k-demand, we show how to obtain constant approximations under a “well-priced” condition, where each product’s price is sufficiently high. We further show that even for a single customer with known valuation, any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS and that no FPTAS exists even when the valuation is succinctly representable.
On the Identifiability of Diagnostic Classification Models

This paper establishes fundamental results for statistical analysis based on diagnostic classification models (DCMs). The results are developed at a high level of generality and are applicable to essentially all diagnostic classification models. In particular, we establish identifiability results for various modeling parameters, notably item response probabilities, attribute distribution, and Q-matrix-induced partial information structure. These results are stated under a general setting of latent class models. Through a nonparametric Bayes approach, we construct an estimator that can be shown to be consistent when the identifiability conditions are satisfied. Simulation results show that these estimators perform well under various model settings. We also apply the proposed method to a dataset from the National Epidemiological Survey on Alcohol and Related Conditions (NESARC).
The pop-switch planar algebra and the Jones–Wenzl idempotents

The Jones–Wenzl idempotents are elements of the Temperley–Lieb (TL) planar algebra that are important, but complicated to write down. We will present a new planar algebra, the pop-switch planar algebra (PSPA), which contains the TL planar algebra. It is motivated by Jones' idea of the graph planar algebra (GPA) of type An. In the tensor category of idempotents of the PSPA, the nth Jones–Wenzl idempotent is isomorphic to a direct sum of n + 1 diagrams consisting of only vertical strands.
Meyers inequality and strong stability for stable-like operators

Let α∈(0,2), let E(u,u)=∫Rd∫Rd(u(y)−u(x))2A(x,y)|x−y|d+αdydx be the Dirichlet form for a stable-like operator, let Γu(x)=(∫Rd(u(y)−u(x))2A(x,y)|x−y|d+αdy)1/2, let L be the associated infinitesimal generator, and suppose A(x,y) is jointly measurable, symmetric, bounded, and bounded below by a positive constant. We prove that if u is the weak solution to Lu=h, then Γu∈Lp for some p>2. This is the analogue of an inequality of Meyers for solutions to divergence form elliptic equations. As an application, we prove strong stability results for stable-like operators. If A is perturbed slightly, we give explicit bounds on how much the semigroup and fundamental solution are perturbed.
Automatic Analysis of EEGs Using Big Data and Hybrid Deep Learning Architectures

Brain monitoring combined with automatic analysis of EEGs provides a clinical decision support tool that can reduce time to diagnosis and assist clinicians in real-time monitoring applications (e.g., neurological intensive care units). Clinicians have indicated that a sensitivity of 95% with specificity below 5% was the minimum requirement for clinical acceptance. In this study, a high-performance automated EEG analysis system based on principles of machine learning and big data is proposed. This hybrid architecture integrates hidden Markov models (HMMs) for sequential decoding of EEG events with deep learning-based post-processing that incorporates temporal and spatial context. These algorithms are trained and evaluated using the Temple University Hospital EEG, which is the largest publicly available corpus of clinical EEG recordings in the world. This system automatically processes EEG records and classifies three patterns of clinical interest in brain activity that might be useful in diagnosing brain disorders: (1) spike and/or sharp waves, (2) generalized periodic epileptiform discharges, (3) periodic lateralized epileptiform discharges. It also classifies three patterns used to model the background EEG activity: (1) eye movement, (2) artifacts, and (3) background. Our approach delivers a sensitivity above 90% while maintaining a specificity below 5%. We also demonstrate that this system delivers a low false alarm rate, which is critical for any spike detection application.
A graph-embedded deep feedforward network for disease outcome classification and feature selection using gene expression data

Motivation Gene expression data represents a unique challenge in predictive model building, because of the small number of samples (n) compared with the huge amount of features (p). This 'n≪p' property has hampered application of deep learning techniques for disease outcome classification. Sparse learning by incorporating external gene network information could be a potential solution to this issue. Still, the problem is very challenging because (i) there are tens of thousands of features and only hundreds of training samples, (ii) the scale-free structure of the gene network is unfriendly to the setup of convolutional neural networks. Results To address these issues and build a robust classification model, we propose the Graph-Embedded Deep Feedforward Networks (GEDFN), to integrate external relational information of features into the deep neural network architecture. The method is able to achieve sparse connection between network layers to prevent overfitting. To validate the method's capability, we conducted both simulation experiments and real data analysis using a breast invasive carcinoma RNA-seq dataset and a kidney renal clear cell carcinoma RNA-seq dataset from The Cancer Genome Atlas. The resulting high classification accuracy and easily interpretable feature selection results suggest the method is a useful addition to the current graph-guided classification models and feature selection procedures. Availability and implementation The method is available at https://github.com/yunchuankong/GEDFN. Supplementary information Supplementary data are available at Bioinformatics online.
Benchmarking the Capabilities and Limitations of SAT Solvers in Defeating Obfuscation Schemes

In this paper, we investigate the strength of six different SAT solvers in attacking various obfuscation schemes. Our investigation revealed that Glucose and Lingeling SAT solvers are generally suited for attacking small-to-midsize obfuscated circuits, while the MapleGlucose, if the system is not memory bound, is best suited for attacking mid-to-difficult obfuscation methods. Our experimental result indicates that when dealing with extremely large circuits and very difficult oufuscation problems, the SAT solver may be memory bound, and Lingeling, for having the most memory efficient implementation, is the best suited solver for such problems. Additionally, our investigation revealed that SAT solver execution times may vary widely across different SAT solvers. Hence, when testing the hardness of an obfuscation methods, although the increase in difficulty could be verified by one SAT solver, the pace of increase in difficulty is dependent on the choice of a SAT solver.
On Strong Cosmic Censorship

For almost half of the one hundred year history of Einstein’s theory of general relativity, Strong Cosmic Censorship has been one of its most intriguing conjectures. The SCC conjecture addresses the issue of the nature of the singularities found in most solutions of Einstein’s gravitational field equations: Are such singularities generically characterized by unbounded curvature? Is the existence of a Cauchy horizon (and the accompanying extensions into spacetime regions in which determinism fails) an unstable feature of solutions of Einstein’s equations? In this short review article, after briefly commenting on the history of the SCC conjecture, we survey some of the progress made in research directed either toward supporting SCC or toward uncovering some of its weaknesses. We focus in particular on model versions of SCC which have been proven for restricted families of spacetimes (e.g., the Gowdy spacetimes), and the role played by the generic presence of Asymptotically Velocity Term Dominated behavior in these solutions. We also note recent work on spacetimes containing weak null singularities, and their relevance for the SCC conjecture.
The Road to Serfdom after 75 Years

This paper revisits Friedrich Hayek's book, The Road to Serfdom, on the seventy-fifth anniversary of its publication. Though the book is well-known, its arguments are often mischaracterized. The paper traces the origins of the book, noting the various people and arguments that Hayek was responding to, and places it in the context of its times. The structure of the book is explored and some common criticisms addressed. Finally, it is shown how, after its publication, the book took on a life of its own.
Online Risk-Bounded Motion Planning for Autonomous Vehicles in Dynamic Environments.

A crucial challenge to efficient and robust motion planning for autonomous vehicles is understanding the intentions of the surrounding agents. Ignoring the intentions of the other agents in dynamic environments can lead to risky or overconservative plans. In this work, we model the motion planning problem as a partially observable Markov decision process (POMDP) and propose an online system that combines an intent recognition algorithm and a POMDP solver to generate risk-bounded plans for the ego vehicle navigating with a number of dynamic agent vehicles. The intent recognition algorithm predicts the probabilistic hybrid motion states of each agent vehicle over a finite horizon using Bayesian filtering and a library of pre-learned maneuver motion models. We update the POMDP model with the intent recognition results in real time and solve it using a heuristic search algorithm which produces policies with upper-bound guarantees on the probability of near colliding with other dynamic agents. We demonstrate that our system is able to generate better motion plans in terms of efficiency and safety in a number of challenging environments including unprotected intersection left turns and lane changes as compared to the baseline methods.
Planning with State Abstractions for Non-Markovian Task Specifications

Often times, we specify tasks for a robot using temporal language that can also span different levels of abstraction. The example command ``go to the kitchen before going to the second floor'' contains spatial abstraction, given that ``floor'' consists of individual rooms that can also be referred to in isolation ("kitchen", for example). There is also a temporal ordering of events, defined by the word "before". Previous works have used Linear Temporal Logic (LTL) to interpret temporal language (such as "before"), and Abstract Markov Decision Processes (AMDPs) to interpret hierarchical abstractions (such as "kitchen" and "second floor"), separately. To handle both types of commands at once, we introduce the Abstract Product Markov Decision Process (AP-MDP), a novel approach capable of representing non-Markovian reward functions at different levels of abstractions. The AP-MDP framework translates LTL into its corresponding automata, creates a product Markov Decision Process (MDP) of the LTL specification and the environment MDP, and decomposes the problem into subproblems to enable efficient planning with abstractions. AP-MDP performs faster than a non-hierarchical method of solving LTL problems in over 95% of tasks, and this number only increases as the size of the environment domain increases. We also present a neural sequence-to-sequence model trained to translate language commands into LTL expression, and a new corpus of non-Markovian language commands spanning different levels of abstraction. We test our framework with the collected language commands on a drone, demonstrating that our approach enables a robot to efficiently solve temporal commands at different levels of abstraction.
On matchable subsets in abelian groups and their linear analogues

Abstract In this paper, we introduce the notions of matching matrices in groups and vector spaces, which lead to some necessary conditions for existence of acyclic matching in abelian groups and its linear analogue. We also study the linear local matching property in field extensions to find a dimension criterion for linear locally matchable bases. Moreover, we define the weakly locally matchable subspaces and we investigate their relations with matchable subspaces. We provide an upper bound for the dimension of primitive subspaces in a separable field extension. We employ MATLAB coding to investigate the existence of acyclic matchings in finite cyclic groups. Finally, a possible research problem on matchings in n-groups is presented. Our tools in this paper mix combinatorics and linear algebra.
Variance Reduction for Matrix Games

We present a randomized primal-dual algorithm that solves the problem min_x max_y y^T A x to additive error epsilon in time nnz(A) + sqrt{nnz(A) n} / epsilon, for matrix A with larger dimension n and nnz(A) nonzero entries. This improves the best known exact gradient methods by a factor of sqrt{nnz(A) / n} and is faster than fully stochastic gradient methods in the accurate and/or sparse regime epsilon < sqrt{n / nnz(A)$. Our results hold for x,y in the simplex (matrix games, linear programming) and for x in an \ell_2 ball and y in the simplex (perceptron / SVM, minimum enclosing ball). Our algorithm combines the Nemirovski's "conceptual prox-method" and a novel reduced-variance gradient estimator based on "sampling from the difference" between the current iterate and a reference point.
An approach to automatic maintenance of semantic integrity in large design data bases

One way a data base can cease retaining a meaningful relationship with the "real world" situation that it models is through violations of its semantic integrity , i.e., transgressions of the defining constraints of its data. These constraints state the legality of the data values and are defined by the creators of the data, e.g., a checking account cannot be negative, or the salary of an assistant professor cannot be greater than that of a full professor.
PRNet: Self-Supervised Learning for Partial-to-Partial Registration

We present a simple, flexible, and general framework titled Partial Registration Network (PRNet), for partial-to-partial point cloud registration. Inspired by recently-proposed learning-based methods for registration, we use deep networks to tackle non-convexity of the alignment and partial correspondence problem. While previous learning-based methods assume the entire shape is visible, PRNet is suitable for partial-to-partial registration, outperforming PointNetLK, DCP, and non-learning methods on synthetic data. PRNet is self-supervised, jointly learning an appropriate geometric representation, a keypoint detector that finds points in common between partial views, and keypoint-to-keypoint correspondences. We show PRNet predicts keypoints and correspondences consistently across views and objects. Furthermore, the learned representation is transferable to classification.
Principles and techniques of the quantum diamond microscope

We provide an overview of the experimental techniques, measurement modalities, and diverse applications of the Quantum Diamond Microscope (QDM). The QDM employs a dense layer of fluorescent nitrogen-vacancy (NV) color centers near the surface of a transparent diamond chip on which a sample of interest is placed. NV electronic spins are coherently probed with microwaves and optically initialized and read out to provide spatially resolved maps of local magnetic fields. NV fluorescence is measured simultaneously across the diamond surface, resulting in a wide-field, two-dimensional magnetic field image with adjustable spatial pixel size set by the parameters of the imaging system. NV measurement protocols are tailored for imaging of broadband and narrowband fields, from DC to GHz frequencies. Here we summarize the physical principles common to diverse implementations of the QDM and review example applications of the technology in geoscience, biology, and materials science.
Bifunctional Small-Molecule Ligands of K-Ras Induce Its Association with Immunophilin Proteins.

Here we report the design, synthesis, and characterization of bifunctional chemical ligands that induce the association of Ras with ubiquitously expressed immunophilin proteins such as FKBP12 and cyclophilin A. We show this approach is applicable to two distinct Ras ligand scaffolds, and that both the identity of the immunophilin ligand and the linker chemistry affect compound efficacy in biochemical and cellular contexts. These ligands bind to Ras in an immunophilin-dependent fashion and mediate the formation of tripartite complexes of Ras, immunophilin, and the ligand. The recruitment of cyclophilin A to GTP-bound Ras blocks its interaction with B-Raf in biochemical assays. Our study demonstrates the feasibility of ligand-induced association of Ras with intracellular proteins and suggests it as a promising therapeutic strategy for Ras-driven cancers.