Publications

This page lists publications by members of our group.

2012

• Trinh Huynh, Jakob Nordström: On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity. STOC 2012. [ETH]. Full version upcoming.

2011

• Chandan Dubey, Thomas Holenstein: Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle.  APPROX 2011.  Full version: [arXiv:1106.2619].
• Thomas Holenstein, Renato Renner: On the randomness of independent experiments. IEEE Transactions on Information Theory 57(4): 1865-1871 (2011). [arXiv:cs/0608007].
• Thomas Holenstein, Robin Künzler, Stefano Tessaro: Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited.  STOC 2011.  Full version: [arXiv:1011.1264].
• Thomas Holenstein, Grant Schoenebeck: General Hardness Amplification of Predicates and Puzzles.  TCC 2011.  Full version: [arXiv:1002.3534], [TCC 2011 slides].
• Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer: Subsampling Semidefinite Programs and Max-Cut on the Sphere. SODA 2011.  Full version: [arXiv:0911.5526].

2010

• Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil Vadhan, Hoeteck Wee: Universal one-way hash functions via inaccessible entropy, Eurocrypt 2010, [IACR eprint 2010/120].
  

2009

• Thomas Holenstein: Parallel Repetition: Simplification and the No-Signaling Case, Theory of Computing vol. 5, no.8.  Preliminary version at STOC 2007. [ToC]
  
• Iftach Haitner, Thomas Holenstein: On the (im)possibility of Key-Dependent Encryption.  TCC 2009. [IACR eprint 2008/164].
• Robin Künzler: Are the Random Oracle and the Ideal Cipher Models Equivalent? Master's thesis, ETH Zurich, Switzerland, 2009. [ETH]
  

2008

• Liad Blumrosen, Thomas Holenstein: Posted prices vs. negotiations: an asymptotic analysis.  EC 2008. [Microsoft].
  
• Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, Udi Wieder: Trace reconstruction with constant deletion probability and related results. SODA 2008. [ACM]
  

2006

• Thomas Holenstein: Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness.  TCC 2006. [ETH]
• Thomas Holenstein: Strengthening Key Agreement using Hard-Core Sets, PhD Thesis.  [ETH]
  

2005

• Thomas Holenstein, Renato Renner: One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption, CRYPTO 2005. [ETH]
• Thomas Holenstein: Key agreement from weak bit agreement, STOC 2005. [ETH]

2004

• Thomas Holenstein, Ueli Maurer, Johan Sjödin: Complete Classification of Bilinear Hard-Core Functions, CRYPTO 2004.  [ETH]
• Matthias Fitzi, Thomas Holenstein, Jürg Wullschleger: Multi-party Computation with Hybrid Security. EUROCRYPT 2004.  [ETH]

2003

• Matthias Fitzi, Martin Hirt, Thomas Holenstein, Jürg Wullschleger: Two-Threshold Broadcast and Detectable Multi-party Computation.  EUROCRYPT 2003.  [ETH]

2002

• Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein, Adam Smith: Detectable byzantine agreement secure against faulty majorities.  PODC 2002.  [ETH]