Recently proposed as a stable means of evaluating geometric compactness, the
- Award ID(s):
- 1838071
- PAR ID:
- 10430695
- Publisher / Repository:
- Wiley-Blackwell
- Date Published:
- Journal Name:
- Computer Graphics Forum
- Volume:
- 39
- Issue:
- 5
- ISSN:
- 0167-7055
- Page Range / eLocation ID:
- p. 1-13
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Tauman_Kalai, Yael (Ed.)We show improved monotonicity testers for the Boolean hypercube under the p-biased measure, as well as over the hypergrid [m]ⁿ. Our results are: 1) For any p ∈ (0,1), for the p-biased hypercube we show a non-adaptive tester that makes Õ(√n/ε²) queries, accepts monotone functions with probability 1 and rejects functions that are ε-far from monotone with probability at least 2/3. 2) For all m ∈ ℕ, we show an Õ(√nm³/ε²) query monotonicity tester over [m]ⁿ. We also establish corresponding directed isoperimetric inequalities in these domains, analogous to the isoperimetric inequality in [Subhash Khot et al., 2018]. Previously, the best known tester due to Black, Chakrabarty and Seshadhri [Hadley Black et al., 2018] had Ω(n^{5/6}) query complexity. Our results are optimal up to poly-logarithmic factors and the dependency on m. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension n into a function over a Boolean cube of a larger dimension n', while preserving its distance from being monotone; an embedding is considered efficient if n' is not much larger than n, and we show how to construct efficient embeddings in the above mentioned settings.more » « less
-
Abstract Estimates of population characteristics such as domain means are often expected to follow monotonicity assumptions. Recently, a method to adaptively pool neighbouring domains was proposed, which ensures that the resulting domain mean estimates follow monotone constraints. The method leads to asymptotically valid estimation and inference, and can lead to substantial improvements in efficiency, in comparison with unconstrained domain estimators. However, assuming incorrect shape constraints may lead to biased estimators. Here, we develop the Cone Information Criterion for Survey Data as a diagnostic method to measure monotonicity departures on population domain means. We show that the criterion leads to a consistent methodology that makes an asymptotically correct decision choosing between unconstrained and constrained domain mean estimators.
The Canadian Journal of Statistics 47: 315–331; 2019 © 2019 Statistical Society of Canada -
Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)We propose precise notions of what it means to guard a domain "robustly", under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees.more » « less
-
Abstract In this work, we consider the nonlinear Schrödinger equation (NLSE) in 2+1 dimensions with arbitrary nonlinearity exponent
κ in the presence of an external confining potential. Exact solutions to the system are constructed, and their stability as we increase the ‘mass’ (i.e., theL 2norm) and the nonlinearity parameterκ is explored. We observe both theoretically and numerically that the presence of the confining potential leads to wider domains of stability over the parameter space compared to the unconfined case. Our analysis suggests the existence of a stable regime of solutions for allκ as long as their mass is less than a critical valueM *(κ ). Furthermore, we find that there are two different critical masses, one corresponding to width perturbations and the other one to translational perturbations. The results of Derrick’s theorem are also obtained by studying the small amplitude regime of a four-parameter collective coordinate (4CC) approximation. A numerical stability analysis of the NLSE shows that the instability curveM *(κ )versus κ lies below the two curves found by Derrick’s theorem and the 4CC approximation. In the absence of the external potential,κ = 1 demarcates the separation between the blowup regime and the stable regime. In this 4CC approximation, forκ < 1, when the mass is above the critical mass for the translational instability, quite complicated motions of the collective coordinates are possible. Energy conservation prevents the blowup of the solution as well as confines the center of the solution to a finite spatial domain. We call this regime the ‘frustrated’ blowup regime and give some illustrations. In an appendix, we show how to extend these results to arbitrary initial ground state solution data and arbitrary spatial dimensiond . -
Shapley value provides a unique way to fairly assess each player's contribution in a coalition and has enjoyed many applications. However, the exact computation of Shapley value is #P-hard due to the combinatoric nature of Shapley value. Many existing applications of Shapley value are based on Monte-Carlo approximation, which requires a large number of samples and the assessment of utility on many coalitions to reach high quality approximation, and thus is still far from being efficient. Can we achieve an efficient approximation of Shapley value by smartly obtaining samples? In this paper, we treat the sampling approach to Shapley value approximation as a stratified sampling problem. Our main technical contributions are a novel stratification design and two sample allocation methods based on Neyman allocation and empirical Bernstein bound, respectively. Experimental results on several real data sets and synthetic data sets demonstrate the effectiveness and efficiency of our novel stratification design and sampling approaches.more » « less