(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)
`
`Apple 1109
`
`

`
`(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 1939
`
`(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 Machinery
`(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 Broadway
`New York New York l0036
`(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)
`Copyright
`I998 by the Association for Computing Machinery. lnc.(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)
`Permission to make digital or hard copies of all or pan oflhis 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 tnade or distributed for profit or cointnercial 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 the full citation on the first page. To copy
`(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)
`othenvisc. 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)
`reqmres prior specific permission and/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)
`Request permission to republish from: Publications Dept. ACM. inc. Fax +l (212)
`(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-048! or <pennissions(a2acm.org>. For other copying ofarticlcs 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'thc first or last page. copying 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 in the code is paid through the Copyrigln Clearance Center. 222
`Rosewood Drive. Danvers. MA (H923.
`(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: ll-X‘)7‘)|-‘J62-9
`(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 Ortlcr Department
`PO Box I I4 H
`(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)
`Church 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 ltt2X(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: I-8()(t-3-I2-(»(»2(»
`(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)
`+|-ZIZ-626-(l5(l(l
`(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)
`(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)
`(all other countries)
`Fax: +|-2l2-9-H-l3l8
`(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: aciiipiibs((t1aciii.org
`
`ACM Order Number: sozwxo
`(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)
`
`4
`(cid:13)
`
`

`
`(cid:25)(cid:76)(cid:79)(cid:63)
`(cid:20)(cid:24)(cid:17)(cid:65)
`(cid:80)
`
`(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:3)
`
`(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 IA
`(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 . . . . . . . .
`.
`.
`.
`.
`. . . . . . . .
`.
`.
`.
`.
`.
`. . . . .
`. . . . .
`1
`(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)
`Don‘: Aharonov, 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 Karlofl’ and Yuval Rabani
`
`(cid:54)(cid:72)(cid:86)(cid:86)(cid:76)(cid:82)(cid:81)(cid:3)(cid:21)(cid:36)
`Session 2A
`(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 Aw’ Wigderson
`
`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 Deterministic Fully-dynamic Algorithms for Connectivity, Minimum Sparming 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:43)(cid:82)(cid:79)(cid:80)(cid:15)(cid:3)(cid:46)(