[iasmath-seminars] Theoretical Computer Science/Discrete Math Seminars -- Week of October 23, 2017

[Anthony Pulido]

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:	http://www.math.ias.edu/seminars/abstract?event=128781



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:	http://www.math.ias.edu/seminars/abstract?event=129013

1 A nearly optimal lower bound on the approximate degree of AC$^0$
    Mark Bun

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.

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.

This is joint work with Justin Thaler and is available at 
https://eccc.weizmann.ac.il/report/2017/051/.

http://www.math.ias.edu/seminars/abstract?event=128781

2 On the strength of comparison queries
    Shay Moran

Joint work with Daniel Kane (UCSD) and Shachar Lovett (UCSD)

We construct near optimal linear decision trees for a variety of 
decision problems in combinatorics and discrete geometry.

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.

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.

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.

http://www.math.ias.edu/seminars/abstract?event=129013

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/iasmathsemo/attachments/20171019/4e7c2697/attachment.html>