Algorithms and Complexity Seminar
 |
Ankit Sharma: Multiway Cut Monday, November 25, 2013 - 4:00pm to 5:00pm Multiway cut is a generalization of the min-cut problem to one with more than two terminals. |
|
|
Mohammad Bavarian: Beyond XOR Games: Information causality, Szemerédi-Trotter and Algebraic Variants of CHSH Wednesday, December 11, 2013 - 4:00pm to 5:00pm CHSH_q is the following simple two-player game: two parties are given x,y in F_q uniformly at random, and each must produce an output a,b in F_q$ without communicating to the other. The players objective is to maximize the probability that their outputs satisfy a+b=xy in F_q. |
|
|
Daniel Kane: Pseudorandom Generators for Polynomial Threshold Functions Monday, November 18, 2013 - 4:00pm to 5:00pm We study several developments in the construction of explicit pseudorandom generators for polynomial threshold functions, with particular emphasis on a recent result producing a seed length subpolynomial in the error parameter. |
|
|
Thomas Steinke: Pseudorandomness for Regular Branching Programs via Fourier Analysis Wednesday, December 4, 2013 - 4:00pm to 5:00pm We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is O(log2n), where n is the length of the branching program. |
|
|
Michael Forbes : Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order Thursday, October 31, 2013 - 4:00pm to 5:00pm It is an important open question whether we can derandomize small space computation, that is, whether RL equals L. One version of this question is to construct pseudorandom generators for read-once oblivious branching programs. |
|
|
Ilya Razenshteyn: Beyond Locality-Sensitive Hashing Wednesday, November 20, 2013 - 4:00pm to 5:00pm We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in Rd, our algorithm achieves Oc(dnρ) query time and Oc(n1+ρ+nd) space, where ρ≤7/(8c2)+O(1/c3)+oc(1). |
|
|
Ludwig Schmidt: Approximation-Tolerant Model-Based Compressive Sensing Wednesday, November 13, 2013 - 4:00pm to 5:00pm The goal of sparse recovery is to recover a k-sparse signal x from (possibly noisy) linear measurements of the form y=Ax, where A describes the measurement process. |
|
|
Siu On Chan: Approximate Constraint Satisfaction Requires Large LP Relaxations Wednesday, October 16, 2013 - 4:00pm to 5:00pm We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. |
|
|
Huy L. Nguyen: Cutting corners cheaply, or how to remove Steiner points Wednesday, October 9, 2013 - 4:00pm to 5:00pm Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which resolves in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006). |
|
|
Private Analysis of Graphs Wednesday, October 2, 2013 - 4:00pm to 5:00pm We discuss algorithms for the private analysis of network data. Such algorithms work on data sets that contain sensitive relationship information (for example, romantic ties). |
Pages
