📄 http:^^cs.nyu.edu^cs^faculty^siegel^index.html
字号:
Date: Mon, 25 Nov 1996 22:03:31 GMTServer: NCSA/1.4.1Content-type: text/htmlLast-modified: Wed, 09 Aug 1995 00:13:41 GMTContent-length: 4947<html><head><title>Alan Siegel</title><link rev="made" href="mailto:siegel@cs.nyu.edu (Alan Siegel)"></head><body><H1>Alan Siegel</H1><H2>Associate Professor, Computer Science Dept</H2><H2> <!WA0><A HREF="http://found.cs.nyu.edu/cgi-bin/finger?siegel@merv">Alan Siegel@cs.nyu.edu</H2><HR><!WA1><a HREF="http://cs.nyu.edu/">Department of Computer Science<br></a><!WA2><a HREF="http://cs.nyu.edu/cs/courantnyu.html">Courant Institute of Mathematical Sciences<br></a><!WA3><a HREF="http://nyu.edu/">New York University<p></a><HR><PRE><H2>Mail Address</H2> <!WA4><a HREF="http://cs.nyu.edu/cs/faculty/siegel/wsq-campus.html">Courant Inst. of Math. Sciences</a>, rm 413<br> 251 Mercer St.<br> New York, NY 10012, U.S.A.<p></PRE><PRE><H2>Phones</H2> 212.998.3122 (voice) 212.995.4121 (fax)<p></PRE><PRE><H2>Email</H2><I> <!WA5><A HREF="http://found.cs.nyu.edu/cgi-bin/finger?siegel@merv">Alan Siegel@cs.nyu.edu</A></I></PRE><HR><H2>Topics</H2><ul><li>SODA 95 paper<!WA6><a href="http://cs.nyu.edu/cs/faculty/siegel/soda.ps">PostScript</A></ul></ul><P><dt><!WA7><a href="file://cs.nyu.edu/pub/tech-reports/tr684.ps.gz">tr684 </a><dd> A. Siegel,"On Universal Classes of Extremely Random Constant Time Hash Functionsand their Time-space Tradeoff",Apr. 1995<P>Abstract: A family of functions F that map [0,n]->[0,n], is said to be h-wise independentif any h points in [0,n] have an image, for randomly selected f in F, that isuniformly distributed. This paper gives both probabilistic and explicitrandomized constructions of (n**epsilon)-wise independent functions, forepsilon<1, that can be evaluated in constant time for the standard randomaccess model of computation. Simple extensions give comparable behavior forlarger domains. As a consequence, many probabilistic algorithms can for thefirst time be shown to achieve their expected asymptotic performance for afeasible model of computation.<P>This paper also establishes a tight tradeoff in the number of random seeds thatmust be precomputed for a random function that runs in time T and is h-wiseindependent.<dd></dt> <P><dt><!WA8><a href="file://cs.nyu.edu/pub/tech-reports/tr685.ps.gz">tr685 </a><dd> A. Siegel,"Toward a Usable Theory of Chernoff Bounds for Heterogeneous and PartiallyDependent Random Variables",Apr. 1995<P>Abstract:Let X be a sum of real valued random variables and have a bounded mean E[X].The generic Chernoff-Hoeffding estimate for large deviations of X is:P{X-E[X]>=a}<=min_{y>=0}exp(-y(a+E[X]))E[exp(y X)], which applies with a>=0to random variables with very small tails. At issue is how to use this methodto attain sharp and useful estimates. We present a number of Chernoff-Hoeffdingbounds for sums of random variables that may have a variety of dependentrelationships and that may be heterogeneously distributed.<dd></dt><P><dt><!WA9><a href="file://cs.nyu.edu/pub/tech-reports/tr686.ps.gz">tr686 </a><dd> J. Schmidt, A. Siegel,"Double Hashing is Computable and Randomizable with Universal Hash Functions",Apr. 1995<P>Abstract:Universal hash functions that exhibit (c log n)-wise independence are shown togive a performance in double hashing and virtually any reasonablegeneralization of double hashing that has an expected probe count of1/(1-alpha) + epsilon for the insertion of the (alpha n)-th item into a tableof size n, for any fixed alpha < 1 and epsilon > 0. This performance is withinepsilon of optimal. These results are derived from a novel formulation thatoverestimates the expected probe count by underestimating the presence ofpartial items already inserted into the hash table, and from a sharp analysisof the underlying stochastic structures formed by colliding items.<dd></dt> <P><dt><!WA10><a href="file://cs.nyu.edu/pub/tech-reports/tr687.ps.gz">tr687 </a><dd> A. Siegel, J. Schmidt,"Closed Hashing is Computable and Optimally Randomizable with Universal Hash Functions",Apr. 1995<P>Abstract:Universal hash functions that exhibit (c log n)-wise independence are shown togive a performance in double hashing, uniform hashing and virtually anyreasonable generalization of double hashing that has an expected probe count of1/(1-alpha)+O(1/n) for the insertion of the (alpha n)-th item into a table ofsize n, for any fixed alpha < 1. This performance is optimal. These resultsare derived from a novel formulation that overestimates the expected probecount by underestimating the presence of local items already inserted into thehash table, and from a very sharp analysis of the underlying stochasticstructures formed by colliding items.<P>Analogous bounds are attained for the expected r-th moment of the probe count,for any fixed r, and linear probing is also shown to achieve a performancewith universal hash functions that is equivalent to the fully random case.<dd></dt><P><li>NYU Tech Reports<!WA11><a href="file://cs.nyu.edu/pub/tech-reports/tr.html">hypertext</A><HR><HR></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -