September 24

Add to Calendar 2019-09-24 16:00:00 2019-09-24 17:00:00 America/New_York László Végh: A Strongly Polynomial Algorithm for Linear Exchange Markets Abstract: In this talk, I will present the first strongly polynomial algorithm for computing an equilibrium in exchange markets with linear utilities. The exchange market model has been extensively studied since its introduction by Walras in 1874. Our starting point is the previous weakly polynomial combinatorial algorithm by Duan and Mehlhorn. We use a variant of this algorithm to gradually reveal new variables that are in the support of every equilibrium. A key subroutine used for re-initializing this algorithm reduces to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time. This turns out to be good enough to make the overall algorithm run in strongly polynomial time.This is based on joint work with Jugal Garg. Kiva/G449 Belfer

November 05

Add to Calendar 2019-11-05 16:00:00 2019-11-05 17:00:00 America/New_York Anindya De: Junta correlation is testable. Abstract: A Boolean function f on the n-dimensional hypercube is saidto be a k-junta if it is dependent only on some k coordinates of theinput. These functions have been widely studied in the context ofPCPs, learning theory and property testing. In particular, a flagshipresult in property testing is that k-juntas can be tested with\tilde{O}(k) queries -- i.e., there is an algorithm which when givena black box to f, makes only \tilde{O}(k) queries and decides betweenthe following two cases:1. f is a k-junta.2. f is at least 0.01 far from every k-junta g in Hamming distance.Surprisingly, the query complexity is completely independent of theambient dimension n. In this work, we achieve the same qualitativeguarantee for the noise tolerant version of this problem. Inparticular, we give a 2^k query algorithm to distinguish between thefollowing two cases.1. f is 0.48-close to some k-junta.2. f is at least 0.49 far from every k-junta.The algorithm and its proof of correctness are simple and modularemploying some classical tools like "random restrictions" withelementary properties of the noise operator on the cube.Joint work with Elchanan Mossel and Joe Neeman. Patil Kiva G449 Belfer