A New Approximate Min-Max Theorem with Applications in Cryptography

2015/06/22 by Skorski, Maciej
#Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1506.06633

Abstract

We propose a novel proof technique that can be applied to attack a broad class of problems in computational complexity, when switching the order of universal and existential quantifiers is helpful. Our approach combines the standard min-max theorem and convex approximation techniques, offering quantitative improvements over the standard way of using min-max theorems as well as more concise and elegant proofs.

Related

• A Combinatorial Problem Related to Sparse Systems of Equations
• On the Cryptanalysis via Approximation of Cryptographic Primitives Relying on the Planted Clique Conjecture
• On the Low Weight Polynomial Multiple Problem
• The General Adversary Bound: A Survey
• The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control