Robustness of Average-Case Meta-Complexity via Pseudorandomness

Robustness of Average-Case Meta-Complexity via Pseudorandomness

Bibliographic Details
Main Authors:	Ilango, Rahul, Ren, Hanlin, Santhanam, Rahul
Other Authors:	Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format:	Article
Language:	English
Published:	ACM\|Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 2022
Online Access:	https://hdl.handle.net/1721.1/146440

Similar Items

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
by: Huang, Yizhi, et al.
Published: (2023)

Pseudorandomness and the Minimum Circuit Size problem
by: Santhanam, R, et al.
Published: (2020)

A Duality between One-Way Functions and Average-Case Symmetry of Information
by: Hirahara, Shuichi, et al.
Published: (2023)

On the average-case complexity of MCSP and its variants
by: Hirahara, S, et al.
Published: (2017)

Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
by: Oliveira, I, et al.
Published: (2017)

Errorless versus error-prone average-case complexity
by: Hirahara, S, et al.
Published: (2022)

Algebraic methods in pseudorandomness and circuit complexity
by: Remscrim, Zachary (Zachary N.)
Published: (2016)

Strong Average-Case Lower Bounds from Non-trivial Derandomization
by: Chen, Lijie, et al.
Published: (2022)

Low complexity pseudorandom generators and indistinguishability obfuscation
by: Lombardi, Alex (Alex John)
Published: (2018)

A relativization perspective on meta-complexity
by: Ren, H, et al.
Published: (2022)

Efficient Quantum Pseudorandomness
by: Brandão, Fernando G. S. L., et al.
Published: (2018)

1‐Factorizations of pseudorandom graphs
by: Ferber, Asaf, et al.
Published: (2022)

Cryptanalysis of pseudorandom number generator
by: Huang, Ruimin
Published: (2024)

Functional Signatures and Pseudorandom Functions
by: Boyle, Elette, et al.
Published: (2014)

Algebraic methods in randomness and pseudorandomness
by: Kopparty, Swastik
Published: (2011)

Chaotic pseudorandom sequences and the security of cryptosystems
by: Hina, Aliyu Danladi, et al.
Published: (2015)

On finite pseudorandom sequences of k symbols
by: Bérczi, G
Published: (2003)

Pseudorandom functions with structure : extensions and implications
by: Cohen, Aloni (Aloni Jonathan)
Published: (2015)

Sidorenko's conjecture, graph norms, and pseudorandomness
by: Lee, J
Published: (2017)

Extremal results in sparse pseudorandom graphs
by: Conlon, David, et al.
Published: (2015)

Extremal results in sparse pseudorandom graphs
by: Conlon, D, et al.
Published: (2014)

Minimum distance of error correcting codes versus encoding complexity, symmetry, and pseudorandomness
by: Bazzi, Louay Mohamad Jamil, 1974-
Published: (2005)

An average-case lower bound against ACC$^0$
by: Chen, R, et al.
Published: (2018)

A sequence of triangle-free pseudorandom graphs
by: Conlon, D
Published: (2016)

Post-Quantum Verifiable Oblivious Pseudorandom Functions
by: Propson, Helen
Published: (2024)

Full orbit sequences in affine spaces via fractional jumps and pseudorandom number generation
by: Micheli, G, et al.
Published: (2018)

Average-case lower bounds and satisfiability algorithms for small threshold circuits
by: Chen, R, et al.
Published: (2016)

Average-case lower bounds and satisfiability algorithms for small threshold circuits
by: Chen, R, et al.
Published: (2018)

The Non-hardness of Approximating Circuit Size
by: Allender, Eric, et al.
Published: (2022)

The Non-hardness of Approximating Circuit Size
by: Allender, Eric, et al.
Published: (2021)

Average-case complexity of detecting cliques
by: Rossman, Benjamin (Benjamin E.)
Published: (2011)

Generation and statistical analysis of chaos-based pseudorandom sequences
by: Hina, Aliyu Danladi
Published: (2019)

Z8-Kerdock codes and pseudorandom binary sequences
by: Lahtonen, Jyrki, et al.
Published: (2013)

Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation
by: Lombardi, Alex, et al.
Published: (2021)

Robust sample average approximation
by: Gupta, Vishal, et al.
Published: (2018)

Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
by: Ilango, Rahul, et al.
Published: (2023)

Beating Brute Force for Compression Problems
by: Hirahara, Shuichi, et al.
Published: (2024)

Robust averaging during perceptual judgment.
by: de Gardelle, V, et al.
Published: (2011)

Robust averaging during perceptual choice
by: De Gardelle, V, et al.
Published: (2011)

Pseudorandom dynamics of frequency combs in free-running quantum cascade lasers
by: Henry, Nathan, et al.
Published: (2018)