# Justin Thaler

According to our database

Collaborative distances:

^{1}, Justin Thaler authored at least 54 papers between 2010 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Ad Hoc Multi-Input Functional Encryption.

IACR Cryptology ePrint Archive, 2019

Vanishing-Error Approximate Degree and QMA Complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Sign-Rank Can Increase Under Intersection.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Approximate degree, secret sharing, and concentration phenomena.

Electronic Colloquium on Computational Complexity (ECCC), 2019

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

Electronic Colloquium on Computational Complexity (ECCC), 2019

2018

The Large-Error Approximate Degree of AC

^{0}.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Quantum algorithms and approximating polynomials for composed functions with shared inputs.

Electronic Colloquium on Computational Complexity (ECCC), 2018

2017

Doubly-efficient zkSNARKs without trusted setup.

IACR Cryptology ePrint Archive, 2017

Full accounting for verifiable outsourcing.

IACR Cryptology ePrint Archive, 2017

A Nearly Optimal Lower Bound on the Approximate Degree of AC

^{0}.
Electronic Colloquium on Computational Complexity (ECCC), 2017

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials.

Electronic Colloquium on Computational Complexity (ECCC), 2017

A high-performance algorithm for identifying frequent items in data streams.

Proceedings of the 2017 Internet Measurement Conference, 2017

On the Power of Statistical Zero Knowledge.

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Reliably Learning the ReLU in Polynomial Time.

Proceedings of the 30th Conference on Learning Theory, 2017

Determining Tournament Payout Structures for Daily Fantasy Sports.

Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016

Data Stream Verification.

Encyclopedia of Algorithms, 2016

Parallel Peeling Algorithms.

TOPC, 2016

Dual Polynomials for Collision and Element Distinctness.

Theory of Computing, 2016

Approximate Degree and the Complexity of Depth Three Circuits.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Improved Bounds on the Sign-Rank of AC

^{0}.
Electronic Colloquium on Computational Complexity (ECCC), 2016

On SZK and PP.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Technical Perspective: Catching lies (and mistakes) in offloaded computation.

Commun. ACM, 2016

Space Lower Bounds for Itemset Frequency Sketches.

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

A Framework for Estimating Stream Expression Cardinalities.

Proceedings of the 19th International Conference on Database Theory, 2016

Improved Bounds on the Sign-Rank of AC^0.

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Stream Verification.

CoRR, 2015

Streaming Verification in Data Analysis.

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Variable Selection is Hard.

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Annotations in Data Streams.

ACM Trans. Algorithms, 2014

Verifiable computation using multiple provers.

IACR Cryptology ePrint Archive, 2014

Lower Bounds for the Approximate Degree of Block-Composed Functions.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Semi-Streaming Algorithms for Annotated Graph Streams.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Verifiable Stream Computation and Arthur-Merlin Communication.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Space Lower Bounds for Itemset Frequency Sketches.

CoRR, 2014

Annotations for Sparse Data Streams.

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Faster private release of marginals on small databases.

Proceedings of the Innovations in Theoretical Computer Science, 2014

Distribution-independent Reliable Learning.

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Time-Optimal Interactive Proofs for Circuit Evaluation.

IACR Cryptology ePrint Archive, 2013

On Interactivity in Arthur-Merlin Communication and Stream Computation.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Streaming Graph Computations with a Helpful Advisor.

Algorithmica, 2013

External-Memory Multimaps.

Algorithmica, 2013

2012

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.

Proceedings of the COLT 2012, 2012

Cache-Oblivious Dictionaries and Multimaps with Negligible Failure Probability.

Proceedings of the Design and Analysis of Algorithms, 2012

Continuous time channels with interference.

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

Practical verified computation with streaming interactive proofs.

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Faster Algorithms for Privately Releasing Marginals.

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Verifiable Computation with Massively Parallel Interactive Proofs.

Proceedings of the 4th USENIX Workshop on Hot Topics in Cloud Computing, 2012

Peeling arguments and double hashing.

Proceedings of the 50th Annual Allerton Conference on Communication, 2012

Hierarchical Heavy Hitters with the Space Saving Algorithm.

Proceedings of the 14th Meeting on Algorithm Engineering & Experiments, 2012

2011

Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps

CoRR, 2011

On the zero-error capacity threshold for deletion channels.

Proceedings of the Information Theory and Applications Workshop, 2011

2010

Verifying Computations with Streaming Interactive Proofs.

Electronic Colloquium on Computational Complexity (ECCC), 2010