@article{1617,
abstract = {We study the discrepancy of jittered sampling sets: such a set P⊂ [0,1]d is generated for fixed m∈ℕ by partitioning [0,1]d into md axis aligned cubes of equal measure and placing a random point inside each of the N=md cubes. We prove that, for N sufficiently large, 1/10 d/N1/2+1/2d ≤EDN∗(P)≤ √d(log N) 1/2/N1/2+1/2d, where the upper bound with an unspecified constant Cd was proven earlier by Beck. Our proof makes crucial use of the sharp Dvoretzky-Kiefer-Wolfowitz inequality and a suitably taylored Bernstein inequality; we have reasons to believe that the upper bound has the sharp scaling in N. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime N≳dd. We also prove a partition principle showing that every partition of [0,1]d combined with a jittered sampling construction gives rise to a set whose expected squared L2-discrepancy is smaller than that of purely random points.},
author = {Pausinger, Florian and Steinerberger, Stefan},
journal = {Journal of Complexity},
pages = {199 -- 216},
publisher = {Academic Press},
title = {{On the discrepancy of jittered sampling}},
doi = {10.1016/j.jco.2015.11.003},
volume = {33},
year = {2016},
}
@article{1641,
abstract = {The plant hormone auxin (indole-3-acetic acid) is a major regulator of plant growth and development including embryo and root patterning, lateral organ formation and growth responses to environmental stimuli. Auxin is directionally transported from cell to cell by the action of specific auxin influx [AUXIN-RESISTANT1 (AUX1)] and efflux [PIN-FORMED (PIN)] transport regulators, whose polar, subcellular localizations are aligned with the direction of the auxin flow. Auxin itself regulates its own transport by modulation of the expression and subcellular localization of the auxin transporters. Increased auxin levels promote the transcription of PIN2 and AUX1 genes as well as stabilize PIN proteins at the plasma membrane, whereas prolonged auxin exposure increases the turnover of PIN proteins and their degradation in the vacuole. In this study, we applied a forward genetic approach, to identify molecular components playing a role in the auxin-mediated degradation. We generated EMS-mutagenized Arabidopsis PIN2::PIN2:GFP, AUX1::AUX1:YFP eir1aux1 populations and designed a screen for mutants with persistently strong fluorescent signals of the tagged PIN2 and AUX1 after prolonged treatment with the synthetic auxin 2,4-dichlorophenoxyacetic acid (2,4-D). This approach yielded novel auxin degradation mutants defective in trafficking and degradation of PIN2 and AUX1 proteins and established a role for auxin-mediated degradation in plant development.},
author = {Zemová, Radka and Zwiewka, Marta and Bielach, Agnieszka and Robert, Hélène and Friml, Jirí},
journal = {Journal of Plant Growth Regulation},
number = {2},
pages = {465 -- 476},
publisher = {Springer},
title = {{A forward genetic screen for new regulators of auxin mediated degradation of auxin transport proteins in Arabidopsis thaliana}},
doi = {10.1007/s00344-015-9553-2},
volume = {35},
year = {2016},
}
@inproceedings{1653,
abstract = {A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest y = H hk (x) using a public hashing-key hk. Furthermore, there is a way to set up the hash key hk to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which hk is statistically binding from any other position i’. Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and y = H hk (x) it should be possible to create a short proof π that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO).
The prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption (FHE) and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions.},
author = {Okamoto, Tatsuaki and Pietrzak, Krzysztof Z and Waters, Brent and Wichs, Daniel},
location = {Auckland, New Zealand},
pages = {121 -- 145},
publisher = {Springer},
title = {{New realizations of somewhere statistically binding hashing and positional accumulators}},
doi = {10.1007/978-3-662-48797-6_6},
volume = {9452},
year = {2016},
}
@inproceedings{1225,
abstract = {At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme.},
author = {Fuchsbauer, Georg and Hanser, Christian and Kamath Hosdurg, Chethan and Slamanig, Daniel},
location = {Amalfi, Italy},
pages = {391 -- 408},
publisher = {Springer},
title = {{Practical round-optimal blind signatures in the standard model from weaker assumptions}},
doi = {10.1007/978-3-319-44618-9_21},
volume = {9841},
year = {2016},
}
@article{1662,
abstract = {We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.},
author = {Edelsbrunner, Herbert and Pausinger, Florian},
journal = {Advances in Mathematics},
pages = {674 -- 703},
publisher = {Academic Press},
title = {{Approximation and convergence of the intrinsic volume}},
doi = {10.1016/j.aim.2015.10.004},
volume = {287},
year = {2016},
}
@article{1705,
abstract = {Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential.},
author = {Bogomolov, Sergiy and Donzé, Alexandre and Frehse, Goran and Grosu, Radu and Johnson, Taylor and Ladan, Hamed and Podelski, Andreas and Wehrle, Martin},
journal = {International Journal on Software Tools for Technology Transfer},
number = {4},
pages = {449 -- 467},
publisher = {Springer},
title = {{Guided search for hybrid systems based on coarse-grained space abstractions}},
doi = {10.1007/s10009-015-0393-y},
volume = {18},
year = {2016},
}
@article{1833,
abstract = {Relational models for contingency tables are generalizations of log-linear models, allowing effects associated with arbitrary subsets of cells in the table, and not necessarily containing the overall effect, that is, a common parameter in every cell. Similarly to log-linear models, relational models can be extended to non-negative distributions, but the extension requires more complex methods. An extended relational model is defined as an algebraic variety, and it turns out to be the closure of the original model with respect to the Bregman divergence. In the extended relational model, the MLE of the cell parameters always exists and is unique, but some of its properties may be different from those of the MLE under log-linear models. The MLE can be computed using a generalized iterative scaling procedure based on Bregman projections. },
author = {Klimova, Anna and Rudas, Tamás},
journal = {Journal of Multivariate Analysis},
pages = {440 -- 452},
publisher = {Elsevier},
title = {{On the closure of relational models}},
doi = {10.1016/j.jmva.2015.10.005},
volume = {143},
year = {2016},
}
@article{1881,
abstract = {We consider random matrices of the form H=W+λV, λ∈ℝ+, where W is a real symmetric or complex Hermitian Wigner matrix of size N and V is a real bounded diagonal random matrix of size N with i.i.d.\ entries that are independent of W. We assume subexponential decay for the matrix entries of W and we choose λ∼1, so that the eigenvalues of W and λV are typically of the same order. Further, we assume that the density of the entries of V is supported on a single interval and is convex near the edges of its support. In this paper we prove that there is λ+∈ℝ+ such that the largest eigenvalues of H are in the limit of large N determined by the order statistics of V for λ>λ+. In particular, the largest eigenvalue of H has a Weibull distribution in the limit N→∞ if λ>λ+. Moreover, for N sufficiently large, we show that the eigenvectors associated to the largest eigenvalues are partially localized for λ>λ+, while they are completely delocalized for λ<λ+. Similar results hold for the lowest eigenvalues. },
author = {Lee, Jioon and Schnelli, Kevin},
journal = {Probability Theory and Related Fields},
number = {1-2},
pages = {165 -- 241},
publisher = {Springer},
title = {{Extremal eigenvalues and eigenvectors of deformed Wigner matrices}},
doi = {10.1007/s00440-014-0610-8},
volume = {164},
year = {2016},
}
@article{1411,
abstract = {We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.},
author = {Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli},
journal = {Israel Journal of Mathematics},
number = {1},
pages = {37 -- 79},
publisher = {Springer},
title = {{Untangling two systems of noncrossing curves}},
doi = {10.1007/s11856-016-1294-9},
volume = {212},
year = {2016},
}
@article{1794,
abstract = {We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.},
author = {Kolmogorov, Vladimir and Takhanov, Rustem},
journal = {Algorithmica},
number = {1},
pages = {17 -- 46},
publisher = {Springer},
title = {{Inference algorithms for pattern-based CRFs on sequence data}},
doi = {10.1007/s00453-015-0017-7},
volume = {76},
year = {2016},
}