source: Simons Institute 2017年3月6日
One theme of this workshop will be how to leverage weak pseudorandomness properties, fooling simple classes of tests, in order to derive stronger pseudorandomness properties related to more complex tests. In the setting of additive combinatorics, what is the minimal set of tests that primes have to satisfy in order to guarantee that they contain arithmetic progressions (or other structures)? For example, recent work of Conlon, Fox and Zhao shows that a “correlation condition” initially imposed in the work of Green and Tao is not necessary.
In complexity theory, most unconditional constructions of pseudorandom generators ultimately all rely on various combinations of four basic tools: k-wise independence, small-bias distributions, error-correcting codes, and random walks in expanders. The technical core of the analysis of known pseudorandom generators is to show that pseudorandomness against simple tests implies pseudorandomness against more complex tests (see for example Braverman’s theorem). Explicit constructions of pseudorandom objects have been essential to derandomize algorithms such as primality testing and undirected connectivity, and they have been applied in cryptography, distributed systems, complexity theory, streaming algorithms and learning theory. This workshop will explore unconditional constructions of pseudorandom objects at the frontier of progress, such as pseudorandom generators for small-space computations, small-depth circuits with modular gates, threshold circuits and DNFs. For more information, please visit: https://simons.berkeley.edu/workshops/pseudorandomness2017-2
These presentations were supported in part by an award from the Simons Foundation.
The Uncanny Usefulness of Constructive Proofs of Pseudorandomness 34:00 Valentine Kabanets, Simon Fraser University
Approximately Counting Solutions to Systems of Quadratic Equations 30:39
Pseudorandomness in Data Structures 1:00:42
Packing Degenerate Graphs Using Pseudorandomness 1:00:35
Regularity Inheritance in Pseudorandom Graphs 31:43
The Number of B_h-sets of a Given Cardinality 36:27
Removal Lemmas with Polynomial Bounds 57:05
Forcing Quasirandomness with Triangles 1:01:25
Explicit, Almost Optimal, Epsilon-Balanced Codes 1:04:49
Preserving Randomness for Adaptive Adversaries 1:00:26
Mixing Implies Lower Bounds for Space Bounded Learning 49:46
Algorithmic Regularity Lemmas and Applications 30:54
Linear-Algebraic Pseudorandomness: Subspace Designs and Dimension Expanders 59:55
Derandomizing "Algebraic RL" 59:44
Deterministic Isolation for Bipartite Matching and Matroid Intersection 32:57
PRGs for Small Space via Fourier Analysis 33:34
[private video]Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas 34:35
Query-to-Communication Lifting for BPP 28:40
Fast Permutation Property Testing and Metrics of Permutations 49:14
Randomness Intuition 1:03:53
A Reduction from Efficient Non-Malleable Extractors to Low-Error Two-Source Extractors 50:20
No comments:
Post a Comment