(cid:51)(cid:53)(cid:50)(cid:38)(cid:40)(cid:40)(cid:39)(cid:44)(cid:49)(cid:42)(cid:54)(cid:3)(cid:50)(cid:41)(cid:3)(cid:55)(cid:43)(cid:40)(cid:3)(cid:55)(cid:43)(cid:44)(cid:53)(cid:55)(cid:44)(cid:40)(cid:55)(cid:43)(cid:3)
`(cid:36)(cid:49)(cid:49)(cid:56)(cid:36)(cid:47)(cid:3)(cid:36)(cid:38)(cid:48)(cid:3)(cid:54)(cid:60)(cid:48)(cid:51)(cid:50)(cid:54)(cid:44)(cid:56)(cid:48)(cid:3)(cid:50)(cid:49)(cid:3)
`(cid:55)(cid:43)(cid:40)(cid:50)(cid:53)(cid:60)(cid:3)(cid:50)(cid:41)(cid:3)(cid:38)(cid:50)(cid:48)(cid:51)(cid:56)(cid:55)(cid:44)(cid:49)(cid:42)
`
`(cid:39)(cid:68)(cid:79)(cid:79)(cid:68)(cid:86)(cid:15)(cid:3)(cid:55)(cid:72)(cid:91)(cid:68)(cid:86)(cid:3)
`(cid:48)(cid:68)(cid:92)(cid:3)(cid:21)(cid:22)(cid:16)(cid:21)(cid:25)(cid:15)(cid:3)(cid:20)(cid:28)(cid:28)(cid:27)(cid:3)
`(cid:54)(cid:51)(cid:50)(cid:49)(cid:54)(cid:50)(cid:53)(cid:40)(cid:39)(cid:3)(cid:37)(cid:60)
`(cid:55)(cid:43)(cid:40)(cid:3)(cid:36)(cid:38)(cid:48)(cid:3)(cid:54)(cid:51)(cid:40)(cid:38)(cid:44)(cid:36)(cid:47)(cid:3)(cid:44)(cid:49)(cid:55)(cid:40)(cid:53)(cid:40)(cid:54)(cid:55)(cid:3)(cid:42)(cid:53)(cid:50)(cid:56)(cid:51)(cid:3)(cid:41)(cid:50)(cid:53)(cid:3)
`(cid:36)(cid:47)(cid:42)(cid:50)(cid:53)(cid:44)(cid:55)(cid:43)(cid:48)(cid:54)(cid:3)(cid:36)(cid:49)(cid:39)(cid:3)(cid:38)(cid:50)(cid:48)(cid:51)(cid:56)(cid:55)(cid:36)(cid:55)(cid:44)(cid:50)(cid:49)(cid:3)(cid:55)(cid:43)(cid:40)(cid:50)(cid:53)(cid:60)
`
`i
`
`Apple 1009
`
`
`(cid:36)(cid:49)(cid:49)(cid:56)(cid:36)(cid:47)(cid:3)(cid:36)(cid:38)(cid:48)(cid:3)(cid:54)(cid:60)(cid:48)(cid:51)(cid:50)(cid:54)(cid:44)(cid:56)(cid:48)(cid:3)(cid:50)(cid:49)(cid:3)
`(cid:55)(cid:43)(cid:40)(cid:50)(cid:53)(cid:60)(cid:3)(cid:50)(cid:41)(cid:3)(cid:38)(cid:50)(cid:48)(cid:51)(cid:56)(cid:55)(cid:44)(cid:49)(cid:42)
`
`(cid:39)(cid:68)(cid:79)(cid:79)(cid:68)(cid:86)(cid:15)(cid:3)(cid:55)(cid:72)(cid:91)(cid:68)(cid:86)(cid:3)
`(cid:48)(cid:68)(cid:92)(cid:3)(cid:21)(cid:22)(cid:16)(cid:21)(cid:25)(cid:15)(cid:3)(cid:20)(cid:28)(cid:28)(cid:27)(cid:3)
`(cid:54)(cid:51)(cid:50)(cid:49)(cid:54)(cid:50)(cid:53)(cid:40)(cid:39)(cid:3)(cid:37)(cid:60)
`(cid:55)(cid:43)(cid:40)(cid:3)(cid:36)(cid:38)(cid:48)(cid:3)(cid:54)(cid:51)(cid:40)(cid:38)(cid:44)(cid:36)(cid:47)(cid:3)(cid:44)(cid:49)(cid:55)(cid:40)(cid:53)(cid:40)(cid:54)(cid:55)(cid:3)(cid:42)(cid:53)(cid:50)(cid:56)(cid:51)(cid:3)(cid:41)(cid:50)(cid:53)(cid:3)
`(cid:36)(cid:47)(cid:42)(cid:50)(cid:53)(cid:44)(cid:55)(cid:43)(cid:48)(cid:54)(cid:3)(cid:36)(cid:49)(cid:39)(cid:3)(cid:38)(cid:50)(cid:48)(cid:51)(cid:56)(cid:55)(cid:36)(cid:55)(cid:44)(cid:50)(cid:49)(cid:3)(cid:55)(cid:43)(cid:40)(cid:50)(cid:53)(cid:60)
`
`i
`
`Apple 1009
`
`
`
`(cid:47)(cid:76)(cid:69)(cid:85)(cid:68)(cid:85)(cid:92)(cid:15)(cid:3)(cid:56)(cid:38)(cid:3)(cid:54)(cid:68)(cid:85)(cid:77)(cid:87)(cid:68)(cid:3)(cid:38)(cid:85)(cid:76)(cid:76)(cid:93)(cid:3)(cid:20)(cid:28)(cid:28)(cid:28)
`Univ. Library, UL} Santa Cruz "£933:
`
`(cid:55)(cid:75)(cid:72)(cid:3)(cid:36)(cid:86)(cid:86)(cid:82)(cid:70)(cid:76)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:38)(cid:82)(cid:80)(cid:83)(cid:88)(cid:87)(cid:76)(cid:81)(cid:74)(cid:3)(cid:48)(cid:68)(cid:70)(cid:75)(cid:76)(cid:81)(cid:72)(cid:85)(cid:92)(cid:3)
`The Association for Computing Maehittery
`(cid:20)(cid:24)(cid:20)(cid:24)(cid:3)(cid:37)(cid:85)(cid:82)(cid:68)(cid:71)(cid:90)(cid:68)(cid:92)(cid:3)
`I515 Bruatlway
`New York New York 10036
`(cid:49)(cid:72)(cid:90)(cid:3)(cid:60)(cid:82)(cid:85)(cid:78)(cid:3)(cid:49)(cid:72)(cid:90)(cid:3)(cid:60)(cid:82)(cid:85)(cid:78)(cid:3)(cid:20)(cid:19)(cid:19)(cid:22)(cid:25)
`
`(cid:38)(cid:82)(cid:83)(cid:92)(cid:85)(cid:76)(cid:74)(cid:79)(cid:76)(cid:79)(cid:3)(cid:20)(cid:3)(cid:181)(cid:45)(cid:92)(cid:54)(cid:3)(cid:69)(cid:92)(cid:3)(cid:11)(cid:75)(cid:72)(cid:3)(cid:36)(cid:86)(cid:86)(cid:82)(cid:70)(cid:76)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:38)(cid:82)(cid:81)(cid:76)(cid:83)(cid:88)(cid:79)(cid:76)(cid:81)(cid:74)(cid:3)(cid:48)(cid:68)(cid:70)(cid:75)(cid:76)(cid:81)(cid:72)(cid:85)(cid:92)(cid:15)(cid:3)(cid:44)(cid:81)(cid:70)(cid:17)(cid:11)(cid:36)(cid:38)(cid:48)(cid:12)(cid:17)(cid:3)
`Cop_\-"right
`I998 by the Associatiott for Computing Maeltinery. lne.(ACM).
`(cid:51)(cid:72)(cid:85)(cid:80)(cid:76)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:87)(cid:82)(cid:3)(cid:80)(cid:68)(cid:78)(cid:72)(cid:3)(cid:71)(cid:76)(cid:74)(cid:76)(cid:87)(cid:68)(cid:79)(cid:3)(cid:82)(cid:85)(cid:3)(cid:79)(cid:76)(cid:68)(cid:85)(cid:71)(cid:3)(cid:70)(cid:82)(cid:83)(cid:76)(cid:72)(cid:86)(cid:3)(cid:82)(cid:73)(cid:3)(cid:68)(cid:79)(cid:79)(cid:3)(cid:82)(cid:85)(cid:3)(cid:83)(cid:68)(cid:85)(cid:87)(cid:3)(cid:82)(cid:73)(cid:3)(cid:11)(cid:75)(cid:76)(cid:86)(cid:3)(cid:90)(cid:82)(cid:85)(cid:78)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)
`Pertttission to make digital or hard copies ofall or pan of this work for
`(cid:83)(cid:72)(cid:85)(cid:86)(cid:82)(cid:81)(cid:68)(cid:79)(cid:3)(cid:82)(cid:85)(cid:3)(cid:70)(cid:79)(cid:68)(cid:86)(cid:86)(cid:85)(cid:82)(cid:82)(cid:80)(cid:3)(cid:88)(cid:86)(cid:72)(cid:3)(cid:76)(cid:86)(cid:3)(cid:74)(cid:85)(cid:68)(cid:81)(cid:87)(cid:72)(cid:71)(cid:3)(cid:90)(cid:76)(cid:87)(cid:75)(cid:82)(cid:88)(cid:87)(cid:3)(cid:73)(cid:72)(cid:72)(cid:3)(cid:83)(cid:85)(cid:82)(cid:89)(cid:76)(cid:71)(cid:72)(cid:71)(cid:3)(cid:87)(cid:75)(cid:68)(cid:87)(cid:3)(cid:70)(cid:82)(cid:83)(cid:76)(cid:72)(cid:86)(cid:3)
`personal or classroom use is granted without fee provided that copies
`(cid:68)(cid:85)(cid:70)(cid:3)(cid:81)(cid:82)(cid:87)(cid:3)(cid:80)(cid:68)(cid:71)(cid:72)(cid:3)(cid:82)(cid:85)(cid:3)(cid:71)(cid:76)(cid:86)(cid:87)(cid:85)(cid:76)(cid:69)(cid:88)(cid:87)(cid:72)(cid:71)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:83)(cid:85)(cid:82)(cid:73)(cid:76)(cid:87)(cid:3)(cid:82)(cid:85)(cid:3)(cid:70)(cid:82)(cid:80)(cid:80)(cid:72)(cid:85)(cid:70)(cid:76)(cid:68)(cid:79)(cid:3)(cid:68)(cid:71)(cid:89)(cid:68)(cid:81)(cid:87)(cid:68)(cid:74)(cid:72)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:11)(cid:75)(cid:68)(cid:87)(cid:3)
`are not made or distributed for profit or commercial advantage and that
`(cid:70)(cid:82)(cid:83)(cid:76)(cid:72)(cid:86)(cid:3)(cid:69)(cid:72)(cid:68)(cid:85)(cid:3)(cid:87)(cid:75)(cid:76)(cid:86)(cid:3)(cid:81)(cid:82)(cid:87)(cid:76)(cid:70)(cid:72)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:73)(cid:88)(cid:79)(cid:79)(cid:3)(cid:70)(cid:76)(cid:87)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:82)(cid:81)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:73)(cid:76)(cid:85)(cid:86)(cid:87)(cid:3)(cid:83)(cid:68)(cid:74)(cid:72)(cid:17)(cid:3)(cid:55)(cid:82)(cid:3)(cid:70)(cid:82)(cid:83)(cid:92)(cid:3)
`copies bear this notice and tlte full citation on the lirst page. To cop)
`(cid:82)(cid:87)(cid:75)(cid:72)(cid:85)(cid:90)(cid:76)(cid:86)(cid:72)(cid:15)(cid:3)(cid:87)(cid:82)(cid:3)(cid:85)(cid:72)(cid:83)(cid:88)(cid:69)(cid:79)(cid:76)(cid:86)(cid:75)(cid:15)(cid:3)(cid:87)(cid:82)(cid:3)(cid:83)(cid:82)(cid:86)(cid:87)(cid:3)(cid:82)(cid:81)(cid:3)(cid:86)(cid:72)(cid:85)(cid:89)(cid:72)(cid:85)(cid:86)(cid:3)(cid:82)(cid:85)(cid:3)(cid:87)(cid:82)(cid:3)(cid:85)(cid:72)(cid:71)(cid:76)(cid:86)(cid:79)(cid:85)(cid:76)(cid:69)(cid:88)(cid:87)(cid:72)(cid:3)(cid:87)(cid:82)(cid:3)(cid:79)(cid:76)(cid:86)(cid:87)(cid:86)(cid:15)(cid:3)
`otherwise. to republish. to post on servers or to redistribute to lists.
`(cid:85)(cid:72)(cid:84)(cid:88)(cid:76)(cid:85)(cid:72)(cid:86)(cid:3)(cid:83)(cid:85)(cid:76)(cid:82)(cid:85)(cid:3)(cid:86)(cid:83)(cid:72)(cid:70)(cid:76)(cid:73)(cid:76)(cid:70)(cid:3)(cid:83)(cid:72)(cid:85)(cid:80)(cid:76)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:68)(cid:81)(cid:71)(cid:18)(cid:82)(cid:85)(cid:3)(cid:68)(cid:3)(cid:73)(cid:72)(cid:72)(cid:17)
`requires prior specific permissiott attd/or a fee.
`
`(cid:53)(cid:72)(cid:84)(cid:88)(cid:72)(cid:86)(cid:87)(cid:3)(cid:83)(cid:72)(cid:85)(cid:80)(cid:76)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:87)(cid:82)(cid:3)(cid:85)(cid:72)(cid:83)(cid:88)(cid:69)(cid:79)(cid:76)(cid:86)(cid:75)(cid:3)(cid:73)(cid:85)(cid:82)(cid:80)(cid:29)(cid:3)(cid:51)(cid:88)(cid:69)(cid:79)(cid:76)(cid:70)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:86)(cid:3)(cid:39)(cid:72)(cid:83)(cid:87)(cid:17)(cid:3)(cid:36)(cid:38)(cid:48)(cid:17)(cid:3)(cid:44)(cid:81)(cid:70)(cid:17)(cid:3)(cid:41)(cid:68)(cid:17)(cid:63)(cid:3)(cid:14)(cid:20)(cid:3)(cid:11)(cid:21)(cid:20)(cid:21)(cid:12)(cid:3)
`Reqttest permission to republish from: Publications Dept. ACM. lttc. Fax +1 (2l2)
`(cid:27)(cid:25)(cid:28)(cid:16)(cid:19)(cid:23)(cid:27)(cid:20)(cid:3)(cid:82)(cid:85)(cid:3)(cid:31)(cid:83)(cid:72)(cid:85)(cid:80)(cid:76)(cid:86)(cid:86)(cid:76)(cid:82)(cid:88)(cid:86)(cid:11)(cid:58)(cid:17)(cid:68)(cid:70)(cid:80)(cid:17)(cid:82)(cid:85)(cid:74)(cid:33)(cid:17)(cid:3)(cid:41)(cid:82)(cid:85)(cid:3)(cid:82)(cid:87)(cid:79)(cid:76)(cid:70)(cid:85)(cid:3)(cid:70)(cid:82)(cid:83)(cid:92)(cid:76)(cid:81)(cid:74)(cid:3)(cid:82)(cid:73)(cid:3)(cid:68)(cid:85)(cid:87)(cid:76)(cid:70)(cid:79)(cid:72)(cid:86)(cid:3)(cid:87)(cid:75)(cid:68)(cid:87)(cid:3)(cid:70)(cid:68)(cid:85)(cid:85)(cid:92)(cid:10)(cid:3)(cid:68)(cid:3)(cid:70)(cid:82)(cid:71)(cid:72)(cid:3)
`869-()48l or <pcnnissionsmzacnt.org>. For other copying ofarticles that carry a code
`(cid:68)(cid:87)(cid:3)(cid:11)(cid:75)(cid:72)(cid:3)(cid:69)(cid:82)(cid:87)(cid:87)(cid:82)(cid:80)(cid:3)(cid:82)(cid:73)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:73)(cid:76)(cid:85)(cid:86)(cid:87)(cid:3)(cid:82)(cid:85)(cid:3)(cid:79)(cid:68)(cid:86)(cid:87)(cid:3)(cid:83)(cid:68)(cid:74)(cid:72)(cid:15)(cid:3)(cid:70)(cid:82)(cid:83)(cid:92)(cid:76)(cid:81)(cid:74)(cid:3)(cid:76)(cid:86)(cid:3)(cid:83)(cid:72)(cid:85)(cid:80)(cid:76)(cid:87)(cid:87)(cid:72)(cid:71)(cid:3)(cid:83)(cid:85)(cid:82)(cid:89)(cid:76)(cid:71)(cid:72)(cid:71)(cid:3)(cid:11)(cid:75)(cid:68)(cid:87)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:83)(cid:72)(cid:85)(cid:16)(cid:70)(cid:82)(cid:83)(cid:92)(cid:3)
`at the bottom ol'the first or last page. copyittg is permitted provided that the per-copy
`(cid:73)(cid:72)(cid:72)(cid:3)(cid:76)(cid:81)(cid:71)(cid:76)(cid:70)(cid:68)(cid:87)(cid:72)(cid:71)(cid:3)(cid:76)(cid:81)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:70)(cid:82)(cid:71)(cid:72)(cid:3)(cid:76)(cid:86)(cid:3)(cid:83)(cid:68)(cid:76)(cid:71)(cid:3)(cid:87)(cid:75)(cid:85)(cid:82)(cid:88)(cid:74)(cid:75)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:38)(cid:82)(cid:83)(cid:92)(cid:85)(cid:76)(cid:74)(cid:75)(cid:87)(cid:3)(cid:38)(cid:79)(cid:72)(cid:68)(cid:85)(cid:68)(cid:81)(cid:70)(cid:72)(cid:3)(cid:38)(cid:72)(cid:81)(cid:87)(cid:72)(cid:85)(cid:17)(cid:3)(cid:21)(cid:21)(cid:21)(cid:3)
`fee indicated itt the code is paid through the Copyrigltt Clearance Center. 222
`Roscuood Drive. Danvers. MA tll‘)2."v.
`(cid:53)(cid:82)(cid:86)(cid:72)(cid:90)(cid:82)(cid:82)(cid:71)(cid:3)(cid:39)(cid:85)(cid:76)(cid:89)(cid:72)(cid:17)(cid:3)(cid:39)(cid:68)(cid:81)(cid:89)(cid:72)(cid:85)(cid:86)(cid:17)(cid:3)(cid:48)(cid:36)(cid:3)(cid:19)(cid:20)(cid:28)(cid:21)(cid:17)(cid:10)(cid:76)(cid:17)
`
`ACM ISBN: l)-X‘)7‘)I-‘)(»2-‘)
`(cid:36)(cid:38)(cid:48)(cid:3)(cid:44)(cid:54)(cid:37)(cid:49)(cid:29)(cid:3)(cid:19)(cid:16)(cid:27)(cid:28)(cid:26)(cid:28)(cid:20)(cid:16)(cid:28)(cid:25)(cid:21)(cid:16)(cid:28)
`
`(cid:36)(cid:71)(cid:71)(cid:76)(cid:87)(cid:76)(cid:82)(cid:81)(cid:68)(cid:79)(cid:3)(cid:70)(cid:82)(cid:83)(cid:76)(cid:72)(cid:86)(cid:3)(cid:80)(cid:68)(cid:92)(cid:3)(cid:69)(cid:72)(cid:3)(cid:82)(cid:85)(cid:71)(cid:72)(cid:85)(cid:72)(cid:71)(cid:3)(cid:83)(cid:85)(cid:72)(cid:83)(cid:68)(cid:76)(cid:71)(cid:3)(cid:73)(cid:85)(cid:82)(cid:80)(cid:29)
`Additional copies may be ordered prepaid from:
`
`(cid:36)(cid:38)(cid:48)(cid:3)(cid:50)(cid:85)(cid:71)(cid:72)(cid:85)(cid:3)(cid:39)(cid:72)(cid:83)(cid:68)(cid:85)(cid:87)(cid:80)(cid:72)(cid:81)(cid:87)(cid:3)
`ACM Ortler Department
`PO Box I I~tl-l
`(cid:51)(cid:50)(cid:3)(cid:37)(cid:82) (cid:17)(cid:81)(cid:3)(cid:20)(cid:20)(cid:23)(cid:20)(cid:23)
`Clturelt Street Station
`(cid:38)(cid:75)(cid:88)(cid:85)(cid:70)(cid:75)(cid:3)(cid:54)(cid:87)(cid:85)(cid:72)(cid:72)(cid:87)(cid:3)(cid:54)(cid:87)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)
`New York. NY Itl2t<(i
`(cid:49)(cid:72)(cid:90)(cid:3)(cid:60)(cid:82)(cid:85)(cid:78)(cid:17)(cid:3)(cid:49)(cid:60)(cid:3)(cid:20)(cid:19)(cid:21)(cid:27)(cid:25)
`
`Phone:
`l-Xtltt-342-(t(i2(»
`(cid:51)(cid:75)(cid:82)(cid:81)(cid:72)(cid:29)(cid:3)(cid:20)(cid:16)(cid:27)(cid:19)(cid:19)(cid:16)(cid:15)(cid:5)(cid:76)(cid:23)(cid:21)(cid:16)(cid:25)(cid:25)(cid:21)(cid:25)(cid:3)
`(US and Canada)
`(cid:11)(cid:56)(cid:54)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:38)(cid:68)(cid:81)(cid:68)(cid:71)(cid:68)(cid:12)
`+ I-212-620-ttitttl
`(cid:14)(cid:3)(cid:20)(cid:16)(cid:21)(cid:20)(cid:21)(cid:16)(cid:25)(cid:21)(cid:25)(cid:16)(cid:19)(cid:17)(cid:24)(cid:19)(cid:19)(cid:3)
`(all Otlter countries)
`(cid:11)(cid:68)(cid:79)(cid:79)(cid:3)(cid:82)(cid:87)(cid:75)(cid:72)(cid:85)(cid:3)(cid:70)(cid:82)(cid:88)(cid:81)(cid:87)(cid:85)(cid:76)(cid:72)(cid:86)(cid:12)
`Fax: +l—2l2-944-I3 I8
`(cid:41)(cid:68)(cid:17)(cid:63)(cid:29)(cid:3)(cid:14)(cid:20)(cid:16)(cid:21)(cid:20)(cid:21)(cid:16)(cid:28)(cid:23)(cid:23)(cid:16)(cid:20)(cid:17)(cid:20)(cid:20)(cid:27)(cid:3)
`(cid:40)(cid:16)(cid:87)(cid:81)(cid:68)(cid:76)(cid:79)(cid:29)(cid:3)(cid:68)(cid:70)(cid:80)(cid:83)(cid:88)(cid:69)(cid:86)(cid:11)(cid:85)(cid:18)(cid:30)(cid:68)(cid:70)(cid:80)(cid:17)(cid:82)(cid:85)(cid:74)
`E-mail: actt1pttbs.’u‘2aettt.org
`
`0
`(cid:13)
`
`ACM Order Number: S(l8')8tl
`(cid:36)(cid:38)(cid:48)(cid:3)(cid:50)(cid:85)(cid:71)(cid:72)(cid:85)(cid:3)(cid:49)(cid:88)(cid:80)(cid:75)(cid:72)(cid:85)(cid:29)(cid:3)(cid:17)(cid:24)(cid:19)(cid:27)(cid:28)(cid:27)(cid:19)(cid:3)
`Printed in the USA
`(cid:51)(cid:85)(cid:76)(cid:81)(cid:87)(cid:72)(cid:71)(cid:3)(cid:76)(cid:81)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:56)(cid:54)(cid:36)
`
`ii
`
`
`
`(cid:25)(cid:76)(cid:79)(cid:63)
`(cid:20)(cid:24)(cid:17)(cid:65)
`. 5
`/if
`(cid:80)
`4%’
`.
`
`7 )
`
`A 5
`
`(cid:38)(cid:82)(cid:81)(cid:73)(cid:72)(cid:85)(cid:72)(cid:81)(cid:70)(cid:72)(cid:3)(cid:50)(cid:85)(cid:74)(cid:68)(cid:81)(cid:76)(cid:93)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)
`Conference Organization
`
`SIGACT Chair
`
`(cid:54)(cid:44)(cid:42)(cid:36)(cid:38)(cid:55)(cid:3)(cid:38)(cid:75)(cid:68)(cid:76)(cid:85)
`
`(cid:45)(cid:72)(cid:73)(cid:73)(cid:85)(cid:72)(cid:92)(cid:3)(cid:57)(cid:76)(cid:87)(cid:87)(cid:72)(cid:85)
`Jeffrey Vitter
`
`Conference Chairs
`
`(cid:38)(cid:82)(cid:81)(cid:73)(cid:72)(cid:85)(cid:72)(cid:81)(cid:70)(cid:72)(cid:3)(cid:38)(cid:75)(cid:68)(cid:76)(cid:85)(cid:86)
`
`(cid:58)(cid:82)(cid:79)(cid:73)(cid:3)(cid:37)(cid:72)(cid:76)(cid:81)(cid:3)
`Wolf Bein
`(cid:54)(cid:87)(cid:72)(cid:89)(cid:72)(cid:3)(cid:55)(cid:68)(cid:87)(cid:72)
`Steve Tate
`
`(cid:51)(cid:85)(cid:82)(cid:74)(cid:85)(cid:68)(cid:80)(cid:3)(cid:38)(cid:75)(cid:68)(cid:76)(cid:85)(cid:86)
`Program Chairs
`
`(cid:41)(cid:68)(cid:81)(cid:3)(cid:38)(cid:75)(cid:88)(cid:81)(cid:74)(cid:3)(cid:42)(cid:85)(cid:68)(cid:75)(cid:68)(cid:80)
`Fan Chung Graham
`
`Treasurer
`
`(cid:55)(cid:85)(cid:72)(cid:68)(cid:86)(cid:88)(cid:85)(cid:72)(cid:85)
`
`(cid:47)(cid:68)(cid:90)(cid:85)(cid:72)(cid:81)(cid:70)(cid:72)(cid:3)(cid:47)(cid:68)(cid:85)(cid:80)(cid:82)(cid:85)(cid:72)
`Lawrence Larmore
`
`(cid:77)(cid:10)
`
`(cid:51)(cid:88)(cid:69)(cid:79)(cid:76)(cid:70)(cid:76)(cid:87)(cid:92)(cid:3)(cid:38)(cid:75)(cid:68)(cid:76)(cid:85)
`Publicity Chair
`
`(cid:44)(cid:68)(cid:81)(cid:3)(cid:51)(cid:68)(cid:85)(cid:69)(cid:72)(cid:85)(cid:85)(cid:92)
`Ian Parberry
`
`(cid:54)(cid:44)(cid:42)(cid:36)(cid:38)(cid:55)(cid:3)(cid:44)(cid:81)(cid:86)(cid:87)(cid:76)(cid:87)(cid:88)(cid:87)(cid:76)(cid:82)(cid:81)(cid:68)(cid:79)(cid:3)(cid:54)(cid:83)(cid:82)(cid:81)(cid:86)(cid:82)(cid:85)(cid:86)
`SIGACT Institutional Sponsors
`
`(cid:36)(cid:70)(cid:68)(cid:71)(cid:72)(cid:80)(cid:76)(cid:70)(cid:3)(cid:51)(cid:85)(cid:72)(cid:86)(cid:86)(cid:15)(cid:3)(cid:44)(cid:81)(cid:70)(cid:17)
`Academic Press, Inc.
`(cid:36)(cid:55)(cid:9)(cid:55)(cid:3)(cid:47)(cid:68)(cid:69)(cid:82)(cid:85)(cid:68)(cid:87)(cid:82)(cid:85)(cid:76)(cid:72)(cid:86)
`A T & T Laboratories
`(cid:44)(cid:37)(cid:48)(cid:3)(cid:38)(cid:82)(cid:85)(cid:83)(cid:82)(cid:85)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:178)(cid:3)(cid:55)(cid:45)(cid:3)(cid:58)(cid:68)(cid:87)(cid:86)(cid:82)(cid:81)(cid:3)(cid:53)(cid:72)(cid:86)(cid:72)(cid:68)(cid:85)(cid:70)(cid:75)(cid:3)(cid:38)(cid:72)(cid:81)(cid:87)(cid:72)(cid:85)(cid:3)
`IBM Corporation — TJ Watson Research Center
`(cid:44)(cid:81)(cid:87)(cid:72)(cid:85)(cid:81)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:68)(cid:79)(cid:3)(cid:55)(cid:75)(cid:82)(cid:80)(cid:86)(cid:82)(cid:81)(cid:3)(cid:51)(cid:88)(cid:69)(cid:79)(cid:76)(cid:86)(cid:75)(cid:76)(cid:81)(cid:74)(cid:3)
`International Thomson Publishing
`(cid:47)(cid:88)(cid:70)(cid:72)(cid:81)(cid:87)(cid:3)(cid:55)(cid:72)(cid:70)(cid:75)(cid:81)(cid:82)(cid:79)(cid:82)(cid:74)(cid:76)(cid:72)(cid:86)(cid:87)(cid:16)(cid:37)(cid:72)(cid:79)(cid:79)(cid:3)(cid:47)(cid:68)(cid:69)(cid:82)(cid:85)(cid:68)(cid:87)(cid:82)(cid:85)(cid:76)(cid:72)(cid:86)(cid:3)
`Lucent Technologiest—Bell Laboratories
`(cid:48)(cid:76)(cid:70)(cid:85)(cid:82)(cid:86)(cid:82)(cid:73)(cid:87)(cid:3)(cid:53)(cid:72)(cid:86)(cid:72)(cid:68)(cid:85)(cid:70)(cid:75)(cid:3)
`Microsoft Research
`(cid:51)(cid:58)(cid:54)(cid:3)(cid:51)(cid:88)(cid:69)(cid:79)(cid:76)(cid:86)(cid:75)(cid:76)(cid:81)(cid:74)(cid:3)(cid:38)(cid:82)(cid:17)
`PWS Publishing Co.
`(cid:59)(cid:72)(cid:85)(cid:82)(cid:91)(cid:3)(cid:38)(cid:82)(cid:85)(cid:83)(cid:82)(cid:85)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:16)(cid:3)(cid:51)(cid:68)(cid:79)(cid:82)(cid:3)(cid:36)(cid:79)(cid:87)(cid:82)(cid:3)(cid:53)(cid:72)(cid:86)(cid:72)(cid:68)(cid:85)(cid:70)(cid:75)(cid:3)(cid:38)(cid:72)(cid:81)(cid:87)(cid:72)(cid:85)
`Xerox Corporation — Palo Alto Research Center
`
`iii
`
`
`
`(cid:51)(cid:85)(cid:82)(cid:70)(cid:72)(cid:72)(cid:71)(cid:76)(cid:81)(cid:74)(cid:86)(cid:3)(cid:82)(cid:73)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:55)(cid:75)(cid:76)(cid:85)(cid:87)(cid:76)(cid:72)(cid:87)(cid:75)(cid:3)
`Proceedings of the Thirtieth
`(cid:36)(cid:81)(cid:81)(cid:88)(cid:68)(cid:79)(cid:3)(cid:36)(cid:38)(cid:48)(cid:3)(cid:54)(cid:92)(cid:80)(cid:83)(cid:82)(cid:86)(cid:76)(cid:88)(cid:80)(cid:3)(cid:82)(cid:81)(cid:3)(cid:55)(cid:75)(cid:72)(cid:82)(cid:85)(cid:92)(cid:3)(cid:82)(cid:73)(cid:3)(cid:38)(cid:82)(cid:80)(cid:83)(cid:88)(cid:87)(cid:76)(cid:81)(cid:74)
`Annual ACM Symposium on Theory of Computing
`(cid:48)(cid:68)(cid:92)(cid:3)(cid:21)(cid:22)(cid:3)(cid:16)(cid:3)(cid:21)(cid:25)(cid:15)(cid:20)(cid:28)(cid:28)(cid:27)(cid:15)(cid:3)(cid:39)(cid:68)(cid:79)(cid:79)(cid:68)(cid:86)(cid:15)(cid:3)(cid:55)(cid:72)(cid:91)(cid:68)(cid:86)(cid:15)(cid:3)(cid:56)(cid:54)(cid:36)
`May 23 — 26, 1998, Dallas, Texas, USA
`
`TABLE OF CONTENTS
`
`(cid:55)(cid:36)(cid:37)(cid:47)(cid:40)(cid:3)(cid:50)(cid:41)(cid:3)(cid:38)(cid:50)(cid:49)(cid:55)(cid:40)(cid:49)(cid:55)(cid:54)
`
`(cid:54)(cid:88)(cid:81)(cid:71)(cid:68)(cid:92)(cid:15)(cid:3)(cid:48)(cid:68)(cid:92)(cid:3)(cid:21)(cid:23)
`Sunday, May 24
`
`Session 1A
`(cid:54)(cid:72)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:79)(cid:36)
`(cid:50)(cid:81)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:47)(cid:76)(cid:80)(cid:76)(cid:87)(cid:86)(cid:3)(cid:82)(cid:73)(cid:3)(cid:49)(cid:82)(cid:81)(cid:16)(cid:36)(cid:83)(cid:83)(cid:85)(cid:82)(cid:91)(cid:76)(cid:80)(cid:68)(cid:69)(cid:76)(cid:79)(cid:76)(cid:87)(cid:92)(cid:3)(cid:82)(cid:73)(cid:3)(cid:47)(cid:68)(cid:87)(cid:87)(cid:76)(cid:70)(cid:72)(cid:3)(cid:51)(cid:85)(cid:82)(cid:69)(cid:79)(cid:72)(cid:80)(cid:86)(cid:3)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:3)(cid:20)
`On the Limits of Non-Approximability of Lattice Problems .
`.
`.
`. . .
`.
`.
`.
`. . . . . . . .
`.
`.
`.
`.
`.
`.
`.
`.
`. . .
`.
`.
`. . . . .
`l
`(cid:50)(cid:71)(cid:72)(cid:71)(cid:3)(cid:42)(cid:82)(cid:79)(cid:71)(cid:85)(cid:72)(cid:76)(cid:70)(cid:75)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:54)(cid:75)(cid:68)(cid:73)(cid:87)(cid:3)(cid:42)(cid:82)(cid:79)(cid:71)(cid:90)(cid:68)(cid:86)(cid:86)(cid:72)(cid:85)
`Oded Goldreich and Shafi Goldwasser
`(cid:55)(cid:75)(cid:72)(cid:3)(cid:54)(cid:75)(cid:82)(cid:85)(cid:87)(cid:72)(cid:86)(cid:87)(cid:3)(cid:57)(cid:72)(cid:70)(cid:87)(cid:82)(cid:85)(cid:3)(cid:51)(cid:85)(cid:82)(cid:69)(cid:79)(cid:72)(cid:80)(cid:3)(cid:76)(cid:81)(cid:3)(cid:47)(cid:21)(cid:3)(cid:76)(cid:86)(cid:3)(cid:49)(cid:51)(cid:16)(cid:43)(cid:68)(cid:85)(cid:71)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:53)(cid:68)(cid:81)(cid:71)(cid:82)(cid:80)(cid:76)(cid:93)(cid:72)(cid:71)(cid:3)(cid:53)(cid:72)(cid:71)(cid:88)(cid:70)(cid:87)(cid:76)(cid:82)(cid:81)(cid:86)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:20)(cid:19)
`The Shortest Vector Problem in L2 is NP-Hard for Randomized Reductions .
`.
`.
`.
`.
`. . . .
`.
`. . .
`.
`.
`. . .
`.
`. 10
`(cid:48)(cid:76)(cid:78)(cid:79)(cid:71)(cid:86)(cid:3)(cid:36)(cid:77)(cid:87)(cid:68)(cid:76)
`Miklos Ajtai
`(cid:52)(cid:88)(cid:68)(cid:81)(cid:87)(cid:88)(cid:80)(cid:3)(cid:38)(cid:76)(cid:85)(cid:70)(cid:88)(cid:76)(cid:87)(cid:86)(cid:3)(cid:90)(cid:76)(cid:87)(cid:75)(cid:3)(cid:48)(cid:76)(cid:91)(cid:72)(cid:71)(cid:3)(cid:54)(cid:87)(cid:68)(cid:87)(cid:72)(cid:86)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:21)(cid:19)
`Quantum Circuits with Mixed States .
`.
`.
`.
`.
`.
`.
`. .
`.
`.
`.
`.
`.
`.
`.
`. . . .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. . .
`.
`.
`. . .
`.
`.
`.
`.
`.
`.
`.
`.
`. . .
`.
`.
`. . . .
`. 20
`(cid:39)(cid:82)(cid:85)(cid:76)(cid:87)(cid:3)(cid:36)(cid:75)(cid:68)(cid:85)(cid:82)(cid:81)(cid:82)(cid:89)(cid:15)(cid:3)(cid:36)(cid:79)(cid:72)(cid:91)(cid:72)(cid:76)(cid:3)(cid:46)(cid:76)(cid:87)(cid:68)(cid:72)(cid:89)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:49)(cid:82)(cid:68)(cid:80)(cid:3)(cid:49)(cid:76)(cid:86)(cid:68)(cid:81)
`Dorit Ahamnov, Alexei Kitaev and Noam Nisan
`
`Session 1B
`(cid:54)(cid:72)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:44)(cid:37)
`(cid:40)(cid:91)(cid:68)(cid:70)(cid:87)(cid:3)(cid:54)(cid:68)(cid:80)(cid:83)(cid:79)(cid:76)(cid:81)(cid:74)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:36)(cid:83)(cid:83)(cid:85)(cid:82)(cid:91)(cid:76)(cid:80)(cid:68)(cid:87)(cid:72)(cid:3)(cid:38)(cid:82)(cid:88)(cid:81)(cid:87)(cid:76)(cid:81)(cid:74)(cid:3)(cid:55)(cid:72)(cid:70)(cid:75)(cid:81)(cid:76)(cid:84)(cid:88)(cid:72)(cid:86)(cid:3)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17) (cid:3)(cid:22)(cid:20)
`Exact Sampling and Approximate Counting Techniques . .
`.
`.
`.
`.
`.
`.
`.
`. . .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. . .
`.
`.
`. 31
`Mark L. Huber
`(cid:48)(cid:68)(cid:85)(cid:78)(cid:3)(cid:47)(cid:17)(cid:3)(cid:43)(cid:88)(cid:69)(cid:72)(cid:85)
`(cid:36)(cid:3)(cid:51)(cid:82)(cid:79)(cid:92)(cid:81)(cid:82)(cid:80)(cid:76)(cid:68)(cid:79)(cid:3)(cid:36)(cid:83)(cid:83)(cid:85)(cid:82)(cid:91)(cid:76)(cid:80)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:36)(cid:79)(cid:74)(cid:82)(cid:85)(cid:76)(cid:87)(cid:75)(cid:80)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:87)(cid:75)(cid:72)(cid:3)(cid:48)(cid:76)(cid:81)(cid:76)(cid:80)(cid:88)(cid:80)(cid:3)(cid:41)(cid:76)(cid:79)(cid:79)(cid:16)(cid:44)(cid:81)(cid:3)(cid:51)(cid:85)(cid:82)(cid:69)(cid:79)(cid:72)(cid:80)(cid:3)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:23)(cid:20)
`A Polynomial Approximation Algorithm for the Minimum Fill-In Problem . . . . . . . . .
`.
`.
`.
`. . . .
`.
`.
`.
`. 41
`(cid:36)(cid:86)(cid:86)(cid:68)(cid:73)(cid:3)(cid:49)(cid:68)(cid:87)(cid:68)(cid:81)(cid:93)(cid:82)(cid:81)(cid:15)(cid:3)(cid:53)(cid:82)(cid:81)(cid:3)(cid:54)(cid:75)(cid:68)(cid:80)(cid:76)(cid:85)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:53)(cid:82)(cid:71)(cid:72)(cid:71)(cid:3)(cid:54)(cid:75)(cid:68)(cid:85)(cid:68)(cid:81)
`AssafNatanzon, Ron Shamir and Roded Sharan
`(cid:44)(cid:80)(cid:83)(cid:85)(cid:82)(cid:89)(cid:72)(cid:71)(cid:3)(cid:36)(cid:83)(cid:83)(cid:85)(cid:82)(cid:91)(cid:76)(cid:80)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:36)(cid:79)(cid:74)(cid:82)(cid:85)(cid:76)(cid:87)(cid:75)(cid:80)(cid:86)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:48)(cid:56)(cid:47)(cid:55)(cid:44)(cid:58)(cid:36)(cid:60)(cid:3)(cid:38)(cid:56)(cid:55)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:3)(cid:23)(cid:27)
`Improved Approximation Algorithms for MULTIWAY CUT .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. . .
`.
`.
`. . .
`. . . . .
`. 48
`(cid:42)(cid:85)(cid:88)(cid:76)(cid:68)(cid:3)(cid:38)(cid:71)(cid:79)(cid:76)(cid:81)(cid:72)(cid:86)(cid:70)(cid:88)(cid:82)(cid:15)(cid:3)(cid:43)(cid:82)(cid:90)(cid:68)(cid:85)(cid:71)(cid:3)(cid:46)(cid:68)(cid:85)(cid:79)(cid:82)(cid:73)(cid:73)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:60)(cid:88)(cid:89)(cid:68)(cid:79)(cid:3)(cid:53)(cid:68)(cid:69)(cid:68)(cid:81)(cid:76)
`Gruia Cdlinescuo, Howard Karlofi’ and Yuval Rabani
`
`Session 2A
`(cid:54)(cid:72)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:21)(cid:36)
`(cid:36)(cid:3)(cid:41)(cid:85)(cid:68)(cid:80)(cid:72)(cid:90)(cid:82)(cid:85)(cid:78)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:41)(cid:68)(cid:86)(cid:87)(cid:3)(cid:52)(cid:88)(cid:68)(cid:81)(cid:87)(cid:88)(cid:80)(cid:3)(cid:48)(cid:72)(cid:70)(cid:75)(cid:68)(cid:81)(cid:76)(cid:70)(cid:68)(cid:79)(cid:3)(cid:36)(cid:79)(cid:74)(cid:82)(cid:85)(cid:76)(cid:87)(cid:75)(cid:80)(cid:86)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17) (cid:24)(cid:22)
`A Framework for Fast Quantum Mechanical Algorithms .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. . . .. 53
`Lov K. Gmver
`(cid:47)(cid:82)(cid:89)(cid:3)(cid:46)(cid:17)(cid:3)(cid:42)(cid:85)(cid:82)(cid:89)(cid:72)(cid:85)
`(cid:52)(cid:88)(cid:68)(cid:81)(cid:87)(cid:88)(cid:80)(cid:3)(cid:89)(cid:86)(cid:17)(cid:3)(cid:38)(cid:79)(cid:68)(cid:86)(cid:86)(cid:76)(cid:70)(cid:68)(cid:79)(cid:3)(cid:38)(cid:82)(cid:80)(cid:80)(cid:88)(cid:81)(cid:76)(cid:70)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:38)(cid:82)(cid:80)(cid:83)(cid:88)(cid:87)(cid:68)(cid:87)(cid:76)(cid:82)(cid:81)(cid:3)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:3)(cid:25)(cid:22)
`Quantum vs. Classical Communication and Computation . . . .
`.
`. . .
`.
`. . . . . . . . . . .
`.
`.
`.
`.
`.
`.
`.
`. . . .
`.
`.
`. .. 63
`(cid:43)(cid:68)(cid:85)(cid:85)(cid:92)(cid:3)(cid:37)(cid:88)(cid:75)(cid:85)(cid:80)(cid:68)(cid:81)(cid:15)(cid:3)(cid:53)(cid:76)(cid:70)(cid:75)(cid:68)(cid:85)(cid:71)(cid:3)(cid:38)(cid:79)(cid:72)(cid:89)(cid:72)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:36)(cid:89)(cid:76)(cid:3)(cid:58)(cid:76)(cid:74)(cid:71)(cid:72)(cid:85)(cid:86)(cid:82)(cid:81)
`Harry Buhrman, Richard Cleve and Avi Mgderson
`
`Session 2B
`(cid:54)(cid:72)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:21)(cid:37)
`(cid:41)(cid:76)(cid:81)(cid:71)(cid:76)(cid:81)(cid:74)(cid:3)(cid:48)(cid:68)(cid:91)(cid:76)(cid:80)(cid:88)(cid:80)(cid:3)(cid:41)(cid:79)(cid:82)(cid:90)(cid:86)(cid:3)(cid:76)(cid:81)(cid:3)(cid:54)(cid:76)(cid:80)(cid:83)(cid:79)(cid:72)(cid:3)(cid:56)(cid:81)(cid:71)(cid:76)(cid:85)(cid:72)(cid:70)(cid:87)(cid:72)(cid:71)(cid:3)(cid:42)(cid:85)(cid:68)(cid:83)(cid:75)(cid:86)(cid:3)(cid:76)(cid:86)(cid:3)(cid:40)(cid:68)(cid:86)(cid:76)(cid:72)(cid:85)(cid:3)(cid:55)(cid:75)(cid:68)(cid:81)(cid:3)(cid:37)(cid:76)(cid:83)(cid:68)(cid:85)(cid:87)(cid:76)(cid:87)(cid:72)(cid:3)(cid:48)(cid:68)(cid:87)(cid:70)(cid:75)(cid:76)(cid:81)(cid:74)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:25)(cid:28)
`Finding Maximum Flows in Simple Undirected Graphs is Easier Than Bipartite Matching . . .
`.
`.
`. . 69
`(cid:39)(cid:68)(cid:89)(cid:76)(cid:71)(cid:3)(cid:53)(cid:17)(cid:3)(cid:46)(cid:68)(cid:85)(cid:74)(cid:72)(cid:85)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:48)(cid:68)(cid:87)(cid:87)(cid:75)(cid:72)(cid:90)(cid:3)(cid:54)(cid:17)(cid:3)(cid:47)(cid:72)(cid:89)(cid:76)(cid:81)(cid:72)
`David R. Karger and Matthew S. Levine
`(cid:51)(cid:82)(cid:79)(cid:92)(cid:16)(cid:79)(cid:82)(cid:74)(cid:68)(cid:85)(cid:76)(cid:87)(cid:75)(cid:80)(cid:76)(cid:70)(cid:3)(cid:39)(cid:72)(cid:87)(cid:72)(cid:85)(cid:80)(cid:76)(cid:81)(cid:76)(cid:86)(cid:87)(cid:76)(cid:70)(cid:3)(cid:41)(cid:88)(cid:79)(cid:79)(cid:92)(cid:16)(cid:71)(cid:92)(cid:81)(cid:68)(cid:80)(cid:76)(cid:70)(cid:3)(cid:36)(cid:79)(cid:74)(cid:82)(cid:85)(cid:76)(cid:87)(cid:75)(cid:80)(cid:86)(cid:3)(cid:73)(cid:82)(cid:85)(cid:3)(cid:38)(cid:82)(cid:81)(cid:81)(cid:72)(cid:70)(cid:87)(cid:76)(cid:89)(cid:76)(cid:87)(cid:92)(cid:15)(cid:3)(cid:48)(cid:76)(cid:81)(cid:76)(cid:80)(cid:88)(cid:80)(cid:3)(cid:54)(cid:83)(cid:68)(cid:81)(cid:81)(cid:76)(cid:81)(cid:74)(cid:3)(cid:87)(cid:85)(cid:72)(cid:72)(cid:15)
`Poly-logarithmic Detenninistic Fully-dynamic Algorithms for Connectivity, Minimum Spanning tree,
`(cid:21)(cid:16)(cid:72)(cid:71)(cid:74)(cid:72)(cid:3)(cid:68)(cid:81)(cid:71)(cid:3)(cid:37)(cid:76)(cid:70)(cid:82)(cid:81)(cid:81)(cid:72)(cid:70)(cid:87)(cid:76)(cid:89)(cid:76)(cid:87)(cid:92)(cid:3)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17)(cid:17) (cid:3)(cid:26)(cid:28)
`2-edge and Biconnectivity . .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. . . .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`. . . . . . . . . .
`.
`.
`. . .
`.
`.
`.
`.
`.
`.
`.
`.
`. . .
`.
`.
`.
`.
`. 79
`(cid:45)(cid:68)(cid:70)(cid:82)(cid:69)(cid:3)(cid
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
