Publications (31)
Approximate degree, secret sharing, and concentration phenomena
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1
On the Power of Statistical Zero Knowledge
Adam Bouland, Lijie Chen, Dhiraj Holden +2
Distribution-Independent Reliable Learning
Varun Kanade, Justin Thaler
Practical Verified Computation with Streaming Interactive Proofs
Graham Cormode, Michael Mitzenmacher, Justin Thaler
Verifying Computations with Streaming Interactive Proofs
Graham Cormode, Justin Thaler, Ke Yi
Hierarchical Heavy Hitters with the Space Saving Algorithm
Michael Mitzenmacher, Thomas Steinke, Justin Thaler
Determining Tournament Payout Structures for Daily Fantasy Sports
Christopher Musco, Maxim Sviridenko, Justin Thaler
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Mark Bun, Justin Thaler
On the Zero-Error Capacity Threshold for Deletion Channels
Ian A. Kash, Michael Mitzenmacher, Justin Thaler +1
Annotations for Sparse Data Streams
Amit Chakrabarti, Graham Cormode, Navin Goyal +1
Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps
Michael T. Goodrich, Daniel S. Hirschberg, Michael Mitzenmacher +1
Time-Optimal Interactive Proofs for Circuit Evaluation
Justin Thaler
Streaming Graph Computations with a Helpful Advisor
Graham Cormode, Michael Mitzenmacher, Justin Thaler
Reliably Learning the ReLU in Polynomial Time
Surbhi Goel, Varun Kanade, Adam Klivans +1
Variable Selection is Hard
Dean Foster, Howard Karloff, Justin Thaler
Stream Verification
Justin Thaler
A High-Performance Algorithm for Identifying Frequent Items in Data Streams
Daniel Anderson, Pryce Bevan, Kevin Lang +3
Space Lower Bounds for Itemset Frequency Sketches
Edo Liberty, Michael Mitzenmacher, Justin Thaler +1
Verifiable Computation with Massively Parallel Interactive Proofs
Justin Thaler, Mike Roberts, Michael Mitzenmacher +1
Sign-Rank Can Increase Under Intersection
Mark Bun, Nikhil S. Mande, Justin Thaler
Faster Algorithms for Privately Releasing Marginals
Justin Thaler, Jonathan Ullman, Salil Vadhan
Continuous Time Channels with Interference
Ioana Ivan, Michael Mitzenmacher, Justin Thaler +1
Parallel Peeling Algorithms
Jiayang Jiang, Michael Mitzenmacher, Justin Thaler
Semi-Streaming Algorithms for Annotated Graph Streams
Justin Thaler
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
Mark Bun, Justin Thaler
External-Memory Multimaps
Elaine Angelino, Michael T. Goodrich, Michael Mitzenmacher +1
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
Mark Bun, Justin Thaler
Streaming Verification in Data Analysis
Samira Daruki, Justin Thaler, Suresh Venkatasubramanian
Faster Private Release of Marginals on Small Databases
Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman +1
A Framework for Estimating Stream Expression Cardinalities
Anirban Dasgupta, Kevin Lang, Lee Rhodes +1
Dual Polynomials for Collision and Element Distinctness
Mark Bun, Justin Thaler