"Fast approximation algorithms for the diameter and radius of sparse graphs"
Time: 9:30 AM
Location: Core 433
Abstract: Arnab will lead discussion on Fast approximation algorithms for the diameter and radius of
sparse graphs (http://www.cs.berkeley.edu/~virgi/diam.pdf) by Liam Roddity and Virginia Vassilevska Williams.
Wednesday, April 17th
Yixin Xu, Rutgers
"Lee-Yang theorems and the complexity of computing averages"
Time: 9:30 AM
Location: Core 433
Abstract: Yixin will continue discussion on Lee-Yang theorems and the complexity of computing averages (http://arxiv.org/abs/1211.2376) by Alistair Sinclair and Piyush Srivastava.
Wednesday, April 10th
Yixin Xu, Rutgers
"Lee-Yang theorems and the complexity of computing averages"
Time: 9:30 AM
Location: Core 433
Abstract: Yixin will lead discussion on Lee-Yang theorems and the complexity of computing averages (http://arxiv.org/abs/1211.2376) by Alistair Sinclair and Piyush Srivastava.
Wednesday, April 3rd
Raghu Meka, Rutgers
"Approximating Bin Packing within > > O(log OPT * log log OPT) bins"
Time: 9:30 AM
Location: Core 433
Abstract: Raghu will lead discussion on "Approximating Bin Packing within > > O(log OPT * log log OPT) bins" (http://arxiv.org/abs/1301.4010) by Thomos Rothvoss.
Wednesday, March 27th
Swastik Kopparty, Rutgers
"On the list decodability of random linear codes with large error rate"
Time: 9:30 AM
Location: Core 433
Abstract: Swastik will continue to lead discussion on the aforementioned paper by Mary Wootters (http://arxiv.org/abs/1302.2261).
Wednesday, March 13th
Tim Naumovitz, Rutgers
"A {huge o(n)} monotonicity tester for Boolean functions over the hypercube"
Time: 9:30 AM
Location: Core 433
Abstract: We will be doing a group reading of "A {huge o(n)} monotonicity tester for Boolean functions over the hypercube" by Chakrabarty and Seshadhri (http://eccc.hpi-web.de/report/2013/029/)
Wednesday, March 6th
Luke Friedman, Rutgers
"Natural Proofs Versus Derandomization"
Time: 9:30 AM
Location: Core 433
Abstract: Luke will lead discussion on "Natural Proofs Versus Derandomization", http://www.stanford.edu/~rrwill/natural-f.pdf by Ryan Williams.
Wednesday, February 20th
Shubhangi Saraf, Rutgers
"Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs"
Time: 9:30 AM
Location: Core 433
Abstract: This week Shubhangi will lead discussion on "Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs" (http://www.cs.technion.ac.il/~shpilka/publications/ForbesShpilka12.pdf) by Forbes and Shpilka. No, we didn't do this last week. We switched things around last week in order to discuss a recent new discovery in the area of crossing out the number four and replacing it with three.
Wednesday, February 13th
Shubhangi Saraf, Rutgers
"Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs"
Time: 9:30 AM
Location: Core 433
Abstract: This week Shubhangi will lead discussion on "Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs" (http://www.cs.technion.ac.il/~shpilka/publications/ForbesShpilka12.pdf) by Forbes and Shpilka.
Wednesday, February 6th
Aleksandar Nikolov, Rutgers
"The Approximate Rank of a Matrix and its Algorithmic Applications"
Time: 9:30 AM
Location: Core 433
Abstract: Alex will lead discussion on "The Approximate Rank of a Matrix and its Algorithmic Applications",
http://eccc.hpi-web.de/report/2012/169/ by Alon and Vempala.
Wednesday, January 30th
Eric Allender, Rutgers University
"Hierarchies against Sublinear Advice"
Time: 9:30 AM
Location: Core 433
Abstract: Eric will lead discussion on "Hierarchies against Sublinear Advice" by Fortnow and Santhanam. A link to the paper is available in the seminar email.
Wednesday, January 23rd
Tim Naumovitz, Rutgers
"On the Complexity of Finding Narrow Proofs"
Time: 9:30 AM
Location: Core 433
Abstract: I'll start us off by leading the discussion on: Christoph Berkholz, "On the Complexity of Finding Narrow Proofs", http://arxiv.org/pdf/1204.0775v2.pdf. The refreshments are not for us.
This page was last updated on April 15, 2013 at 12:22 pm and is maintained by webmaster@math.rutgers.edu.
For questions regarding courses and/or special permission, please contact
mclausen@math.rutgers.edu.
