| Publication | Date of Publication | Type |
|---|
| On correlation bounds against polynomials | 2024-11-19 | Paper |
| New sampling lower bounds via the separator | 2024-11-19 | Paper |
| Affine extractors and AC0-parity | 2024-08-22 | Paper |
| Efficient resilient functions | 2024-05-14 | Paper |
| scientific article; zbMATH DE number 7829312 (Why is no real title available?) | 2024-04-09 | Paper |
scientific article; zbMATH DE number 7829348 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
scientific article; zbMATH DE number 7768398 (Why is no real title available?)
(available as arXiv preprint) | 2023-11-20 | Paper |
Approximate degree, weight, and indistinguishability
ACM Transactions on Computation Theory | 2022-09-24 | Paper |
Pseudorandom bits and lower bounds for randomized Turing machines
Theory of Computing | 2022-07-26 | Paper |
| Quasirandom groups enjoy interleaved mixing | 2022-06-19 | Paper |
| Average-case rigidity lower bounds | 2022-03-21 | Paper |
AC0 unpredictability
ACM Transactions on Computation Theory | 2022-03-14 | Paper |
Revisiting frequency moment estimation in random order streams
(available as arXiv preprint) | 2021-07-28 | Paper |
How to Store a Random Walk
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
More on bounded independence plus noise: pseudorandom generators for read-once polynomials
Theory of Computing | 2020-12-17 | Paper |
| Bounded independence plus noise fools products | 2020-05-26 | Paper |
Sampling lower bounds: Boolean average-case and permutations
SIAM Journal on Computing | 2020-02-20 | Paper |
Lower bounds for data structures with space close to maximum imply circuit lower bounds
Theory of Computing | 2020-02-12 | Paper |
Constant-error pseudorandomness proofs from hardness require majority
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
Bounded independence versus symmetric tests
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
The coin problem for product tests
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Quadratic Maps Are Hard to Sample
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
On the complexity of information spreading in dynamic networks
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
The communication complexity of addition
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Interleaved Group Products
SIAM Journal on Computing | 2019-05-07 | Paper |
Local expanders
Computational Complexity | 2018-08-03 | Paper |
Substitution-permutation networks, pseudorandom functions, and natural proofs
Journal of the ACM | 2018-08-02 | Paper |
Local reduction
Information and Computation | 2018-06-14 | Paper |
Bounded independence plus noise fools products
SIAM Journal on Computing | 2018-05-18 | Paper |
| Bounded independence vs. moduli | 2018-04-19 | Paper |
| On randomness extraction in \({\mathcal{AC}}^0\) | 2018-01-24 | Paper |
Some limitations of the sum of small-bias distributions
Theory of Computing | 2018-01-10 | Paper |
Block-symmetric polynomials correlate with parity better than symmetric
Computational Complexity | 2017-10-18 | Paper |
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
The communication complexity of addition
Combinatorica | 2017-03-31 | Paper |
Bounded indistinguishability and the complexity of recovering secrets
Advances in Cryptology – CRYPTO 2016 | 2016-11-09 | Paper |
On beating the hybrid argument
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
3SUM, 3XOR, triangles
Algorithmica | 2016-03-23 | Paper |
Local reductions
Automata, Languages, and Programming | 2015-10-27 | Paper |
Real advantage
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Improved separations between nondeterministic and randomized multiparty communication
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
The communication complexity of interleaved group products
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
On the complexity of constructing pseudorandom functions (especially when they don't exist)
Journal of Cryptology | 2015-08-03 | Paper |
Bit-probe lower bounds for succinct data structures
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Randomness buys depth for approximate counting
Computational Complexity | 2014-12-17 | Paper |
scientific article; zbMATH DE number 6351503 (Why is no real title available?)
Theory of Computing | 2014-10-06 | Paper |
Shielding circuits with groups
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Extractors for Circuit Sources
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Extractors for circuit sources
SIAM Journal on Computing | 2014-07-30 | Paper |
Randomness Buys Depth for Approximate Counting
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Bounded Independence Fools Halfspaces
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Short PCPs with projection queries
Automata, Languages, and Programming | 2014-07-01 | Paper |
| Cell-probe lower bounds for succinct partial sums | 2014-05-22 | Paper |
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Bit-probe lower bounds for succinct data structures
SIAM Journal on Computing | 2013-03-19 | Paper |
Bounded-depth circuits cannot sample good codes
Computational Complexity | 2012-12-07 | Paper |
Extractors for Turing-machine sources
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Substitution-permutation networks, pseudorandom functions, and natural proofs
Lecture Notes in Computer Science | 2012-09-25 | Paper |
The complexity of distributions
SIAM Journal on Computing | 2012-05-30 | Paper |
A computational view of market efficiency
Quantitative Finance | 2011-08-19 | Paper |
Norms, XOR lemmas, and lower bounds for polynomials and protocols
Theory of Computing | 2011-05-24 | Paper |
On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators
Theory of Cryptography | 2011-05-19 | Paper |
One-way multiparty communication lower bound for pointer jumping with applications
Combinatorica | 2011-04-26 | Paper |
Hardness Amplification Proofs Require Majority
SIAM Journal on Computing | 2011-04-04 | Paper |
Bounded Independence Fools Halfspaces
SIAM Journal on Computing | 2011-04-04 | Paper |
The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
Computational Complexity | 2011-02-18 | Paper |
On approximate majority and probabilistic time
Computational Complexity | 2011-02-18 | Paper |
Pseudorandom bits for polynomials
SIAM Journal on Computing | 2011-01-17 | Paper |
Using nondeterminism to amplify hardness
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
On the power of small-depth computation
Foundations and Trends® in Theoretical Computer Science | 2010-01-18 | Paper |
| scientific article; zbMATH DE number 5485572 (Why is no real title available?) | 2009-01-05 | Paper |
Improved Separations between Nondeterministic and Randomized Multiparty Communication
Lecture Notes in Computer Science | 2008-11-27 | Paper |
Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
STACS 2006 | 2008-03-19 | Paper |
Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
SIAM Journal on Computing | 2007-10-22 | Paper |
Using Nondeterminism to Amplify Hardness
SIAM Journal on Computing | 2006-06-01 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
The complexity of constructing pseudorandom generators from hard functions
Computational Complexity | 2005-03-01 | Paper |
| scientific article; zbMATH DE number 2044516 (Why is no real title available?) | 2004-02-18 | Paper |
