default search action
Justin Thaler
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c53]Alexander R. Block, Zhiyong Fang, Jonathan Katz, Justin Thaler, Hendrik Waldner, Yupeng Zhang:
Field-Agnostic SNARKs from Expand-Accumulate Codes. CRYPTO (10) 2024: 276-307 - [c52]Arasu Arun, Srinath T. V. Setty, Justin Thaler:
Jolt: SNARKs for Virtual Machines via Lookups. EUROCRYPT (6) 2024: 3-33 - [c51]Srinath T. V. Setty, Justin Thaler, Riad S. Wahby:
Unlocking the Lookup Singularity with Lasso. EUROCRYPT (6) 2024: 180-209 - [i81]Quang Dao, Justin Thaler:
Constraint-Packing and the Sum-Check Protocol over Binary Tower Fields. IACR Cryptol. ePrint Arch. 2024: 1038 (2024) - [i80]Suyash Bagad, Yuval Domb, Justin Thaler:
The Sum-Check Protocol over Fields of Small Characteristic. IACR Cryptol. ePrint Arch. 2024: 1046 (2024) - [i79]Quang Dao, Justin Thaler:
More Optimizations to Sum-Check Proving. IACR Cryptol. ePrint Arch. 2024: 1210 (2024) - 2023
- [j21]Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, Pavel Veselý:
Relative Error Streaming Quantiles. J. ACM 70(5): 30:1-30:48 (2023) - [c50]Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, Michal Zajac:
Fiat-Shamir Security of FRI and Related SNARKs. ASIACRYPT (2) 2023: 3-40 - [c49]Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby:
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS. CRYPTO (2) 2023: 193-226 - [c48]Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, Justin Thaler:
sfTestudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup. LATINCRYPT 2023: 331-351 - [i78]Srinath T. V. Setty, Justin Thaler, Riad S. Wahby:
Customizable constraint systems for succinct arguments. IACR Cryptol. ePrint Arch. 2023: 552 (2023) - [i77]Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, Justin Thaler:
Testudo: Linear Time Prover SNARKs with Constant Size Proofs and Square Root Size Universal Setup. IACR Cryptol. ePrint Arch. 2023: 961 (2023) - [i76]Alexander R. Block, Albert Garreta, Jonathan Katz, Justin Thaler, Pratyush Ranjan Tiwari, Michal Zajac:
Fiat-Shamir Security of FRI and Related SNARKs. IACR Cryptol. ePrint Arch. 2023: 1071 (2023) - [i75]Srinath T. V. Setty, Justin Thaler, Riad S. Wahby:
Unlocking the lookup singularity with Lasso. IACR Cryptol. ePrint Arch. 2023: 1216 (2023) - [i74]Arasu Arun, Srinath T. V. Setty, Justin Thaler:
Jolt: SNARKs for Virtual Machines via Lookups. IACR Cryptol. ePrint Arch. 2023: 1217 (2023) - [i73]Srinath T. V. Setty, Justin Thaler:
BabySpartan: Lasso-based SNARK for non-uniform computation. IACR Cryptol. ePrint Arch. 2023: 1799 (2023) - 2022
- [j20]Justin Thaler:
Proofs, Arguments, and Zero-Knowledge. Found. Trends Priv. Secur. 4(2-4): 117-660 (2022) - [j19]Mark Bun, Justin Thaler:
Approximate Degree in Classical and Quantum Computing. Found. Trends Theor. Comput. Sci. 15(3-4): 229-423 (2022) - [j18]Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler:
Quantum Proofs of Proximity. Quantum 6: 834 (2022) - [j17]Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, Pavel Veselý:
Relative Error Streaming Quantiles. SIGMOD Rec. 51(1): 69-76 (2022) - [c47]Charlie Dickens, Justin Thaler, Daniel Ting:
Order-Invariant Cardinality Estimators Are Differentially Private. NeurIPS 2022 - [i72]Charlie Dickens, Justin Thaler, Daniel Ting:
(Nearly) All Cardinality Estimators Are Differentially Private. CoRR abs/2203.15400 (2022) - 2021
- [j16]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Quantum 5: 543 (2021) - [j15]Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. Theory Comput. 17: 1-46 (2021) - [j14]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-rank Can Increase under Intersection. ACM Trans. Comput. Theory 13(4): 24:1-24:17 (2021) - [c46]Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, Pavel Veselý:
Relative Error Streaming Quantiles. PODS 2021: 96-108 - [i71]Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler:
Quantum Proofs of Proximity. CoRR abs/2105.03697 (2021) - [i70]Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler:
Quantum Proofs of Proximity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i69]Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby:
Linear-time zero-knowledge SNARKs for R1CS. IACR Cryptol. ePrint Arch. 2021: 30 (2021) - [i68]Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, Riad S. Wahby:
Brakedown: Linear-time and post-quantum SNARKs for R1CS. IACR Cryptol. ePrint Arch. 2021: 1043 (2021) - 2020
- [j13]Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On the Power of Statistical Zero Knowledge. SIAM J. Comput. 49(4) (2020) - [j12]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. SIAM J. Comput. 49(4) (2020) - [j11]Mark Bun, Justin Thaler:
Guest Column: Approximate Degree in Classical and Quantum Computing. SIGACT News 51(4): 48-72 (2020) - [j10]Mark Bun, Robin Kothari, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. 16: 1-71 (2020) - [c45]Amit Chakrabarti, Prantar Ghosh, Justin Thaler:
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. APPROX-RANDOM 2020: 22:1-22:23 - [c44]Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler:
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CCC 2020: 7:1-7:47 - [c43]Justin Thaler, Woong Shin, Steven Roberts, James H. Rogers, Todd Rosedahl:
Hybrid Approach to HPC Cluster Telemetry and Hardware Log Analytics. HPEC 2020: 1-7 - [c42]Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler:
Ad Hoc Multi-Input Functional Encryption. ITCS 2020: 40:1-40:41 - [c41]Nikhil S. Mande, Justin Thaler, Shuchen Zhu:
Improved Approximate Degree Bounds for k-Distinctness. TQC 2020: 2:1-2:22 - [i67]Nikhil S. Mande, Justin Thaler, Shuchen Zhu:
Improved Approximate Degree Bounds For k-distinctness. CoRR abs/2002.08389 (2020) - [i66]Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, Pavel Veselý:
Relative Error Streaming Quantiles. CoRR abs/2004.01668 (2020) - [i65]Amit Chakrabarti, Prantar Ghosh, Justin Thaler:
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. CoRR abs/2007.03039 (2020) - [i64]Amit Chakrabarti, Prantar Ghosh, Justin Thaler:
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. Electron. Colloquium Comput. Complex. TR20 (2020) - [i63]Nikhil S. Mande, Justin Thaler, Shuchen Zhu:
Improved Approximate Degree Bounds For $k$-distinctness. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j9]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
Verifiable Stream Computation and Arthur-Merlin Communication. SIAM J. Comput. 48(4): 1265-1299 (2019) - [c40]Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. APPROX-RANDOM 2019: 55:1-55:16 - [c39]Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson:
Approximate Degree, Secret Sharing, and Concentration Phenomena. APPROX-RANDOM 2019: 71:1-71:21 - [c38]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-Rank Can Increase Under Intersection. ICALP 2019: 30:1-30:14 - [c37]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. SODA 2019: 662-678 - [i62]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-Rank Can Increase Under Intersection. CoRR abs/1903.00544 (2019) - [i61]Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler:
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR abs/1904.08914 (2019) - [i60]Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson:
Approximate degree, secret sharing, and concentration phenomena. CoRR abs/1906.00326 (2019) - [i59]Alexander A. Sherstov, Justin Thaler:
Vanishing-Error Approximate Degree and QMA Complexity. CoRR abs/1909.07498 (2019) - [i58]Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler:
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. TR19 (2019) - [i57]Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson:
Approximate degree, secret sharing, and concentration phenomena. Electron. Colloquium Comput. Complex. TR19 (2019) - [i56]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-Rank Can Increase Under Intersection. Electron. Colloquium Comput. Complex. TR19 (2019) - [i55]Alexander A. Sherstov, Justin Thaler:
Vanishing-Error Approximate Degree and QMA Complexity. Electron. Colloquium Comput. Complex. TR19 (2019) - [i54]Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler:
Ad Hoc Multi-Input Functional Encryption. IACR Cryptol. ePrint Arch. 2019: 356 (2019) - 2018
- [c36]Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. APPROX-RANDOM 2018: 35:1-35:18 - [c35]Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, Michael Walfish:
Doubly-Efficient zkSNARKs Without Trusted Setup. IEEE Symposium on Security and Privacy 2018: 926-943 - [c34]Mark Bun, Robin Kothari, Justin Thaler:
The polynomial method strikes back: tight quantum query bounds via dual polynomials. STOC 2018: 297-310 - [i53]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. CoRR abs/1809.02254 (2018) - [i52]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Electron. Colloquium Comput. Complex. TR18 (2018) - [i51]Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c33]Christopher Musco, Maxim Sviridenko, Justin Thaler:
Determining Tournament Payout Structures for Daily Fantasy Sports. ALENEX 2017: 172-184 - [c32]Riad S. Wahby, Ye Ji, Andrew J. Blumberg, Abhi Shelat, Justin Thaler, Michael Walfish, Thomas Wies:
Full Accounting for Verifiable Outsourcing. CCS 2017: 2071-2086 - [c31]Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler:
Reliably Learning the ReLU in Polynomial Time. COLT 2017: 1004-1042 - [c30]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. FOCS 2017: 1-12 - [c29]Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On the Power of Statistical Zero Knowledge. FOCS 2017: 708-719 - [c28]Daniel Anderson, Pryce Bevan, Kevin J. Lang, Edo Liberty, Lee Rhodes, Justin Thaler:
A high-performance algorithm for identifying frequent items in data streams. Internet Measurement Conference 2017: 268-282 - [i50]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. CoRR abs/1703.05784 (2017) - [i49]Daniel Anderson, Pryce Bevan, Kevin J. Lang, Edo Liberty, Lee Rhodes, Justin Thaler:
A High-Performance Algorithm for Identifying Frequent Items in Data Streams. CoRR abs/1705.07001 (2017) - [i48]Mark Bun, Robin Kothari, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. CoRR abs/1710.09079 (2017) - [i47]Mark Bun, Robin Kothari, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Electron. Colloquium Comput. Complex. TR17 (2017) - [i46]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. Electron. Colloquium Comput. Complex. TR17 (2017) - [i45]Riad S. Wahby, Ye Ji, Andrew J. Blumberg, Abhi Shelat, Justin Thaler, Michael Walfish, Thomas Wies:
Full accounting for verifiable outsourcing. IACR Cryptol. ePrint Arch. 2017: 242 (2017) - [i44]Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, Michael Walfish:
Doubly-efficient zkSNARKs without trusted setup. IACR Cryptol. ePrint Arch. 2017: 1132 (2017) - 2016
- [j8]Michael Mitzenmacher, Justin Thaler:
Technical Perspective: Catching lies (and mistakes) in offloaded computation. Commun. ACM 59(2): 102 (2016) - [j7]Mark Bun, Justin Thaler:
Dual Polynomials for Collision and Element Distinctness. Theory Comput. 12(1): 1-34 (2016) - [j6]Jiayang Jiang, Michael Mitzenmacher, Justin Thaler:
Parallel Peeling Algorithms. ACM Trans. Parallel Comput. 3(1): 7:1-7:27 (2016) - [c27]Justin Thaler:
Lower Bounds for the Approximate Degree of Block-Composed Functions. ICALP 2016: 17:1-17:15 - [c26]Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC^0. ICALP 2016: 37:1-37:14 - [c25]Justin Thaler:
Semi-Streaming Algorithms for Annotated Graph Streams. ICALP 2016: 59:1-59:14 - [c24]Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, Justin Thaler:
A Framework for Estimating Stream Expression Cardinalities. ICDT 2016: 6:1-6:17 - [c23]Edo Liberty, Michael Mitzenmacher, Justin Thaler, Jonathan R. Ullman:
Space Lower Bounds for Itemset Frequency Sketches. PODS 2016: 441-454 - [r1]Justin Thaler:
Data Stream Verification. Encyclopedia of Algorithms 2016: 494-499 - [i43]Christopher Musco, Maxim Sviridenko, Justin Thaler:
Determining Tournament Payout Structures for Daily Fantasy Sports. CoRR abs/1601.04203 (2016) - [i42]Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On SZK and PP. CoRR abs/1609.02888 (2016) - [i41]Surbhi Goel, Varun Kanade, Adam R. Klivans, Justin Thaler:
Reliably Learning the ReLU in Polynomial Time. CoRR abs/1611.10258 (2016) - [i40]Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On SZK and PP. Electron. Colloquium Comput. Complex. TR16 (2016) - [i39]Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC0. Electron. Colloquium Comput. Complex. TR16 (2016) - [i38]Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j5]Mark Bun, Justin Thaler:
Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput. 243: 2-25 (2015) - [c22]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
Verifiable Stream Computation and Arthur-Merlin Communication. CCC 2015: 217-243 - [c21]Dean P. Foster, Howard J. Karloff, Justin Thaler:
Variable Selection is Hard. COLT 2015: 696-709 - [c20]Mark Bun, Justin Thaler:
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. ICALP (1) 2015: 268-280 - [c19]Samira Daruki, Justin Thaler, Suresh Venkatasubramanian:
Streaming Verification in Data Analysis. ISAAC 2015: 715-726 - [i37]Mark Bun, Justin Thaler:
Dual Polynomials for Collision and Element Distinctness. CoRR abs/1503.07261 (2015) - [i36]Justin Thaler:
Stream Verification. CoRR abs/1507.04188 (2015) - [i35]Samira Daruki, Justin Thaler, Suresh Venkatasubramanian:
Streaming Verification in Data Analysis. CoRR abs/1509.05514 (2015) - [i34]Anirban Dasgupta, Kevin J. Lang, Lee Rhodes, Justin Thaler:
A Framework for Estimating Stream Expression Cardinalities. CoRR abs/1510.01455 (2015) - [i33]Mark Bun, Justin Thaler:
Dual Polynomials for Collision and Element Distinctness. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j4]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler:
Annotations in Data Streams. ACM Trans. Algorithms 11(1): 7:1-7:30 (2014) - [c18]Varun Kanade, Justin Thaler:
Distribution-independent Reliable Learning. COLT 2014: 3-24 - [c17]Karthekeyan Chandrasekaran, Justin Thaler, Jonathan R. Ullman, Andrew Wan:
Faster private release of marginals on small databases. ITCS 2014: 387-402 - [c16]Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler:
Annotations for Sparse Data Streams. SODA 2014: 687-706 - [c15]Jiayang Jiang, Michael Mitzenmacher, Justin Thaler:
Parallel peeling algorithms. SPAA 2014: 319-330 - [i32]Varun Kanade, Justin Thaler:
Distribution-Independent Reliable Learning. CoRR abs/1402.5164 (2014) - [i31]Justin Thaler:
Semi-Streaming Algorithms for Annotated Graph Streams. CoRR abs/1407.3462 (2014) - [i30]Edo Liberty, Michael Mitzenmacher, Justin Thaler:
Space Lower Bounds for Itemset Frequency Sketches. CoRR abs/1407.3740 (2014) - [i29]Dean P. Foster, Howard J. Karloff, Justin Thaler:
Variable Selection is Hard. CoRR abs/1412.4832 (2014) - [i28]Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
Verifiable Stream Computation and Arthur-Merlin Communication. Electron. Colloquium Comput. Complex. TR14 (2014) - [i27]Justin Thaler:
Semi-Streaming Algorithms for Annotated Graph Streams. Electron. Colloquium Comput. Complex. TR14 (2014) - [i26]Justin Thaler:
Lower Bounds for the Approximate Degree of Block-Composed Functions. Electron. Colloquium Comput. Complex. TR14 (2014) - [i25]Andrew J. Blumberg, Justin Thaler, Victor Vu, Michael Walfish:
Verifiable computation using multiple provers. IACR Cryptol. ePrint Arch. 2014: 846 (2014) - 2013
- [j3]Graham Cormode, Michael Mitzenmacher, Justin Thaler:
Streaming Graph Computations with a Helpful Advisor. Algorithmica 65(2): 409-442 (2013) - [j2]Elaine Angelino, Michael T. Goodrich, Michael Mitzenmacher, Justin Thaler:
External-Memory Multimaps. Algorithmica 67(1): 23-48 (2013) - [c14]Justin Thaler:
Time-Optimal Interactive Proofs for Circuit Evaluation. CRYPTO (2) 2013: 71-89 - [c13]Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. ICALP (1) 2013: 303-314 - [i24]Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. CoRR abs/1302.6191 (2013) - [i23]Jiayang Jiang, Michael Mitzenmacher, Justin Thaler:
Parallel Peeling Algorithms. CoRR abs/1302.7014 (2013) - [i22]Karthekeyan Chandrasekaran, Justin Thaler, Jonathan R. Ullman, Andrew Wan:
Faster Private Release of Marginals on Small Databases. CoRR abs/1304.3754 (2013) - [i21]Justin Thaler:
Time-Optimal Interactive Proofs for Circuit Evaluation. CoRR abs/1304.3812 (2013) - [i20]Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler:
Annotations for Sparse Data Streams. CoRR abs/1304.3816 (2013) - [i19]Mark Bun,