Publications

Recent Manuscripts

• On Fairness and Stability in Two-Sided Matchings
  G. Karni, G. N. Rothblum and G. Yona
  Innovations in Theoretical Computer Science conference (ITCS) 2022 (to appear)

Conferences and Journals (in reverse chronological order)

• Addressing bias in prediction models by improving subpopulation calibration
  N. Barda, G. Yona, G. N. Rothblum, P. Greenland, M. Leibowitz, R. Balicer, E. Bachmat and N. Dagan
  Journal of the American Medical Informatics Association (JAMIA) 2021
• On Prover-Efficient Public-Coin Emulation of Interactive Proofs
  G. Arnon and G. N. Rothblum
  Conference on Information-Theoretic Cryptography (ITC) 2021
• Multi-group Agnostic PAC Learnability
  G. N. Rothblum and G. Yona
  International Conference on Machine Learning (ICML) 2021
• Interactive Proofs for Verifying Machine Learning
  S. Goldwasser, G. N. Rothblum, J. Shafer and A. Yehudayoff
  Innovations in Theoretical Computer Science conference (ITCS) 2021
• Abstracting Fairness: Oracles, Metrics, and Interpretability
  C. Dwork, C. Ilvento, G. N. Rothblum and P. Sur
  Symposium on Foundations of Responsible Computing (FORC) 2020
• Batch Verification and Proofs of Proximity with Polylog Overhead
  G. N. Rothblum and R. D. Rothblum
  Theory of Cryptography Conference (TCC) 2020
• Batch Verification for Statistical Zero Knowledge Proofs
  I. Kaslasi, G. N. Rothblum, R. D. Rothblum, A. Sealfon and P. N. Vasudevan
  Theory of Cryptography Conference (TCC) 2020
• Worst-Case to Average-Case Reductions for Subclasses of P
  O. Goldreich and G. N. Rothblum
  Computational Complexity and Property Testing 2020
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
  O. Goldreich and G. N. Rothblum
  Computational Complexity and Property Testing 2020
• Preference-Informed Fairness
  P. Kim, A. Korolova, G. N. Rothblum and G. Yona
  Innovations in Theoretical Computer Science conference (ITCS) 2020
  ACM Conference on Fairness, Accountability, and Transparency (FAccT) 2020
• Incrementally Verifiable Computation via Incremental PCPs
  M. Naor, O. Paneth and G. N. Rothblum
  Theory of Cryptography Conference (TCC) 2019
• Learning from Outcomes: Evidence-Based Rankings
  Dwork, M. P. Kim, O. Reingold, G. N. Rothblum and G. Yona
  IEEE Symposium on Foundations of Computer Science (FOCS) 2019
• Finding a Nash Equilibrium is No Easier than Breaking Fiat-Shamir
  R. Choudhuri, P. Hubacek, C. Kamath, K. Pietrzak, A. Rosen and G. N. Rothblum
  ACM Symposium on Theory of Computing (STOC) 2019
• Fiat-Shamir: From Practice to Theory
  Canetti, Y. Chen, J. Holmgren, A. Lombardi, G. N. Rothblum, R. D. Rothblum and D. Wichs
  ACM Symposium on Theory of Computing (STOC) 2019
• Gentle Measurement of Quantum States and Differential Privacy
  S. Aaronson and G. N. Rothblum
  ACM Symposium on Theory of Computing (STOC) 2019
• Fine-grained Complexity Meets IP = PSPACE
  L. Chen, S. Goldwasser, K. Lyu, G. N. Rothblum and A. Rubinstein
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2019
• Fairness through Computationally-Bounded Awareness
  M. K. Kim, O. Reingold and G. N. Rothblum
  Conference on Neural Information Processing Systems (NIPS) 2018
• Counting t-Cliques: Worst-Case to Average-Case Reductions and Direct Interactive Proof Systems
  O. Goldreich and G. N. Rothblum
  IEEE Symposium on Foundations of Computer Science (FOCS) 2018
• Probably Approximately Metric-Fair Learning
  G. N. Rothblum and G. Yona
  International Conference on Machine Learning (ICML) 2018
• Calibration for the (Computationally-Identifiable) Masses
  Ú. Hébert-Johnson, M. P. Kim, O. Reingold and G. N. Rothblum
  International Conference on Machine Learning (ICML) 2018
  
• Composable and Versatile Privacy via Truncated CDP
  M. Bun, C. Dwork, G. N. Rothblum and T. Steinke
  ACM Symposium on Theory of Computing (STOC) 2018
• Efficient Batch Verification for UP
  O. Reingold, G. N. Rothblum and R. D. Rothblum
  Computational Complexity Conference (CCC) 2018
• Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets
  O. Goldreich and G. N. Rothblum
  Innovations in Theoretical Computer Science conference (ITCS) 2018
  
• On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-Interactive Arguments
  O. Paneth and G. N. Rothblum
  Theory of Cryptography Conference (TCC) 2017
  
• From Obfuscation to the Security of Fiat-Shamir for Proofs
  Y. T. Kalai, G. N. Rothblum and R.D. Rothblum
  International Cryptology Conference (CRYPTO) 2017
  
• Concentrated Differential Privacy
  C. Dwork and G. N. Rothblum
  Arxiv (2016)
• Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems
  C. Dwork, M. Naor, O. Reingold and G. N. Rothblum
  International Cryptology Conference (CRYPTO) 2016
  
• Constant-round interactive proofs for delegating computation
  O. Reingold, G. N. Rothblum and R. D. Rothblum
  ACM Symposium on Theory of Computing (STOC) 2016
  SIAM Journal on Computing, special issue for STOC 2016, by invitation
• Pure Differential Privacy for Rectangle Queries via Private Partitions
  C. Dwork, M. Naor, O. Reingold and G. N. Rothblum
  International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2015)
  
• Fast Pseudorandomness for Independence and Load Balancing
  R. Meka, O. Reingold, G. N. Rothblum and R. D. Rothblum
  International Colloquium on Automata, Languages, and Programming (ICALP) 2014
• Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
  Z. Brakerski and G. N. Rothblum
  Theory of Cryptography Conference (TCC) 2014
• Black-Box Obfuscation for d-CNFs
  Z. Brakerski and G. N. Rothblum
  Innovations in Theoretical Computer Science conference (ITCS) 2014
• Obfuscating Conjunctions
  Z. Brakerski and G. N. Rothblum
  International Cryptology Conference (CRYPTO) 2013
  By invitation, Journal of Cryptology 30(1): 289-320 (2017)
• Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
  G. N. Rothblum, S. Vadhan and A. Wigderson
  ACM Symposium on Theory of Computing (STOC) 2013
• How to Compute under AC⁰ Leakage without Secure Hardware
  G. N. Rothblum
  International Cryptology Conference (CRYPTO) 2012
• How to Compute in the Presence of Leakage
  S. Goldwasser and G. N. Rothblum
  IEEE Symposium on Foundations of Computer Science (FOCS) 2012
  By invitation, SIAM Journal on Computing 44(5): 1480-1549, special issue for FOCS 2012 (2015)
• Refereed Delegation of Computation
  R. Canetti, B. Riva and G. N. Rothblum
  Information Theoretic Security International Conference (ICITS) 2012 Information and Computation 226: 16-36, 2013
• Private Data Release via Learning Thresholds
  M. Hardt, G. N. Rothblum and R. A. Servedio
  ACM-SIAM Symposium on Discrete Algorithms (SODA) 2012
• Program Obfuscation with Leaky Hardware
  N. Bitansky, R. Canetti, S. Goldwasser, S. Halevi, Y. T. Kalai and G. N. Rothblum
  ASIACRYPT 2011
• Practical Delegation of Computation Using Multiple Servers
  R. Canetti, B. Riva and G. N. Rothblum
  ACM Conference on Computer and Communications Security 2011
• On Approximating the Entropy of Polynomial Mappings
  Z. Dvir, D. Gutfreund, G. N. Rothblum and S. Vadhan
  Symposium on Innovations in Computer Science (ICS) 2011
• A Multiplicative Weights Mechanism for Interactive Privacy-Preserving Data Analysis
  M. Hardt and G. N. Rothblum
  IEEE Symposium on Foundations of Computer Science (FOCS) 2010
• Boosting and Differential Privacy
  C. Dwork, G. N. Rothblum and S. Vadhan
  IEEE Symposium on Foundations of Computer Science (FOCS) 2010
• Securing Computation against Continual Leakage
  S. Goldwasser and G. N. Rothblum
  International Cryptology Conference (CRYPTO) 2010
• Differential Privacy under Continual Observation
  C. Dwork, M. Naor, T. Pitassi and G. N. Rothblum
  ACM Symposium on Theory of Computing (STOC) 2010
• Obfuscation of Hyperplane Membership
  R. Canetti, G. N. Rothblum and M. Varia
  Theory of Cryptography Conference (TCC) 2010
• Leakage-Resilient Signatures
  S. Faust, E. Kiltz, K. Pietrzak and G. N. Rothblum
  Theory of Cryptography Conference (TCC) 2010
• Pan-Private Streaming Algorithms
  C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum and S. Yekhanin
  Symposium on Innovations in Computer Science (ICS) 2010
• Are PCPs Inherent in Efficient Arguments?
  G. N. Rothblum and S. Vadhan
  IEEE Conference on Computational Complexity (CCC) 2009
  By invitation, Journal of Computational Complexity 19(2): 265-304, special issue for CCC 2009, 2010
• On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results
  C. Dwork, M. Naor, O. Reingold, G. N. Rothblum and S. Vadhan
  ACM Symposium on Theory of Computing (STOC) 2009
• Weak Verifiable Random Functions
  Z. Brakerski, S. Goldwasser, G. N. Rothblum and V. Vaikuntanathan
  Theory of Cryptography Conference (TCC) 2009
• How Efficient can Memory Checking Be?
  C. Dwork, M. Naor, G. N. Rothblum and V. Vaikuntanathan
  Theory of Cryptography Conference (TCC) 2009
• The Complexity of Local List Decoding
  D. Gutfreund and G. N. Rothblum
  International Workshop on Randomization and Computation (RANDOM) 2008
• One-Time Programs
  S. Goldwasser, Y. T. Kalai and G. N. Rothblum
  International Cryptology Conference (CRYPTO) 2008
• A (De)constructive Approach to Program Checking
  S. Goldwasser, D. Gutfreund, A. Healy, T. Kaufman and G. N. Rothblum
  ACM Symposium on Theory of Computing (STOC) 2008
• Delegating Computation: Interactive Proofs for Muggles
  S. Goldwasser, Y. T. Kalai and G. N. Rothblum
  ACM Symposium on Theory of Computing (STOC) 2008
  Journal of the ACM 62(4): 27:1-27:64 (2015)
• Verifying and Decoding in Constant Depth
  S. Goldwasser, D. Gutfreund, A. Healy, T. Kaufman and G. N. Rothblum
  ACM Symposium on Theory of Computing (STOC) 2007
  Full versions on Verifying and on Decoding
• Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles
  R. Gradwohl, M. Naor, B. Pinkas and G. N. Rothblum
  International Conference on Fun with Algorithms (FUN) 2007
  By invitation, Theory of Computing Systems 44(2): 245-268, special issue for FUN 2007, 2009
• Securely Obfuscating Re-Encryption
  S. Hohenberger, G. N. Rothblum, A. Shelat and V. Vaikuntanathan
  Theory of Cryptography Conference (TCC) 2007
  By Invitation, Journal of Cryptology 24(4): 694-719, 2011
• On Best-Possible Obfuscation
  S. Goldwasser and G. N. Rothblum
  Theory of Cryptography Conference (TCC) 2007
  By invitation, Journal of Cryptology 27(3): 480-505, 2014
• Learning to Impersonate
  M. Naor and G. N. Rothblum
  International Conference on Machine Learning (ICML) 2006
• The Complexity of Online Memory Checking
  M. Naor and G. N. Rothblum
  IEEE Symposium on Foundations of Computer Science (FOCS) 2005
  Journal of the ACM 56(1), 2009

Thesis

“Delegating Computation Reliably: Paradigms and Constructions”
Ph.D. Thesis, MIT, 2009
Supervised by Shafi Goldwasser