8 Search Results for "Holmgren, Justin"


Document
Locally Covert Learning

Authors: Justin Holmgren and Ruta Jawale

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
The goal of a covert learning algorithm is to learn a function f by querying it, while ensuring that an adversary, who sees all queries and their responses, is unable to (efficiently) learn any more about f than they could learn from random input-output pairs. We focus on a relaxation that we call local covertness, in which queries are distributed across k servers and we only limit what is learnable by k - 1 colluding servers. For any constant k, we give a locally covert algorithm for efficiently learning any Fourier-sparse function (technically, our notion of learning is improper, agnostic, and with respect to the uniform distribution). Our result holds unconditionally and for computationally unbounded adversaries. Prior to our work, such an algorithm was known only for the special case of O(log n)-juntas, and only with k = 2 servers [Yuval Ishai et al., 2019]. Our main technical observation is that the original Goldreich-Levin algorithm only utilizes i.i.d. pairs of correlated queries, where each half of every pair is uniformly random. We give a simple generalization of this algorithm in which pairs are replaced by k-tuples in which any k - 1 components are jointly uniform. The cost of this generalization is that the number of queries needed grows exponentially with k.

Cite as

Justin Holmgren and Ruta Jawale. Locally Covert Learning. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{holmgren_et_al:LIPIcs.ITC.2023.14,
  author =	{Holmgren, Justin and Jawale, Ruta},
  title =	{{Locally Covert Learning}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.14},
  URN =		{urn:nbn:de:0030-drops-183421},
  doi =		{10.4230/LIPIcs.ITC.2023.14},
  annote =	{Keywords: learning theory, adversarial machine learning, zero knowledge, Fourier analysis of boolean functions, Goldreich-Levin algorithm, Kushilevitz-Mansour algorithm}
}
Document
RANDOM
Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs

Authors: Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)


Abstract
We prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Our proof technique is new and requires many new ideas. For example, we make use of the Level-k inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.

Cite as

Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan. Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2022.6,
  author =	{Girish, Uma and Mittal, Kunal and Raz, Ran and Zhan, Wei},
  title =	{{Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.6},
  URN =		{urn:nbn:de:0030-drops-171286},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.6},
  annote =	{Keywords: Parallel repetition, Multi-prover games, Fourier analysis}
}
Document
Track A: Algorithms, Complexity and Games
Delegation for Search Problems

Authors: Justin Holmgren, Andrea Lincoln, and Ron D. Rothblum

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
The theory of proof systems in general, and interactive proofs in particular, has been immensely influential. Such proof systems allow a prover to convince a verifier whether a given statement is true or not - namely to solve a decision problem. In this work we initiate a study of interactive proofs for search problems. More precisely, we consider a setting in which a client C, given an input x, would like to find a solution y satisfying (x,y) ∈ R, for a given relation R. The client wishes to delegate this work to an (untrusted) advisor A, who has more resources than C. We seek solutions in which the communication from A is short, and, in particular, shorter than the length of the output y. (In particular, this precludes the trivial solution of the advisor sending y and then proving that (x,y) ∈ R using a standard interactive proof.) We show that such search delegation schemes exist for several problems of interest including (1) longest common subsequence (LCS) and edit distance, (2) parsing context-free grammars and (3) k-SAT.

Cite as

Justin Holmgren, Andrea Lincoln, and Ron D. Rothblum. Delegation for Search Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 73:1-73:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{holmgren_et_al:LIPIcs.ICALP.2022.73,
  author =	{Holmgren, Justin and Lincoln, Andrea and Rothblum, Ron D.},
  title =	{{Delegation for Search Problems}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{73:1--73:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.73},
  URN =		{urn:nbn:de:0030-drops-164146},
  doi =		{10.4230/LIPIcs.ICALP.2022.73},
  annote =	{Keywords: Interactive Proofs, Fine-Grained Complexity, Delegation}
}
Document
PCPs and Instance Compression from a Cryptographic Lens

Authors: Liron Bronfman and Ron D. Rothblum

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary’s power in other information theoretic proof-systems and show how to use this assumption to bypass impossibility results. We first consider the question of constructing succinct PCPs. These are PCPs whose length is polynomial only in the length of the original NP witness (in contrast to standard PCPs whose length is proportional to the non-deterministic verification time). Unfortunately, succinct PCPs are known to be impossible to construct under standard complexity assumptions. Assuming the sub-exponential hardness of the learning with errors (LWE) problem, we construct succinct probabilistically checkable arguments or PCAs (Kalai and Raz 2009), which are PCPs in which soundness is guaranteed against efficiently generated false proofs. Our PCA construction is for every NP relation that can be verified by a small-depth circuit (e.g., SAT, clique, TSP, etc.) and in contrast to prior work is publicly verifiable and has constant query complexity. Curiously, we also show, as a proof-of-concept, that such publicly-verifiable PCAs can be used to derive hardness of approximation results. Second, we consider the notion of Instance Compression (Harnik and Naor, 2006). An instance compression scheme lets one compress, for example, a CNF formula φ on m variables and n ≫ m clauses to a new formula φ' with only poly(m) clauses, so that φ is satisfiable if and only if φ' is satisfiable. Instance compression has been shown to be closely related to succinct PCPs and is similarly highly unlikely to exist. We introduce a computational analog of instance compression in which we require that if φ is unsatisfiable then φ' is effectively unsatisfiable, in the sense that it is computationally infeasible to find a satisfying assignment for φ' (although such an assignment may exist). Assuming the same sub-exponential LWE assumption, we construct such computational instance compression schemes for every bounded-depth NP relation. As an application, this lets one compress k formulas ϕ₁,… ,ϕ_k into a single short formula ϕ that is effectively satisfiable if and only if at least one of the original formulas was satisfiable.

Cite as

Liron Bronfman and Ron D. Rothblum. PCPs and Instance Compression from a Cryptographic Lens. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bronfman_et_al:LIPIcs.ITCS.2022.30,
  author =	{Bronfman, Liron and Rothblum, Ron D.},
  title =	{{PCPs and Instance Compression from a Cryptographic Lens}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.30},
  URN =		{urn:nbn:de:0030-drops-156269},
  doi =		{10.4230/LIPIcs.ITCS.2022.30},
  annote =	{Keywords: PCP, Succinct Arguments, Instance Compression}
}
Document
RANDOM
Parallel Repetition for the GHZ Game: A Simpler Proof

Authors: Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)


Abstract
We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n^{-Ω(1)}. This was first established by Holmgren and Raz [Holmgren and Raz, 2020]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [Greenberger et al., 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [Dinur et al., 2017] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

Cite as

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan. Parallel Repetition for the GHZ Game: A Simpler Proof. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.62,
  author =	{Girish, Uma and Holmgren, Justin and Mittal, Kunal and Raz, Ran and Zhan, Wei},
  title =	{{Parallel Repetition for the GHZ Game: A Simpler Proof}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.62},
  URN =		{urn:nbn:de:0030-drops-147551},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.62},
  annote =	{Keywords: Parallel Repetition, GHZ, Polynomial, Multi-player}
}
Document
Error Correcting Codes for Uncompressed Messages

Authors: Ofer Grossman and Justin Holmgren

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed. We show that in this setting, it is sub-optimal to use standard error correction. We consider a model where there is a set of "valid messages" which the sender may send that may not be efficiently compressible, but where it is possible for the receiver to recognize valid messages. In this model, we construct a (probabilistic) encoding procedure that achieves better tradeoffs between data rates and error-resilience (compared to just applying a standard error correcting code). Additionally, our techniques yield improved efficiently decodable (probabilistic) codes for fully compressed messages (the standard setting where the set of valid messages is all binary strings) in the high-rate regime.

Cite as

Ofer Grossman and Justin Holmgren. Error Correcting Codes for Uncompressed Messages. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{grossman_et_al:LIPIcs.ITCS.2021.43,
  author =	{Grossman, Ofer and Holmgren, Justin},
  title =	{{Error Correcting Codes for Uncompressed Messages}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.43},
  URN =		{urn:nbn:de:0030-drops-135828},
  doi =		{10.4230/LIPIcs.ITCS.2021.43},
  annote =	{Keywords: Coding Theory, List Decoding}
}
Document
Counterexamples to the Low-Degree Conjecture

Authors: Justin Holmgren and Alexander S. Wein

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data. This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs via the low-degree likelihood ratio. In this work, we refute the conjecture of Hopkins. However, our counterexample crucially exploits the specifics of the noise operator used in the conjecture, and we point out a simple way to modify the conjecture to rule out our counterexample. We also give an example illustrating that (even after the above modification), the symmetry assumption in the conjecture is necessary. These results do not undermine the low-degree framework for computational lower bounds, but rather aim to better understand what class of problems it is applicable to.

Cite as

Justin Holmgren and Alexander S. Wein. Counterexamples to the Low-Degree Conjecture. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 75:1-75:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{holmgren_et_al:LIPIcs.ITCS.2021.75,
  author =	{Holmgren, Justin and Wein, Alexander S.},
  title =	{{Counterexamples to the Low-Degree Conjecture}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{75:1--75:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.75},
  URN =		{urn:nbn:de:0030-drops-136148},
  doi =		{10.4230/LIPIcs.ITCS.2021.75},
  annote =	{Keywords: Low-degree likelihood ratio, error-correcting codes}
}
Document
On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?

Authors: Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin

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


Abstract
Garbling schemes, also known as decomposable randomized encodings (DRE), have found many applications in cryptography. However, despite a large body of work on constructing such schemes, very little is known about their limitations. We initiate a systematic study of the DRE complexity of Boolean functions, obtaining the following main results: - Near-quadratic lower bounds. We use a classical lower bound technique of Nečiporuk [Dokl. Akad. Nauk SSSR '66] to show an Ω(n²/log n) lower bound on the size of any DRE for many explicit Boolean functions. For some natural functions, we obtain a corresponding upper bound, thus settling their DRE complexity up to polylogarithmic factors. Prior to our work, no superlinear lower bounds were known, even for non-explicit functions. - Garbling-friendly PRFs. We show that any exponentially secure PRF has Ω(n²/log n) DRE size, and present a plausible candidate for a "garbling-optimal" PRF that nearly meets this bound. This candidate establishes a barrier for super-quadratic DRE lower bounds via natural proof techniques. In contrast, we show a candidate for a weak PRF with near-exponential security and linear DRE size. Our results establish several qualitative separations, including near-quadratic separations between computational and information-theoretic DRE size of Boolean functions, and between DRE size of weak vs. strong PRFs.

Cite as

Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin. On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 86:1-86:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2020.86,
  author =	{Ball, Marshall and Holmgren, Justin and Ishai, Yuval and Liu, Tianren and Malkin, Tal},
  title =	{{On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{86:1--86:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.86},
  URN =		{urn:nbn:de:0030-drops-117714},
  doi =		{10.4230/LIPIcs.ITCS.2020.86},
  annote =	{Keywords: Randomized Encoding, Private Simultaneous Messages}
}
  • Refine by Author
  • 6 Holmgren, Justin
  • 2 Girish, Uma
  • 2 Mittal, Kunal
  • 2 Raz, Ran
  • 2 Rothblum, Ron D.
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational complexity and cryptography
  • 3 Theory of computation → Interactive proof systems
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Machine learning theory

  • Refine by Keyword
  • 1 Coding Theory
  • 1 Delegation
  • 1 Fine-Grained Complexity
  • 1 Fourier analysis
  • 1 Fourier analysis of boolean functions
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2021
  • 3 2022
  • 1 2020
  • 1 2023

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