Now showing items 1-4 of 4

    • Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs 

      Steinke, Thomas Alexander; Vadhan, Salil P.; Wan, Andrew (Dagstuhl Publishing, 2014)
      We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ). The previously best known seed ...
    • Pseudorandomness for Regular Branching Programs via Fourier Analysis 

      Reingold, Omer; Steinke, Thomas Alexander; Vadhan, Salil P. (Springer Berlin Heidelberg, 2013)
      We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is \(O(log^2 n)\), where n is the length ...
    • Robust Traceability from Trace Amounts 

      Dwork, Cynthia; Smith, Adam; Steinke, Thomas Alexander; Ullman, Jonathan; Vadhan, Salil P. (2015)
      The privacy risks inherent in the release of a large number of summary statistics were illustrated by Homer et al. (PLoS Genetics, 2008), who considered the case of 1-way marginals of SNP allele frequencies obtained in a ...
    • Upper and Lower Bounds for Privacy and Adaptivity in Algorithmic Data Analysis 

      Steinke, Thomas Alexander (2016-08-03)
      The increasing collection and use of sensitive personal data raises important privacy concerns. Another concern arising from the use of data in empirical sciences is the danger of producing results that are not statistically ...