<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<pre>INSTITUTE FOR ADVANCED STUDY
School of Mathematics
Princeton, NJ 08540
Theoretical Computer Science/Discrete Math Seminars
Week of October 23, 2017
--------------
To view mathematics in titles and abstracts, please click on the talk's link.
--------------
Monday, October 23
Computer Science/Discrete Mathematics Seminar I
Topic: A nearly optimal lower bound on the approximate degree of AC$^0$
Speaker: Mark Bun, Princeton University
Time/Room: 11:00am - 12:15pm/S-101
Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=128781">http://www.math.ias.edu/seminars/abstract?event=128781</a>
Tuesday, October 24
Computer Science/Discrete Mathematics Seminar II
Topic: On the strength of comparison queries
Speaker: Shay Moran, University of California, San Diego; Member, School of Mathematics
Time/Room: 10:30am - 12:30pm/S-101
Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=129013">http://www.math.ias.edu/seminars/abstract?event=129013</a>
</pre>
1 A nearly optimal lower bound on the approximate degree of AC$^0$
<br>
Mark Bun
<br>
<br>
<p>The approximate degree of a Boolean function $f$ is the least
degree of a real polynomial that approximates $f$ pointwise to
error at most $1/3$. For any constant $\delta > 0$, we exhibit
an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$.
This improves over the best previous lower bound of
$\Omega(n^{2/3})$ due to Aaronson and Shi, and nearly matches the
trivial upper bound of $n$ that holds for any function.</p>
<p>Our lower bound follows from a new hardness amplification
theorem, which shows how to increase the approximate degree of a
given function while preserving its computability by
constant-depth circuits. I will also describe several applications
of our results in communication complexity and cryptography.</p>
<p>This is joint work with Justin Thaler and is available at <a>https://eccc.weizmann.ac.il/report/2017/051/</a>.</p>
<a href="http://www.math.ias.edu/seminars/abstract?event=128781">http://www.math.ias.edu/seminars/abstract?event=128781</a><br>
<br>
2 On the strength of comparison queries
<br>
Shay Moran
<br>
<br>
<p>Joint work with Daniel Kane (UCSD) and Shachar Lovett (UCSD)</p>
<p>We construct near optimal linear decision trees for a variety of
decision problems in combinatorics and discrete geometry.</p>
<p>For example, for any constant $k$, we construct linear decision
trees that solve the $k$-SUM problem on $n$ elements using $O(n
\log^2 n)$ linear queries. This settles a problem studied by
[Meyer auf der Heide ’84, Meiser ‘93, Erickson ‘95, Ailon and
Chazelle ‘05, Gronlund and Pettie '14, Gold and Sharir ’15,
Cardinal et al '15, Ezra and Sharir ’16] and others.</p>
<p>The queries we use are comparison queries, which compare the sums
of two $k$-subsets. When viewed as linear queries, comparison
queries are $2k$-sparse and have only $\{-1,0,1\}$ coefficients.
We give similar constructions for sorting sumsets $A+B$ and for
deciding the SUBSET-SUM problem, both with optimal number of
queries, up to poly-logarithmic terms.</p>
<p>Our constructions are based on the notion of ``inference
dimension", recently introduced by the authors in the context of
active classification with comparison queries. This can be viewed
as another contribution to the fruitful link between machine
learning and discrete geometry, which goes back to the discovery
of the VC dimension.</p>
<a href="http://www.math.ias.edu/seminars/abstract?event=129013">http://www.math.ias.edu/seminars/abstract?event=129013</a><br>
<br>
Computer Science/Discrete Math Seminars can be found on our web
page:<br>
<br>
<a href="http://www.math.ias.edu/csdm">http://www.math.ias.edu/csdm</a><br>
<a href="http://www.math.ias.edu">http://www.math.ias.edu</a>
</body>
</html>