Search Results

Documents authored by Rosen, Alon

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.28
Nondeterministic Interactive Refutations for Nearest Boolean Vector

Authors: Andrej Bogdanov and Alon Rosen

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Most n-dimensional subspaces 𝒜 of ℝ^m are Ω(√m)-far from the Boolean cube {-1, 1}^m when n < cm for some constant c > 0. How hard is it to certify that the Nearest Boolean Vector (NBV) is at least γ √m far from a given random 𝒜? Certifying NBV instances is relevant to the computational complexity of approximating the Sherrington-Kirkpatrick Hamiltonian, i.e. maximizing x^TAx over the Boolean cube for a matrix A sampled from the Gaussian Orthogonal Ensemble. The connection was discovered by Mohanty, Raghavendra, and Xu (STOC 2020). Improving on their work, Ghosh, Jeronimo, Jones, Potechin, and Rajendran (FOCS 2020) showed that certification is not possible in the sum-of-squares framework when m ≪ n^1.5, even with distance γ = 0. We present a non-deterministic interactive certification algorithm for NBV when m ≫ n log n and γ ≪ 1/mn^1.5. The algorithm is obtained by adapting a public-key encryption scheme of Ajtai and Dwork.
Cite as

Andrej Bogdanov and Alon Rosen. Nondeterministic Interactive Refutations for Nearest Boolean Vector. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bogdanov_et_al:LIPIcs.ICALP.2023.28,
  author =	{Bogdanov, Andrej and Rosen, Alon},
  title =	{{Nondeterministic Interactive Refutations for Nearest Boolean Vector}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.28},
  URN =		{urn:nbn:de:0030-drops-180801},
  doi =		{10.4230/LIPIcs.ICALP.2023.28},
  annote =	{Keywords: average-case complexity, statistical zero-knowledge, nondeterministic refutation, Sherrington-Kirkpatrick Hamiltonian, complexity of statistical inference, lattice smoothing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.22
PPP-Completeness and Extremal Combinatorics

Authors: Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, and Nikolaj I. Schwartzbach

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey’s theorem on monochromatic subgraphs and the Erdős-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard under randomized reductions in the case of Ramsey’s theorem and PWPP-hard in the case of the sunflower lemma; here "implicit” means that the collection is represented by a poly-sized circuit inducing an exponentially large number of objects. We show that several other well-known theorems from extremal combinatorics - including Erdős-Ko-Rado, Sperner, and Cayley’s formula – give rise to complete problems for PWPP and PPP. This is in contrast to the Ramsey and Erdős-Rado problems, for which establishing inclusion in PWPP has remained elusive. Besides significantly expanding the set of problems that are complete for PWPP and PPP, our work identifies some key properties of combinatorial proofs of existence that can give rise to completeness for these classes. Our completeness results rely on efficient encodings for which finding collisions allows extracting the desired substructure. These encodings are made possible by the tightness of the bounds for the problems at hand (tighter than what is known for Ramsey’s theorem and the sunflower lemma). Previous techniques for proving bounds in TFNP invariably made use of structured algorithms. Such algorithms are not known to exist for the theorems considered in this work, as their proofs "from the book" are non-constructive.
Cite as

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, and Nikolaj I. Schwartzbach. PPP-Completeness and Extremal Combinatorics. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bourneuf_et_al:LIPIcs.ITCS.2023.22,
  author =	{Bourneuf, Romain and Folwarczn\'{y}, Luk\'{a}\v{s} and Hub\'{a}\v{c}ek, Pavel and Rosen, Alon and Schwartzbach, Nikolaj I.},
  title =	{{PPP-Completeness and Extremal Combinatorics}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.22},
  URN =		{urn:nbn:de:0030-drops-175255},
  doi =		{10.4230/LIPIcs.ITCS.2023.22},
  annote =	{Keywords: total search problems, extremal combinatorics, PPP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.67
Downward Self-Reducibility in TFNP

Authors: Prahladh Harsha, Daniel Mitropolsky, and Alon Rosen

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
A problem is downward self-reducible if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is well studied and it is known that all downward self-reducible problems are in PSPACE. In this paper, we initiate the study of downward self-reducible search problems which are guaranteed to have a solution - that is, the downward self-reducible problems in TFNP. We show that most natural PLS-complete problems are downward self-reducible and any downward self-reducible problem in TFNP is contained in PLS. Furthermore, if the downward self-reducible problem is in TFUP (i.e. it has a unique solution), then it is actually contained in UEOPL, a subclass of CLS. This implies that if integer factoring is downward self-reducible then it is in fact in UEOPL, suggesting that no efficient factoring algorithm exists using the factorization of smaller numbers.
Cite as

Prahladh Harsha, Daniel Mitropolsky, and Alon Rosen. Downward Self-Reducibility in TFNP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{harsha_et_al:LIPIcs.ITCS.2023.67,
  author =	{Harsha, Prahladh and Mitropolsky, Daniel and Rosen, Alon},
  title =	{{Downward Self-Reducibility in TFNP}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{67:1--67:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.67},
  URN =		{urn:nbn:de:0030-drops-175700},
  doi =		{10.4230/LIPIcs.ITCS.2023.67},
  annote =	{Keywords: downward self-reducibility, TFNP, TFUP, factoring, PLS, CLS}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.81
Cryptography from Information Loss

Authors: Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is "lossy" reductions, where the reduction loses some information about the input instance. We show that such reductions, when they exist, have interesting and powerful consequences for lifting hardness into "useful" hardness, namely cryptography. Our first, conceptual, contribution is a definition of lossy reductions in the language of mutual information. Roughly speaking, our definition says that a reduction C is t-lossy if, for any distribution X over its inputs, the mutual information I(X;C(X)) ≤ t. Our treatment generalizes a variety of seemingly related but distinct notions such as worst-case to average-case reductions, randomized encodings (Ishai and Kushilevitz, FOCS 2000), homomorphic computations (Gentry, STOC 2009), and instance compression (Harnik and Naor, FOCS 2006). We then proceed to show several consequences of lossy reductions: 1. We say that a language L has an f-reduction to a language L' for a Boolean function f if there is a (randomized) polynomial-time algorithm C that takes an m-tuple of strings X = (x_1,…,x_m), with each x_i ∈ {0,1}^n, and outputs a string z such that with high probability, L'(z) = f(L(x_1),L(x_2),…,L(x_m)). Suppose a language L has an f-reduction C to L' that is t-lossy. Our first result is that one-way functions exist if L is worst-case hard and one of the following conditions holds: - f is the OR function, t ≤ m/100, and L' is the same as L - f is the Majority function, and t ≤ m/100 - f is the OR function, t ≤ O(m log n), and the reduction has no error This improves on the implications that follow from combining (Drucker, FOCS 2012) with (Ostrovsky and Wigderson, ISTCS 1993) that result in auxiliary-input one-way functions. 2. Our second result is about the stronger notion of t-compressing f-reductions - reductions that only output t bits. We show that if there is an average-case hard language L that has a t-compressing Majority reduction to some language for t=m/100, then there exist collision-resistant hash functions. This improves on the result of (Harnik and Naor, STOC 2006), whose starting point is a cryptographic primitive (namely, one-way functions) rather than average-case hardness, and whose assumption is a compressing OR-reduction of SAT (which is now known to be false unless the polynomial hierarchy collapses). Along the way, we define a non-standard one-sided notion of average-case hardness, which is the notion of hardness used in the second result above, that may be of independent interest.
Cite as

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. Cryptography from Information Loss. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 81:1-81:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2020.81,
  author =	{Ball, Marshall and Boyle, Elette and Degwekar, Akshay and Deshpande, Apoorvaa and Rosen, Alon and Vaikuntanathan, Vinod and Vasudevan, Prashant Nalini},
  title =	{{Cryptography from Information Loss}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{81:1--81:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.81},
  URN =		{urn:nbn:de:0030-drops-117667},
  doi =		{10.4230/LIPIcs.ITCS.2020.81},
  annote =	{Keywords: Compression, Information Loss, One-Way Functions, Reductions, Generic Constructions}
}
Document
DOI: 10.4230/DagRep.1.7.36
Verifiable Elections and the Public (Dagstuhl Seminar 11281)

Authors: R. Michael Alvarez, Josh Benaloh, Alon Rosen, and Peter Y. A. Ryan

Published in: Dagstuhl Reports, Volume 1, Issue 7 (2011)

Abstract
This report documents the program of Dagstuhl Seminar 11281 ``Verifiable Elections and the Public''. This seminar brought together leading researchers from computer and social science, policymakers, and representatives of industry to present new research, develop new interdisciplinary approaches for studying election technologies, and to determine ways to bridge the gap between research and practice.
Cite as

R. Michael Alvarez, Josh Benaloh, Alon Rosen, and Peter Y. A. Ryan. Verifiable Elections and the Public (Dagstuhl Seminar 11281). In Dagstuhl Reports, Volume 1, Issue 7, pp. 36-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{alvarez_et_al:DagRep.1.7.36,
  author =	{Alvarez, R. Michael and Benaloh, Josh and Rosen, Alon and Ryan, Peter Y. A.},
  title =	{{Verifiable Elections and the Public (Dagstuhl Seminar 11281)}},
  pages =	{36--52},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{7},
  editor =	{Alvarez, R. Michael and Benaloh, Josh and Rosen, Alon and Ryan, Peter Y. A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.7.36},
  URN =		{urn:nbn:de:0030-drops-33086},
  doi =		{10.4230/DagRep.1.7.36},
  annote =	{Keywords: Electronic voting, Internet voting, voter verification, verifiable elections}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact