Advances in Computational Complexity and Cryptography

The field of computational complexity and cryptography is rapidly evolving, with recent developments focusing on advancing our understanding of average-case hardness, circuit lower bounds, and lattice problems. A key direction in this research area is the exploration of new models and frameworks for understanding the limitations of efficient algorithms, such as the random noise model and the use of group theory in recovery reductions. Notably, researchers are making progress in establishing conditional lower bounds for various problems, including parity problems and lattice problems, under well-studied hypotheses like SETH and ETH. Furthermore, innovative approaches to magnification of circuit lower bounds and sensitivity-to-communication lifting theorems are being developed, which have significant implications for our understanding of the complexity of computational problems. Some noteworthy papers include: Average-Case Hardness of Parity Problems, which establishes conditional lower bounds for average-case parity-counting versions of several problems. Simple general magnification of circuit lower bounds, which presents a novel approach to magnification and achieves sharp thresholds. Recovery Reductions in the Random Noise Model via Group Theory, which introduces a new model of reductions and establishes optimal recovery reductions for several NP-complete problems. Mind the Gap? Not for SVP Hardness under ETH!, which proves new hardness results for lattice problems under the Exponential Time Hypothesis.

Sources

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More

Simple general magnification of circuit lower bounds

Lifting for Arbitrary Gadgets

SAT problem and Limit of Solomonoff's inductive reasoning theory

Recovery Reductions in the Random Noise Model via Group Theory: Insights into NP-Complete and Fine-Grained Problems

Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction

Mind the Gap? Not for SVP Hardness under ETH!

Built with on top of