Cryptographic hardness of random local functions. Survey (Q332271): Difference between revisions

@@ Property / cites work @@
+A method for obtaining digital signatures and public-key cryptosystems
+Normal rank
@@ Property / cites work @@
+On the solution-space geometry of random constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+Q4526993
@@ Property / cites work: Q4526993 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
+Normal rank
@@ Property / cites work @@
+A spectral technique for coloring random 3-colorable graphs (preliminary version)
+Normal rank
@@ Property / cites work @@
+Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
+Normal rank
@@ Property / cites work @@
+Public-key cryptography from different assumptions
+Normal rank
@@ Property / cites work @@
+A Dichotomy for Local Small-Bias Generators
@@ Property / cites work: A Dichotomy for Local Small-Bias Generators / rank @@
+Normal rank
@@ Property / cites work @@
+Computationally private randomizing polynomials and their applications
+Normal rank
@@ Property / cites work @@
+Cryptography in $NC^0$
@@ Property / cites work: Cryptography in $NC^0$ / rank @@
+Normal rank
@@ Property / cites work @@
+On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\)
+Normal rank
@@ Property / cites work @@
+Locally Computable UOWHF with Linear Shrinkage
@@ Property / cites work: Locally Computable UOWHF with Linear Shrinkage / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation resistant predicates from pairwise independence
+Normal rank
@@ Property / cites work @@
+Sum of Squares Lower Bounds from Pairwise Independence
+Normal rank
@@ Property / cites work @@
+On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Q2913812
@@ Property / cites work: Q2913812 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom Bits for Polynomials
@@ Property / cites work: Pseudorandom Bits for Polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Selection of relevant features and examples in machine learning
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for Read-Once Formulas
@@ Property / cites work: Pseudorandomness for Read-Once Formulas / rank @@
+Normal rank
@@ Property / cites work @@
+On the security of Goldreich's one-way function
@@ Property / cites work: On the security of Goldreich's one-way function / rank @@
+Normal rank
@@ Property / cites work @@
+Input Locality and Hardness Amplification
@@ Property / cites work: Input Locality and Hardness Amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Polylogarithmic independence fools             <i>AC</i>             <sup>0</sup>             circuits
+Normal rank
@@ Property / cites work @@
+A Better Algorithm for Random k-SAT
@@ Property / cites work: A Better Algorithm for Random k-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+On the One-Way Function Candidate Proposed by Goldreich
+Normal rank
@@ Property / cites work @@
+Q4779150
@@ Property / cites work: Q4779150 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded Independence Fools Halfspaces
@@ Property / cites work: Bounded Independence Fools Halfspaces / rank @@
+Normal rank
@@ Property / cites work @@
+Correlation-immunity of nonlinear combining functions for cryptographic applications (Corresp.)
+Normal rank
@@ Property / cites work @@
+New directions in cryptography
@@ Property / cites work: New directions in cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Relations between average case complexity and approximation complexity
+Normal rank
@@ Property / cites work @@
+On the Complexity of Random Satisfiability Problems with Planted Solutions
+Normal rank
@@ Property / cites work @@
+A spectral technique for random satisfiable 3CNF formulas
+Normal rank
@@ Property / cites work @@
+Candidate One-Way Functions Based on Expander Graphs
+Normal rank
@@ Property / cites work @@
+Foundations of Cryptography
@@ Property / cites work: Foundations of Cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Foundations of Cryptography
@@ Property / cites work: Foundations of Cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Every 2-CSP allows nontrivial approximation
@@ Property / cites work: Every 2-CSP allows nontrivial approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for network algorithms
@@ Property / cites work: Pseudorandomness for network algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Robust Pseudorandom Generators
@@ Property / cites work: Robust Pseudorandom Generators / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549728
@@ Property / cites work: Q3549728 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms
+Normal rank
@@ Property / cites work @@
+Cryptographic limitations on learning Boolean formulae and finite automata
+Normal rank
@@ Property / cites work @@
+On the power of unique 2-prover 1-round games
@@ Property / cites work: On the power of unique 2-prover 1-round games / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002801
@@ Property / cites work: Q3002801 / rank @@
+Normal rank
@@ Property / cites work @@
+On ε‐biased generators in NC<sup>0</sup>
@@ Property / cites work: On ε‐biased generators in NC<sup>0</sup> / rank @@
+Normal rank
@@ Property / cites work @@
+Small-Bias Probability Spaces: Efficient Constructions and Applications
+Normal rank
@@ Property / cites work @@
+The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
+Normal rank