Profile cover photo
Profile photo
TCS+
597 followers -
An online seminar series in theoretical computer science, accessible to the widest possible audience, and ensuring a carbon-free dissemination of ideas across the globe.
An online seminar series in theoretical computer science, accessible to the widest possible audience, and ensuring a carbon-free dissemination of ideas across the globe.

597 followers
About
Posts

Post has attachment
Dear TCS+ followers,

A new semester of TCS+ is starting! Our first talk of the year will be given by Zeev Dvir next Wednesday, January 21st, at 1pm EST (details below). This is also the last talk we will announce on the TCS+ page. For further announcements, please subscribe to our mailing list subscribe to our mailing list at http://www.cs.nyu.edu/mailman/listinfo/tcsplus_announce or refer to the TCS+ website https://sites.google.com/site/plustcs/

We hope to see you all on Wednesday!

-------------------------------
Speaker: Zeev Dvir (Princeton University)
Title: 2-Server PIR with sub-polynomial communication
Date: January 21st, 1pm EST

Abstract: 
A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. In this work we construct a 1-round 2-server PIR with total communication cost O(n^sqrt(log log n/log n)). This improves over the currently known 2-server protocols which require O(n^(1/3)) communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives.

Joint work with Sivakanth Gopi (Princeton University). [arXiV abs/1407.6692]
Add a comment...

Post has attachment
Dear TCS+ followers,

Our next talk will take place this coming Wednesday, December 3th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Omri Weinstein from Princeton will speak about "Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis" (abstract below).

[Note the speaker change: due to unforeseeable circumstances Omri Weinstein will give the talk instead of Mark Braverman as previously announced] 

Please sign up on the online form at live seat reservation | plustcs if you wish to join the talk as a group.

** Please remember to subscribe to our mailing list at http://www.cs.nyu.edu/mailman/listinfo/tcsplus_announce to receive further announcements.

** The most current information will always be on our website at plustcs

Hoping to see you all there,

The organizers

-------------------------------
Speaker: Omri Weinstein (CMU)
Title: Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis

Abstract: The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game initiated a quest for finding approximate Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory. We study the computational complexity of finding an \eps-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an epsilon-approximate Nash equilibrium with good social welfare in a two player game and many variants of this problem is at least as hard as finding a planted clique of size O(log n) in the random graph g(n,1/2).

We show that any polynomial time algorithm that finds an \eps-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi. Specifically, it would imply a 2^O(\sqrt{n}) algorithm for SAT.

Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem. Our key tool is a reduction from the PCP machinery to finding Nash equilibrium via free games, the framework introduced in the recent work by Aaronson, Impagliazzo and Moshkovitz. Techniques developed in the process may be useful for replacing planted clique hardness with ETH-hardness in other applications.

Based on joint work with Mark Braverman and Young Kun Ko 
Add a comment...

Post has attachment
Dear TCS+ followers,

Our next talk will take place next Wednesday, November 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Bernhard Haeupler from CMU will speak about "Coding for Interactive Communication Made Communication Efficient and Easy (or "How to make conversations robust to noise.")" (abstract below).

Please sign up on the online form at live seat reservation | plustcs if you wish to join the talk as a group.

** Please remember to subscribe to our mailing list at http://www.cs.nyu.edu/mailman/listinfo/tcsplus_announce to receive further announcements.

** The most current information will always be on our website at plustcs

Hoping to see you all there,

The organizers

-------------------------------
Speaker: Bernhard Haeupler (CMU)
Title: Coding for Interactive Communication Made Communication Efficient and Easy (or "How to make conversations robust to noise.")

Abstract: Abstract: Interactive coding schemes add redundancy to any interactive protocol (=conversation) such that it can be reliably performed over a noisy channel which corrupts any eps fraction of the transmitted symbols.

The fact that such coding schemes even exist is a surprising result of Schulman. His and most subsequent coding schemes achieve this feat by using tree-codes, intricate structures with no known efficient construction. This leads to even more complex protocols if computational efficiency is desired. The biggest drawback however is that all these schemes introduce large unspecified constant factor overheads in their communication and thus have tiny communication rates.

This talk will introduce an new, extremely simple, and natural coding scheme that removes all these complications. The protocol essentially consist of both parties having their original conversation as-is (no coding at all!!), interspersed only by short exchanges of hash values. When hash values do not match, the parties backtrack. We feel the protocol gives the simplest explanation for how and why interactive coding schemes for adversarial noise are possible. Our coding scheme furthermore achieves a communication rate of 1 - Theta(sqrt{eps log log 1/eps}) making it the first communication efficient coding scheme against adversarial noise. Interestingly, its communication rate even outperforms the rate for random noise of [Kol, Raz, STOC13] and, despite its odd form, is conjectured to be optimal. 
Add a comment...

Post has attachment
Please remember that we moved away from google+. To watch the talk of Thomas Rotvoss (or any other talk) live, please go to livetalk | plustcs
Add a comment...

Post has attachment
Dear TCS+ followers,

Our next talk will take place this coming Wednesday, November 5th at
*note the special time, one hour later than usual*
2:00 PM Eastern Time (11:00 AM Pacific Time, 20:00 Central European Time, 19:00 UTC). Thomas Rothvoss from University of Washington will speak about "Constructive discrepancy minimization for convex sets" (abstract below).

Please sign up on the online form at live seat reservation | plustcs if you wish to join the talk as a group.

** Please remember to subscribe to our mailing list at http://www.cs.nyu.edu/mailman/listinfo/tcsplus_announce to receive further announcements.

** The most current information will always be on our website at plustcs

Hoping to see you all there,

The organizers

-------------------------------
Speaker: Thomas Rothvoss (University of Washington)
Title: Constructive discrepancy minimization for convex sets

Abstract: A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1/2). Recent exciting work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett-Meka algorithm finds a half integral point in any "large enough" polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets.
We show that for any symmetric convex set K with measure at least exp(-n/500), the following algorithm finds a point y in K \cap [-1,1]^n with Omega(n) coordinates in {-1,+1}:
(1) take a random Gaussian vector x; (2) compute the point y in K \cap [-1,1]^n that is closest to x. (3) return y. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a Theorem of Giannopoulos. 
Add a comment...

Post has attachment
Add a comment...

Post has attachment
This is a reminder that the live stream for tomorrow's TCS+ talk by Christos Papadimitriou will appear directly on our webpage here: livetalk | plustcs. Please tune in starting 1pm EST.

All those who requested seats via the Doodle poll should have received a link to the hangout. We still have one seat left: if you're interested, please sign up here https://doodle.com/cgb45af3ufxtm534.
Add a comment...

Post has attachment
* Important announcement *
(See below for info on next talk)

TCS+ is going to going to slowly shift away from the use of Google+, which has proven unreliable. The following changes will take place progressively over the coming months:

1) Talk announcements will take place exclusively through our mailing list  tcsplus_announce@cs.nyu.edu. To receive upcoming talk announcements you need to subscribe to the list at http://www.cs.nyu.edu/mailman/listinfo/tcsplus_announce.
Please encourage anyone you know and may be interested to subscribe. We will soon stop announcing talks here. 

2) Reservations for online, in-hangout seats will take place via a doodle poll, the link to which will be included in the email announcing the talk (see below for the link for next week's talk). 

3) The talks will still take place using Google hangouts. For those watching the stream from "outside", the talk will be accessible from the tcsplus page at livetalk | plustcs

4) As a reminder, the google calendar for user plustcs@gmail.com contains updated information on upcoming talks. You can view the calendar on our website plustcs, and at this link: https://www.google.com/calendar/embed?src=plustcs%40gmail.com&ctz=America/New_York.

We hope these changes will streamline the process for everyone: you will only need to:
i) Watch this list for announcements
ii) Participate in the doodle poll if you would like a live seat
ii) If you have a live seat, watch the talk from the hangout at the url that will be emailed to you. If you are watching the YouTube stream, go to livetalk | plustcs at the scheduled time for the talk. 

* Next talk *

Join us for the next TCS+ talk! The talk will be given by Christos Papadimitriou, next Wednesday, October 22th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). 

The talk will be streamed live here: livetalk | plustcs  
Please sign up on the doodle poll at https://doodle.com/cgb45af3ufxtm534 if you wish to join the talk as a group. We will invite you into the hangout 15 minutes ahead of time so that we can make sure everything is working properly. Priority will be given to larger groups. 
 
We have a group limit of 12 spots, which is enough in most cases. So, don't be shy in requesting a seat! 
 
Speaker: Christos Papadimitriou
Affiliation: UC Berkeley
 
Title: Satisfiability and Evolution

Abstract: Consider the following thought experiment:  a random population of truth assignments of a Boolean function F with n variables reproduces with recombination, where satisfying truth assignments have a small fitness advantage (that is, they are slightly more likely than nonsatisfying ones to reach adulthood and reproduction).  Recombination means that the offspring picks the value of each variable from either parent.  Will satisfaction eventually become ubiquitous in the population?   In polynomially many generations, and with polynomially large population (by "polynomial" we mean polynomial in n and the inverse initial probability of satisfaction)?  And if so, would this result tell us anything informative about the way in which complex features depending on many genes emerge in a species?
Add a comment...

Post has attachment
The youtube link for todays talk by Mary Wootters is here:

TCS+ talk: Mary Wootters
Add a comment...

Post has attachment
Join us for the next TCS+ talk! The talk will be given by Mary Wootters, next Wednesday, October 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). 
 
Please leave a comment below if you plan to join as a group. We will invite you into the hangout 15 minutes ahead of time so that we can make sure everything is working properly. Priority will be given to larger groups. 
 
We have a group limit of 12 spots, which is enough in most cases. So, don't be shy in requesting a seat! 
 
Speaker: Mary Wootters
Affiliation: Carnegie Mellon
 
Title: List-decodability of structured random codes

Abstract: In the list-decoding problem, a sender (Alice) sends a message to a receiver (Bob) over a noisy channel, and Bob's job is to come up with a short list of messages with the guarantee that Alice's true message appears in the list.  It turns out that Alice and Bob can succeed even when nearly all of the symbols that Alice sends to Bob are corrupted.  It is known (and not hard to see) that a completely random code will achieve this, and it is also known (and much harder) that there are explicit codes which achieve this.  In this talk, we'll explore the middle-ground of structured random codes: for example, random linear codes, or Reed-Solomon codes with random evaluation points.  Our main result is that if you start with any q-ary code with sufficiently good distance and randomly puncture it, then with high probability, you get a code that is list-decodable up to a 1 - 1/q - epsilon fraction of errors, with near-optimal rate and list sizes.  Our results imply that "most" Reed-Solomon codes are list-decodable beyond the Johnson bound; whether or not such codes even existed was previously open.  Our results also imply improved bounds on the list-decodability of random linear codes over large alphabets.  This is joint work with Atri Rudra.
Add a comment...
Wait while more posts are being loaded