A New Approximate Min-Max Theorem with Applications in Cryptography
From MaRDI portal
Publication:3459902
DOI10.1007/978-3-662-48971-0_55zbMATH Open1472.68070arXiv1506.06633OpenAlexW2963639643MaRDI QIDQ3459902
Publication date: 11 January 2016
Published in: Algorithms and Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1506.06633
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Cryptography (94A60) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Minimal achievable approximation ratio for MAX-MQ in finite fields 👍 👎
- A Uniform Min-Max Theorem with Applications in Cryptography 👍 👎
- Minimalism in Cryptography: The Even-Mansour Scheme Revisited 👍 👎
- Cryptographic Applications of Capacity Theory: On the Optimality of Coppersmith’s Method for Univariate Polynomials 👍 👎
- New applications of Min-max Theory 👍 👎
- Foundations of Information and Knowledge Systems 👍 👎
This page was built for publication: A New Approximate Min-Max Theorem with Applications in Cryptography
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459902)
