1,721,298 research outputs found
Thomas Watson Griggs
No full textAn obituary for the Iowan businessman and politician Thomas Watson Griggs
Thomas Watson Griggs
No full textAn obituary for the Iowan businessman and politician Thomas Watson Griggs
Communication Complexity of Statistical Distance
Get PDFWe prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over elements, and they wish to estimate within +-epsilon the statistical (total variation) distance between their distributions. For some range of parameters, there is up to a log(n) factor gap between the upper and lower bounds, and we identify a barrier to using information complexity techniques to improve the lower bound in this case. We also prove a side result that we discovered along the way: the randomized communication complexity of n-bit Majority composed with n-bit Greater-Than is Theta(n log n)
Advice Lower Bounds for the Dense Model Theorem
Get PDFWe prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution D that is delta-dense in a distribution that is epsilon'-indistinguishable from uniform, there exists a "dense model" for D, that is, a distribution that is delta-dense in the uniform distribution and is epsilon-indistinguishable from D. This epsilon-indistinguishability is with respect to an arbitrary small class of functions F. For the natural case where epsilon' >= Omega(epsilon delta) and epsilon >= delta^{O(1)}, our lower bound implies that Omega(sqrt{(1/epsilon)log(1/delta)} log|F|) advice bits are necessary. There is only a polynomial gap between our lower bound and the best upper bound for this case (due to Zhang), which is O((1/epsilon^2)log(1/delta) log|F|). Our lower bound can be viewed as an analog of list size lower bounds for list-decoding of error-correcting codes, but for "dense model decoding" instead. Our proof introduces some new techniques which may be of independent interest, including an analysis of a majority of majorities of p-biased bits. The latter analysis uses an extremely tight lower bound on the tail of the binomial distribution, which we could not find in the literature
Feu de l’amour, feu du soleil dans The Hekatompathia de Thomas Watson
No full textThis article aims to explore the relations between the themes of love, fire and sun and their mythological representations in The Hekatompathia, a love sonnet sequence by Thomas Watson (1582). The Petrarchist topoi such as the eyes of the beloved as the sun or the burning heart may seem hackneyed, but provide the starting point for an original system, intermingling metaphors, symbols and mythological figures.Ginestet Gaëlle. Feu de l’amour, feu du soleil dans The Hekatompathia de Thomas Watson. In: Anglophonia/Caliban, n°13, 2003. Mythe et Littérature. Shakespeare et ses contemporains. pp. 57-67
Commencement Luncheon, August 10, 1945, Judge Jeremiah O\u27Connell, Mrs. Thomas Watson, and Father Galliher
No full textBlack and white photograph of Commencement Luncheon in Providence Biltmore Garden Restaurant. From left to right: Judge Jeremiah O\u27Connell, Mrs. Thomas Watson, and Father Galliher, President of Providence College from 1945 to 1947.https://digitalcommons.bryant.edu/hist_photos/1077/thumbnail.jp
Watson Family
No full textPhotograph - A group of people sitting on the steps of a house, Athabasca, Alberta. Adults, left to right: Thomas Watson, Cecilia Barbara Wright (Watson), Bessie Finlayson (Bell), and Agnes Bell (sister of Thomas Watson). The Wright children, clockwise from top: George, Robin, Charles and Mari
Metropolitan Museum of Art, Thomas Watson Library, Costume Institute, New York
No full textLes deux bases de la Thomas Watson Library et du MET sont incontournables pour l’étude des textiles. La première, celle de la « Costume Institute Collection », rassemble les collections du Costume Institute et du Irene Lewisohn Costume Reference Library du MET et présente des costumes de théâtre anciens et contemporains, mais également des costumes de fêtes populaires, de mode pour femmes et hommes, etc. Ces archives contiennent plus précisément les croquis des tenues dessinées par Chanel, Di..
The Complexity of Deciding Statistical Properties of Samplable Distributions
Get PDFWe consider the problems of deciding whether the joint distribution sampled by a given circuit satisfies certain statistical properties such as being i.i.d., being exchangeable, being pairwise independent, having two coordinates with identical marginals, having two uncorrelated coordinates, and many other variants. We give a proof that simultaneously shows all these problems are C_{=P}-complete, by showing that the following promise problem (which is a restriction of all the above problems) is C_{=P}-complete: Given a circuit, distinguish the case where the output distribution is uniform and the case where every pair of coordinates is neither uncorrelated nor identically distributed. This completeness result holds even for samplers that are depth-3 circuits.
We also consider circuits that are d-local, in the sense that each output bit depends on at most d input bits. We give linear-time algorithms for deciding whether a 2-local sampler's joint distribution is fully independent, and whether it is exchangeable.
We also show that for general circuits, certain approximation versions of the problems of deciding full independence and exchangeability are SZK-complete.
We also introduce a bounded-error version of C_{=P}, which we call BC_{=P}, and we investigate its structural properties
- …
