<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div dir="ltr">
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"
id="gmail-docs-internal-guid-27f3a02f-d801-f3f4-c53a-fad0dbbb235e"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Please
forward to all interested parties/mailing lists.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">New
York Area Theory Day</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Organized
by: IBM/NYU/Columbia</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Friday,
December 1, 2017</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">The
Theory Day will be held at Courant Institute of Mathematical
Sciences,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">New
York University, 251 Mercer Street, Auditorium 109, New York.</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Directions:
<a href="http://www.cims.nyu.edu/direct.html">http://www.cims.nyu.edu/direct.html</a></span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Apart
from invited distinguished speakers, we also have short talk</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">sessions
in which junior researchers will present some of their
research.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">PROGRAM</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
9:30 - 10:00 Coffee and bagels</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">10:00
- 10:55 Prof. Christos Papadimitriou</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
A Computer Scientist Thinks about the Brain</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">10:55
- 11:15 Coffee break</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">11:15
- 12:05 Short talks:</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
Shay Solomon, Ilya Razenshteyn, Sepideh Mahabadi</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">12:05
- 2:00 Lunch break</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
2:00 - 2:55 Dr. Ilan Komargodski</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
White-Box vs. Black-Box Complexity of Search Problems:</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Ramsey
and Graph Property Testing</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
2:55 - 3:15 Short talk: Sandro Coretti</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
3:15 - 3:35 Coffee break</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
3:35 - 3:55 Short talk: Greg Bodwin</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
3:55 - 4:50 Prof. Virginia Vassilevska Williams</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
Fine-Grained Complexity of Problems in P</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
5:00 - 7:00 Follow-up social</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">For
directions, please see <a
href="http://www.cims.nyu.edu/direct.html">http://www.cims.nyu.edu/direct.html</a></span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">To
subscribe to our mailing list, follow instructions at</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
<a href="http://www.cs.nyu.edu/mailman/listinfo/theory-ny">http://www.cs.nyu.edu/mailman/listinfo/theory-ny</a></span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Organizers:
Alex Andoni (<a href="mailto:andoni@cs.columbia.edu">andoni@cs.columbia.edu</a>);</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Yevgeniy
Dodis (<a href="mailto:dodis@cs.nyu.edu">dodis@cs.nyu.edu</a>);</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Krzysztof
Onak (<a href="mailto:konak@us.ibm.com">konak@us.ibm.com</a>)</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">LONG
TALKS </span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Christos
H. Papadimitriou (Columbia University)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
A Computer Scientist Thinks about the Brain</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
Understanding the ways in which the Brain gives rise to the
Mind</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">(memory,
behavior, cognition, intelligence, language) is the most
challenging</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">problem
facing science today. As the answer seems likely to be at
least partly</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">computational,
computer scientists should work on this problem. Using a</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">simplified
model of Hebbian plasticity and employing random graph theory
and</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Bernoulli
approximations we reproduce a form of association between
memories</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">recently
observed experimentally in humans. We discuss several
implications and</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">extensions.
(Joint work with W. Maass and S. Vempala).</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Ilan
Komargodski (Cornell Tech)</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
White-Box vs. Black-Box Complexity of Search Problems: Ramsey
and Graph</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Property
Testing</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
Ramsey theory assures us that in any graph there is a clique
or</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">independent
set of a certain size, roughly logarithmic in the graph size.
But</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">how
difficult is it to find the clique or independent set? This
problem is in</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">TFNP,
the class of search problems with guaranteed solutions. If
the graph is</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">given
explicitly, then it is possible to do so while examining a
linear number</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">of
edges. If the graph is given by a black-box, where to figure
out whether a</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">certain
edge exists the box should be queried, then a large number of
queries</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">must
be issued.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">1)
What if one is given a program or circuit ("white-box") for
computing the</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
existence of an edge. Does the search problem remain hard?</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">2)
Can we generically translate all TFNP black-box hardness into
white-box</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
hardness?</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">3)
Does the problem remain hard if the black-box instance is
small?</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">We
will answer all of these questions and discuss related
questions in the</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">setting
of property testing.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Joint
work with Moni Naor and Eylon Yogev.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Virginia
Vassilevska Williams (MIT)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
Fine-Grained Complexity of Problems in P</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
A central goal of algorithmic research is to determine how
fast</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">computational
problems can be solved in the worst case. Theorems from
complexity</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">theory
state that there are problems that, on inputs of size n, can
be solved in</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">t(n)
time but not in t(n)^{1-eps} time for eps>0. The main
challenge is to</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">determine
where in this hierarchy various natural and important problems
lie.</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Throughout
the years, many ingenious algorithmic techniques have been
developed</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">and
applied to obtain blazingly fast algorithms for many problems.
Nevertheless,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">for
many other central problems, the best known running times are
essentially</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">those
of their classical algorithms from the 1950s and 1960s.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Unconditional
lower bounds seem very difficult to obtain, and so practically
all</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">known
time lower bounds are conditional. For years, the main tool
for proving</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">hardness
of computational problems have been NP-hardness reductions,
basing</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">hardness
on P\neq NP. However, when we care about the exact running
time (as</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">opposed
to merely polynomial vs non-polynomial), NP-hardness is not
applicable,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">especially
if the problem is already solvable in polynomial time. In
recent</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">years,
a new theory has been developed, based on ``fine-grained
reductions''</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">that
focus on exact running times. Mimicking NP-hardness, the
approach is to (1)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">select
a key problem X that is conjectured to require essentially
t(n) time for</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">some
t, and (2) reduce X in a fine-grained way to many important
problems. This</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">approach
has led to the discovery of many meaningful relationships
between</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">problems,
and even sometimes to equivalence classes.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">The
main key problems used to base hardness on have been: the 3SUM
problem, the</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">CNF-SAT
problem (based on the Strong Exponential TIme Hypothesis
(SETH)) and the</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">All
Pairs Shortest Paths Problem. Research on SETH-based lower
bounds has</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">flourished
in particular in recent years showing that the classical
algorithms</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">are
optimal for problems such as Approximate Diameter, Edit
Distance, Frechet</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Distance,
Longest Common Subsequence etc.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">In
this talk I will give an overview of the current progress in
this area of</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">study,
and will highlight some exciting new developments.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">SHORT
TALKS </span><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span><span style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">
</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Shay
Solomon (IBM Research)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
Fully Dynamic Maximal Matching</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
Graph matching is one of the most well-studied problems in</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">combinatorial
optimization, with a reach plethora of applications.
Nevertheless,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">until
recently little was known about this problem in real-life
dynamic</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">networks,
which aim to model the constantly changing physical world.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Focusing
on the maximal matching problem, there is a trivial linear
time</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">algorithm
for computing such a matching in static networks, which
naturally</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">translates
into an algorithm with a constant amortized cost in the
incremental</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">case.
In this talk I will discuss some of the challenges that we
overcame to</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">obtain
a constant amortized cost algorithm in the fully dynamic case.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Ilya
Razenshteyn (Columbia)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
Practical Data-Dependent Metric Compression with Provable
Guarantees</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
How well can one compress a dataset of points from a
high-dimensional</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">space
while preserving pairwise distances? Indyk and Wagner have
recently</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">obtained
almost optimal bounds for this problem, but their construction
(based</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">on
hierarchical clustering) is not practical. In this talk, I
will show a new</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">practical,
quadtree-based compression scheme, whose provable performance</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">essentially
matches that of the result of Indyk and Wagner.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">In
addition to the theoretical results, we will see experimental
comparison of</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">the
new scheme and Product Quantization (PQ)--one of the most
popular heuristics</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">for
distance-preserving compression--on several datasets. Unlike
PQ and other</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">heuristics
that rely on the clusterability of the dataset, the new
algorithm</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">ends
up being more robust.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">The
talk is based on a joint work with Piotr Indyk and Tal Wagner.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Sepideh
Mahabadi (Columbia)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
Set Cover in Sub-linear Time</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
We study the classic set cover problem from the perspective of</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">sub-linear
algorithms. Given access to a collection of $m$ sets over $n$</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">elements
in the query model, we show that sub-linear algorithms derived
from</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">existing
techniques have almost tight query complexities.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">On
one hand, first we show that an adaptation of streaming
algorithms to the</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">sub-linear
query model returns an $\alpha$-approximate cover using
$\tilde</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">O(m(n/k)^{1/(\alpha-1)}
+ nk)$ queries to the input, where $k$ denotes the value</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">of
a minimum set cover. We then complement this upper bound by
proving that for</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">lower
values of $k$, the required number of queries is $\tilde</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Omega(m(n/k)^{1/(2\alpha)})$,
even for estimating the optimal cover size.</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Moreover,
we prove that even checking whether a given collection of sets
covers</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">all
the elements would require $\Omega(nk)$ queries. These two
lower bounds</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">provide
strong evidence that the upper bound is almost tight for
certain values</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">of
the parameter $k$. On the other hand, we show that this bound
is not optimal</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">for
larger values of the parameter $k$, as there exists a</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">$(1+\eps)$-approximation
algorithm with $\tilde O(mn/k\eps^2)$ queries. We show</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">that
this bound is essentially tight for sufficiently small
constant $\eps$, by</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">establishing
a lower bound of $\tilde Omega(mn/k)$ query complexity.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">This
is a joint work with Piotr Indyk, Ronitt Rubinfeld, Ali
Vakilian, and Anak</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Yodpinyanee.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Sandro
Coretti (New York University)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
Random Oracles and Non-Uniformity</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
Hash functions are ubiquitous in cryptography. They are widely
used in</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">practice
to build one-way functions (OWFs), collision-resistant hash
functions</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">(CRHFs),
pseudorandom functions/generators (PRFs/PRGs), message
authentication</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">codes
(MACs), etc. Moreover, they are often used together with other</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">computational
assumptions to prove the security of higher-level
applications,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">such
as Fiat-Shamir heuristics for signature schemes,
full-domain-hash</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">signatures,
or OAEP encryption, among many others.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">The
security of such schemes is commonly analyzed in the
random-oracle model</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">(ROM),
in which the hash function is modeled as a truly random
function that can</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">be
queried by an attacker at a bounded number of points. The
traditional ROM,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">however,
does not account for the fact that a non-uniform attacker may
obtain</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">arbitrary
advice about the hash function H before attacking a
construction. As a</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">result,
bounds derived in the ROM do not accurately reflect security
against</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">such
attackers.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">To
remedy this situation, Unruh (CRYPTO ’07) considered the
auxiliary-input ROM</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">(AI-ROM),
in which an attacker may obtain (a bounded amount of)
arbitrary</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">leakage
about the random oracle before attacking a cryptographic
scheme. In this</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">talk
we discuss significant improvements to Unruh's presampling
technique,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">which,
intuitively, allows a leaky random oracle to be replaced by
one that is</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">adversarially
fixed on a subset of the coordinates but uniformly random</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">otherwise.
We also show how this improved presampling leads to better and
easily</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">derivable
AI-ROM security bounds for a number of cryptographic
applications. We</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">conclude
by noting that in several cases (such as OWFs, PRGs, and
CRHFs) there</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">are
still significant gaps between the derived bounds and the best
attacks,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">leaving
interesting open problems.</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">================================================================================</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Greg
Bodwin (MIT)</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Title:
Compressing Graphs While Preserving Their Distances</span></p>
<br>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span
style="font-size:10pt;font-family:"Courier
New";color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Abstract:
TBA</span></p>
<br>
</div>
</body>
</html>