28 Search Results for "Goldreich, Oded"


Document
Spanning Adjacency Oracles in Sublinear Time

Authors: Greg Bodwin and Henry Fleischmann

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
Suppose we are given an n-node, m-edge input graph G, and the goal is to compute a spanning subgraph H on O(n) edges. This can be achieved in linear O(m + n) time via breadth-first search. But can we hope for sublinear runtime in some range of parameters - for example, perhaps O(n^{1.9}) worst-case runtime, even when the input graph has n² edges? If the goal is to return H as an adjacency list, there are simple lower bounds showing that Ω(m + n) runtime is necessary. If the goal is to return H as an adjacency matrix, then we need Ω(n²) time just to write down the entries of the output matrix. However, we show that neither of these lower bounds still apply if instead the goal is to return H as an implicit adjacency matrix, which we call an adjacency oracle. An adjacency oracle is a data structure that gives a user the illusion that an adjacency matrix has been computed: it accepts edge queries (u, v), and it returns in near-constant time a bit indicating whether or not (u, v) ∈ E(H). Our main result is that, for any 0 < ε < 1, one can construct an adjacency oracle for a spanning subgraph on at most (1+ε)n edges, in Õ(n ε^{-1}) time (hence sublinear time on input graphs with m ≫ n edges), and that this construction time is near-optimal. Additional results include constructions of adjacency oracles for k-connectivity certificates and spanners, which are similarly sublinear on dense-enough input graphs. Our adjacency oracles are closely related to Local Computation Algorithms (LCAs) for graph sparsifiers; they can be viewed as LCAs with some computation moved to a preprocessing step, in order to speed up queries. Our oracles imply the first LCAs for computing sparse spanning subgraphs of general input graphs in Õ(n) query time, which works by constructing our adjacency oracle, querying it once, and then throwing the rest of the oracle away. This addresses an open problem of Rubinfeld [CSR '17].

Cite as

Greg Bodwin and Henry Fleischmann. Spanning Adjacency Oracles in Sublinear Time. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ITCS.2024.19,
  author =	{Bodwin, Greg and Fleischmann, Henry},
  title =	{{Spanning Adjacency Oracles in Sublinear Time}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.19},
  URN =		{urn:nbn:de:0030-drops-195475},
  doi =		{10.4230/LIPIcs.ITCS.2024.19},
  annote =	{Keywords: Graph algorithms, Sublinear algorithms, Data structures, Graph theory}
}
Document
Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols

Authors: Dieter van Melkebeek and Nicollas Mocelin Sdroievski

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive proofs asks whether Arthur-Merlin protocols can be simulated nondeterministically with a small overhead in time (the AM vs. NP problem). Both questions are intricately tied to lower bounds. Prominently, in both settings blackbox derandomization, i.e., derandomization through pseudo-random generators, has been shown equivalent to lower bounds for decision problems against circuits. Recently, Chen and Tell (FOCS'21) established near-equivalences in the BPP setting between whitebox derandomization and lower bounds for multi-bit functions against algorithms on almost-all inputs. The key ingredient is a technique to translate hardness into targeted hitting sets in an instance-wise fashion based on a layered arithmetization of the evaluation of a uniform circuit computing the hard function f on the given instance. In this paper we develop a corresponding technique for Arthur-Merlin protocols and establish similar near-equivalences in the AM setting. As an example of our results in the hardness to derandomization direction, consider a length-preserving function f computable by a nondeterministic algorithm that runs in time n^a. We show that if every Arthur-Merlin protocol that runs in time n^c for c = O(log² a) can only compute f correctly on finitely many inputs, then AM is in NP. Our main technical contribution is the construction of suitable targeted hitting-set generators based on probabilistically checkable proofs for nondeterministic computations. As a byproduct of our constructions, we obtain the first result indicating that whitebox derandomization of AM may be equivalent to the existence of targeted hitting-set generators for AM, an issue raised by Goldreich (LNCS, 2011). Byproducts in the average-case setting include the first uniform hardness vs. randomness tradeoffs for AM, as well as an unconditional mild derandomization result for AM.

Cite as

Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 17:1-17:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:LIPIcs.CCC.2023.17,
  author =	{van Melkebeek, Dieter and Mocelin Sdroievski, Nicollas},
  title =	{{Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{17:1--17:36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.17},
  URN =		{urn:nbn:de:0030-drops-182870},
  doi =		{10.4230/LIPIcs.CCC.2023.17},
  annote =	{Keywords: Hardness versus randomness tradeoff, Arthur-Merlin protocol, targeted hitting set generator}
}
Document
On Interactive Proofs of Proximity with Proof-Oblivious Queries

Authors: Oded Goldreich, Guy N. Rothblum, and Tal Skverer

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


Abstract
Interactive proofs of proximity (IPPs) offer ultra-fast approximate verification of assertions regarding their input, where ultra-fast means that only a small portion of the input is read and approximate verification is analogous to the notion of approximate decision that underlies property testing. Specifically, in an IPP, the prover can make the verifier accept each input in the property, but cannot fool the verifier into accepting an input that is far from the property (except for with small probability). The verifier in an IPP system engages in two very different types of activities: interacting with an untrusted prover, and querying its input. The definition allows for arbitrary coordination between these two activities, but keeping them separate is both conceptually interesting and necessary for important applications such as addressing temporal considerations (i.e., at what time is each of the services available) and facilitating the construction of zero-knowledge schemes. In this work we embark on a systematic study of IPPs with proof-oblivious queries, where the queries should not be affected by the interaction with the prover. We assign the query and interaction activities to separate modules, and consider different limitations on their coordination. The most strict limitation requires these activities to be totally isolated from one another; they just feed their views to a separate deciding module. We show that such systems can be efficiently emulated by standard testers. Going to the other extreme, we only disallow information to flow from the interacting module to the querying module, but allow free information flow in the other direction. We show that extremely efficient one-round (i.e., two-message) systems of such type can be used to verify properties that are extremely hard to test (without the help of a prover). That is, the complexity of verifying can be polylogarithmic in the complexity of testing. This stands in contrast the MAPs (viewed as 1/2-round systems) in which proof-oblivious queries are as limited as our isolated model. Our focus is on an intermediate model that allows shared randomness between the querying and interacting modules but no information flow between them. In this case we show that 1-round systems are efficiently emulated by standard testers but 3/2-round systems of extremely low complexity exist for properties that are extremely hard to test. One additional result about this model is that it can efficiently emulate any IPP for any property of low-degree polynomials.

Cite as

Oded Goldreich, Guy N. Rothblum, and Tal Skverer. On Interactive Proofs of Proximity with Proof-Oblivious Queries. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 59:1-59:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{goldreich_et_al:LIPIcs.ITCS.2023.59,
  author =	{Goldreich, Oded and Rothblum, Guy N. and Skverer, Tal},
  title =	{{On Interactive Proofs of Proximity with Proof-Oblivious Queries}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{59:1--59:16},
  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.59},
  URN =		{urn:nbn:de:0030-drops-175625},
  doi =		{10.4230/LIPIcs.ITCS.2023.59},
  annote =	{Keywords: Complexity Theory, Property Testing, Interactive Proofs, Interactive Proofs of Proximity, Proof-Oblivious Queries}
}
Document
RANDOM
A Sublinear Local Access Implementation for the Chinese Restaurant Process

Authors: Peter Mörters, Christian Sohler, and Stefan Walzer

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


Abstract
The Chinese restaurant process is a stochastic process closely related to the Dirichlet process that groups sequentially arriving objects into a variable number of classes, such that within each class objects are cyclically ordered. A popular description involves a restaurant, where customers arrive one by one and either sit down next to a randomly chosen customer at one of the existing tables or open a new table. The full state of the process after n steps is given by a permutation of the n objects and cannot be represented in sublinear space. In particular, if we only need specific information about a few objects or classes it would be preferable to obtain the answers without simulating the process completely. A recent line of research [Oded Goldreich et al., 2010; Moni Naor and Asaf Nussboim, 2007; Amartya Shankha Biswas et al., 2020; Guy Even et al., 2021] attempts to provide access to huge random objects without fully instantiating them. Such local access implementations provide answers to a sequence of queries about the random object, following the same distribution as if the object was fully generated. In this paper, we provide a local access implementation for a generalization of the Chinese restaurant process described above. Our implementation can be used to answer any sequence of adaptive queries about class affiliation of objects, number and sizes of classes at any time, position of elements within a class, or founding time of a class. The running time per query is polylogarithmic in the total size of the object, with high probability. Our approach relies on some ideas from the recent local access implementation for preferential attachment trees by Even et al. [Guy Even et al., 2021]. Such trees are related to the Chinese restaurant process in the sense that both involve a "rich-get-richer" phenomenon. A novel ingredient in our implementation is to embed the process in continuous time, in which the evolution of the different classes becomes stochastically independent [Joyce and Tavaré, 1987]. This independence is used to keep the probabilistic structure manageable even if many queries have already been answered. As similar embeddings are available for a wide range of urn processes [Krishna B. Athreya and Samuel Karlin, 1968], we believe that our approach may be applicable more generally. Moreover, local access implementations for birth and death processes that we encounter along the way may be of independent interest.

Cite as

Peter Mörters, Christian Sohler, and Stefan Walzer. A Sublinear Local Access Implementation for the Chinese Restaurant Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{morters_et_al:LIPIcs.APPROX/RANDOM.2022.28,
  author =	{M\"{o}rters, Peter and Sohler, Christian and Walzer, Stefan},
  title =	{{A Sublinear Local Access Implementation for the Chinese Restaurant Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{28:1--28:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.28},
  URN =		{urn:nbn:de:0030-drops-171500},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.28},
  annote =	{Keywords: Chinese restaurant process, Dirichlet process, sublinear time algorithm, random recursive tree, random permutation, random partition, Ewens distribution, simulation, local access implementation, continuous time embedding}
}
Document
Track A: Algorithms, Complexity and Games
Expander Random Walks: The General Case and Limitations

Authors: Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma

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


Abstract
Cohen, Peri and Ta-Shma [Gil Cohen et al., 2021] considered the following question: Assume the vertices of an expander graph are labelled by ± 1. What "test" functions f : {±1}^t → {±1} can or cannot distinguish t independent samples from those obtained by a random walk? [Gil Cohen et al., 2021] considered only balanced labellings, and proved that for all symmetric functions the distinguishability goes down to zero with the spectral gap λ of the expander G. In addition, [Gil Cohen et al., 2021] show that functions computable by AC⁰ circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question. We generalize the result to all labelling, not merely balanced ones. We also improve the upper bound on the error of symmetric functions. More importantly, we give a matching lower bound and show a symmetric function with distinguishability going down to zero with λ but not with t. Moreover, we prove a lower bound on the error of functions in AC⁰ in particular, we prove that a random walk on expanders with constant spectral gap does not fool AC⁰.

Cite as

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43,
  author =	{Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon},
  title =	{{Expander Random Walks: The General Case and Limitations}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{43:1--43: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43},
  URN =		{urn:nbn:de:0030-drops-163849},
  doi =		{10.4230/LIPIcs.ICALP.2022.43},
  annote =	{Keywords: Expander Graphs, Random Walks, Lower Bounds}
}
Document
Randomness Extraction from Somewhat Dependent Sources

Authors: Marshall Ball, Oded Goldreich, and Tal Malkin

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


Abstract
We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness. Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions. Going from the more restricted model to the less restricted one, our models and main results are as follows. 1) Bounded dependence as bounded coordination: Here we consider pairs of distributions that arise from independent random processes that are applied to the outcome of a single global random source, which may be viewed as a mechanism of coordination (which is adversarial from our perspective). We show that if the min-entropy of each of the two outcomes is larger than the length of the global source, then extraction is possible (and is, in fact, feasible). We stress that the extractor has no access to the global random source nor to the internal randomness that the two processes use, but rather gets only the two dependent outcomes. This model is equivalent to a setting in which the two outcomes are generated by two independent sources, but then each outcome is modified based on limited leakage (equiv., communication) between the two sources. (Here this leakage is measured in terms of the number of bits that were communicated, but in the next model we consider the actual influence of this leakage.) 2) Bounded dependence as bounded cross influence: Here we consider pairs of outcomes that are produced by a pair of sources such that each source has bounded (worst-case) influence on the outcome of the other source. We stress that the extractor has no access to the randomness that the two processes use, but rather gets only the two dependent outcomes. We show that, while (proper) randomness extraction is impossible in this case, randomness condensing is possible and feasible; specifically, the randomness deficiency of condensing is linear in our measure of cross influence, and this upper bound is tight. We also discuss various applications of such condensers, including for cryptography, standard randomized algorithms, and sublinear-time algorithms, while pointing out their benefit over using a seeded (single-source) extractor. 3) Bounded dependence as bounded mutual information: Due to the average-case nature of mutual information, here there is a trade-off between the error (or deviation) probability of the extracted output and its randomness deficiency. Loosely speaking, for joint distributions of mutual information t, we can condense with randomness deficiency O(t/ε) and error ε, and this trade-off is optimal. All positive results are obtained by using a standard two-source extractor (or condenser) as a black-box.

Cite as

Marshall Ball, Oded Goldreich, and Tal Malkin. Randomness Extraction from Somewhat Dependent Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2022.12,
  author =	{Ball, Marshall and Goldreich, Oded and Malkin, Tal},
  title =	{{Randomness Extraction from Somewhat Dependent Sources}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{12:1--12:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.12},
  URN =		{urn:nbn:de:0030-drops-156081},
  doi =		{10.4230/LIPIcs.ITCS.2022.12},
  annote =	{Keywords: Randomness Extraction, min-entropy, mutual information, two-source extractors, two-source condenser}
}
Document
Sample-Based Proofs of Proximity

Authors: Guy Goldberg and Guy N. Rothblum

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


Abstract
Suppose we have random sampling access to a huge object, such as a graph or a database. Namely, we can observe the values of random locations in the object, say random records in the database or random edges in the graph. We cannot, however, query locations of our choice. Can we verify complex properties of the object using only this restricted sampling access? In this work, we initiate the study of sample-based proof systems, where the verifier is extremely constrained; Given an input, the verifier can only obtain samples of uniformly random and i.i.d. locations in the input string, together with the values at those locations. The goal is verifying complex properties in sublinear time, using only this restricted access. Following the literature on Property Testing and on Interactive Proofs of Proximity (IPPs), we seek proof systems where the verifier accepts every input that has the property, and with high probability rejects every input that is far from the property. We study both interactive and non-interactive sample-based proof systems, showing: - On the positive side, our main result is that rich families of properties / languages have sub-linear sample-based interactive proofs of proximity (SIPPs). We show that every language in NC has a SIPP, where the sample and communication complexities, as well as the verifier’s running time, are Õ(√n), and with polylog(n) communication rounds. We also show that every language that can be computed in polynomial-time and bounded-polynomial space has a SIPP, where the sample and communication complexities of the protocol, as well as the verifier’s running time are roughly √n, and with a constant number of rounds. This is achieved by constructing a reduction protocol from SIPPs to IPPs. With the aid of an untrusted prover, this reduction enables a restricted, sample-based verifier to simulate an execution of a (query-based) IPP, even though it cannot query the input. Applying the reduction to known query-based IPPs yields SIPPs for the families described above. - We show that every language with an adequate (query-based) property tester has a 1-round SIPP with constant sample complexity and logarithmic communication complexity. One such language is equality testing, for which we give an explicit and simple SIPP. - On the negative side, we show that interaction can be essential: we prove that there is no non-interactive sample-based proof of proximity for equality testing. - Finally, we prove that private coins can dramatically increase the power of SIPPs. We show a strong separation between the power of public-coin SIPPs and private-coin SIPPs for Equality Testing.

Cite as

Guy Goldberg and Guy N. Rothblum. Sample-Based Proofs of Proximity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 77:1-77:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.ITCS.2022.77,
  author =	{Goldberg, Guy and N. Rothblum, Guy},
  title =	{{Sample-Based Proofs of Proximity}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{77:1--77: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.77},
  URN =		{urn:nbn:de:0030-drops-156736},
  doi =		{10.4230/LIPIcs.ITCS.2022.77},
  annote =	{Keywords: Interactive Proof Systems, Sample-Based Access, Proofs of Proximity}
}
Document
Testing Distributions of Huge Objects

Authors: Oded Goldreich and Dana Ron

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


Abstract
We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings. Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings). Accordingly, the model accounts for the total number of local probes into these objects (resp., queries to the strings) as well as for the distance between objects (resp., strings). Specifically, the distance between distributions is defined as the earth mover’s distance with respect to the relative Hamming distance between strings. We study the query complexity of testing in this new model, focusing on three directions. First, we try to relate the query complexity of testing properties in the new model to the sample complexity of testing these properties in the standard distribution testing model. Second, we consider the complexity of testing properties that arise naturally in the new model (e.g., distributions that capture random variations of fixed strings). Third, we consider the complexity of testing properties that were extensively studied in the standard distribution testing model: Two such cases are uniform distributions and pairs of identical distributions, where we obtain the following results. - Testing whether a distribution over n-bit long strings is uniform on some set of size m can be done with query complexity Õ(m/ε³), where ε > (log₂m)/n is the proximity parameter. - Testing whether two distribution over n-bit long strings that have support size at most m are identical can be done with query complexity Õ(m^{2/3}/ε³). Both upper bounds are quite tight; that is, for ε = Ω(1), the first task requires Ω(m^c) queries for any c < 1 and n = ω(log m), whereas the second task requires Ω(m^{2/3}) queries. Note that the query complexity of the first task is higher than the sample complexity of the corresponding task in the standard distribution testing model, whereas in the case of the second task the bounds almost match.

Cite as

Oded Goldreich and Dana Ron. Testing Distributions of Huge Objects. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 78:1-78:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{goldreich_et_al:LIPIcs.ITCS.2022.78,
  author =	{Goldreich, Oded and Ron, Dana},
  title =	{{Testing Distributions of Huge Objects}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{78:1--78: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.78},
  URN =		{urn:nbn:de:0030-drops-156747},
  doi =		{10.4230/LIPIcs.ITCS.2022.78},
  annote =	{Keywords: Property Testing, Distributions}
}
Document
Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity

Authors: Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT complexity of a string). Both MKTP and MCSP are hard for SZK (Statistical Zero Knowledge) under BPP-Turing reductions; neither is known to be NP-complete. Recently, some hardness results for MKTP were proved that are not (yet) known to hold for MCSP. In particular, MKTP is hard for DET (a subclass of P) under nonuniform ≤^{NC^0}_m reductions. In this paper, we improve this, to show that the complement of MKTP is hard for the (apparently larger) class NISZK_L under not only ≤^{NC^0}_m reductions but even under projections. Also, the complement of MKTP is hard for NISZK under ≤^{P/poly}_m reductions. Here, NISZK is the class of problems with non-interactive zero-knowledge proofs, and NISZK_L is the non-interactive version of the class SZK_L that was studied by Dvir et al. As an application, we provide several improved worst-case to average-case reductions to problems in NP, and we obtain a new lower bound on MKTP (which is currently not known to hold for MCSP).

Cite as

Eric Allender, John Gouwar, Shuichi Hirahara, and Caleb Robelle. Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.ISAAC.2021.54,
  author =	{Allender, Eric and Gouwar, John and Hirahara, Shuichi and Robelle, Caleb},
  title =	{{Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.54},
  URN =		{urn:nbn:de:0030-drops-154875},
  doi =		{10.4230/LIPIcs.ISAAC.2021.54},
  annote =	{Keywords: Kolmogorov Complexity, Interactive Proofs, Minimum Circuit Size Problem, Worst-case to Average-case Reductions}
}
Document
RANDOM
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time

Authors: Amartya Shankha Biswas, Talya Eden, and Ronitt Rubinfeld

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


Abstract
We consider the problem of sampling and approximately counting an arbitrary given motif H in a graph G, where access to G is given via queries: degree, neighbor, and pair, as well as uniform edge sample queries. Previous algorithms for these tasks were based on a decomposition of H into a collection of odd cycles and stars, denoted D^*(H) = {O_{k₁},...,O_{k_q}, S_{p₁},...,S_{p_𝓁}}. These algorithms were shown to be optimal for the case where H is a clique or an odd-length cycle, but no other lower bounds were known. We present a new algorithm for sampling arbitrary motifs which, up to poly(log n) factors, is always at least as good, and for most graphs G is strictly better. The main ingredient leading to this improvement is an improved uniform algorithm for sampling stars, which might be of independent interest, as it allows to sample vertices according to the p-th moment of the degree distribution. Finally, we prove that this algorithm is decomposition-optimal for decompositions that contain at least one odd cycle. These are the first lower bounds for motifs H with a nontrivial decomposition, i.e., motifs that have more than a single component in their decomposition.

Cite as

Amartya Shankha Biswas, Talya Eden, and Ronitt Rubinfeld. Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.APPROX/RANDOM.2021.55,
  author =	{Biswas, Amartya Shankha and Eden, Talya and Rubinfeld, Ronitt},
  title =	{{Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{55:1--55: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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.55},
  URN =		{urn:nbn:de:0030-drops-147480},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.55},
  annote =	{Keywords: Sublinear time algorithms, Graph algorithms, Sampling subgraphs, Approximate counting}
}
Document
RANDOM
Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs

Authors: Reut Levi and Nadav Shoshan

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


Abstract
In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In particular, we provide the following algorithms for minor-free unbounded degree graphs. 1) A tester for Hamiltonicity with two-sided error with poly(1/ε)-query complexity, where ε is the proximity parameter. 2) A local algorithm, as defined by Rubinfeld et al. (ICS 2011), for constructing a spanning subgraph with almost minimum weight, specifically, at most a factor (1+ε) of the optimum, with poly(1/ε)-query complexity. Both our algorithms use partition oracles, a tool introduced by Hassidim et al. (FOCS 2009), which are oracles that provide access to a partition of the graph such that the number of cut-edges is small and each part of the partition is small. The polynomial dependence in 1/ε of our algorithms is achieved by combining the recent poly(d/ε)-query partition oracle of Kumar-Seshadhri-Stolman (ECCC 2021) for minor-free graphs with degree bounded by d. For bounded degree minor-free graphs we introduce the notion of covering partition oracles which is a relaxed version of partition oracles and design a poly(d/ε)-time covering partition oracle for this family of graphs. Using our covering partition oracle we provide the same results as above (except that the tester for Hamiltonicity has one-sided error) for minor-free bounded degree graphs, as well as showing that any property which is monotone and additive (e.g. bipartiteness) can be tested in minor-free graphs by making poly(d/ε)-queries. The benefit of using the covering partition oracle rather than the partition oracle in our algorithms is its simplicity and an improved polynomial dependence in 1/ε in the obtained query complexity.

Cite as

Reut Levi and Nadav Shoshan. Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{levi_et_al:LIPIcs.APPROX/RANDOM.2021.61,
  author =	{Levi, Reut and Shoshan, Nadav},
  title =	{{Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{61:1--61:23},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.61},
  URN =		{urn:nbn:de:0030-drops-147540},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.61},
  annote =	{Keywords: Property Testing, Hamiltonian path, minor free graphs, sparse spanning sub-graphs}
}
Document
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Authors: Oded Goldreich and Avi Wigderson

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
A graph G is called self-ordered (a.k.a asymmetric) if the identity permutation is its only automorphism. Equivalently, there is a unique isomorphism from G to any graph that is isomorphic to G. We say that G = (V,E) is robustly self-ordered if the size of the symmetric difference between E and the edge-set of the graph obtained by permuting V using any permutation π:V → V is proportional to the number of non-fixed-points of π. In this work, we initiate the study of the structure, construction and utility of robustly self-ordered graphs. We show that robustly self-ordered bounded-degree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense. Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomial-time (i.e., in time that is poly-logarithmic in the size of the graph). We provide two very different constructions, in tools and structure. The first, a direct construction, is based on proving a sufficient condition for robust self-ordering, which requires that an auxiliary graph is expanding. The second construction is iterative, boosting the property of robust self-ordering from smaller to larger graphs. Structuraly, the first construction always yields expanding graphs, while the second construction may produce graphs that have many tiny (sub-logarithmic) connected components. We also consider graphs of unbounded degree, seeking correspondingly unbounded robustness parameters. We again demonstrate that such graphs (of linear degree) exist (in abundance), and that they can be constructed efficiently, in a strong sense. This turns out to require very different tools. Specifically, we show that the construction of such graphs reduces to the construction of non-malleable two-source extractors (with very weak parameters but with some additional natural features). We demonstrate that robustly self-ordered bounded-degree graphs are useful towards obtaining lower bounds on the query complexity of testing graph properties both in the bounded-degree and the dense graph models. Indeed, their robustness offers efficient, local and distance preserving reductions from testing problems on ordered structures (like sequences) to the unordered (effectively unlabeled) graphs. One of the results that we obtain, via such a reduction, is a subexponential separation between the query complexities of testing and tolerant testing of graph properties in the bounded-degree graph model.

Cite as

Oded Goldreich and Avi Wigderson. Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 12:1-12:74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{goldreich_et_al:LIPIcs.CCC.2021.12,
  author =	{Goldreich, Oded and Wigderson, Avi},
  title =	{{Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{12:1--12:74},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.12},
  URN =		{urn:nbn:de:0030-drops-142867},
  doi =		{10.4230/LIPIcs.CCC.2021.12},
  annote =	{Keywords: Asymmetric graphs, expanders, testing graph properties, two-source extractors, non-malleable extractors, coding theory, tolerant testing, random graphs}
}
Document
Communication Complexity with Defective Randomness

Authors: Marshall Ball, Oded Goldreich, and Tal Malkin

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness. Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over 𝓁 bit strings that have min-entropy at least k ≤ 𝓁. We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in 𝓁-k and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity.

Cite as

Marshall Ball, Oded Goldreich, and Tal Malkin. Communication Complexity with Defective Randomness. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 14:1-14:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.CCC.2021.14,
  author =	{Ball, Marshall and Goldreich, Oded and Malkin, Tal},
  title =	{{Communication Complexity with Defective Randomness}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{14:1--14:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.14},
  URN =		{urn:nbn:de:0030-drops-142886},
  doi =		{10.4230/LIPIcs.CCC.2021.14},
  annote =	{Keywords: Randomized Communication Complexity, Randomness Extraction, Min-Entropy}
}
Document
Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)

Authors: Edward Pyne and Salil Vadhan

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)


Abstract
A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a weighted pseudorandom generator (WPRG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of WPRGs for ordered branching programs whose seed length has a better dependence on the error parameter ε than the classic PRG construction of Nisan (STOC 1990 and Combinatorica 1992). In this work, we give an explicit construction of WPRGs that achieve parameters that are impossible to achieve by a PRG. In particular, we construct a WPRG for ordered permutation branching programs of unbounded width with a single accept state that has seed length Õ(log^{3/2} n) for error parameter ε = 1/poly(n), where n is the input length. In contrast, recent work of Hoza et al. (ITCS 2021) shows that any PRG for this model requires seed length Ω(log² n) to achieve error ε = 1/poly(n). As a corollary, we obtain explicit WPRGs with seed length Õ(log^{3/2} n) and error ε = 1/poly(n) for ordered permutation branching programs of width w = poly(n) with an arbitrary number of accept states. Previously, seed length o(log² n) was only known when both the width and the reciprocal of the error are subpolynomial, i.e. w = n^{o(1)} and ε = 1/n^{o(1)} (Braverman, Rao, Raz, Yehudayoff, FOCS 2010 and SICOMP 2014). The starting point for our results are the recent space-efficient algorithms for estimating random-walk probabilities in directed graphs by Ahmadenijad, Kelner, Murtagh, Peebles, Sidford, and Vadhan (FOCS 2020), which are based on spectral graph theory and space-efficient Laplacian solvers. We interpret these algorithms as giving WPRGs with large seed length, which we then derandomize to obtain our results. We also note that this approach gives a simpler proof of the original result of Braverman, Cohen, and Garg, as independently discovered by Cohen, Doron, Renard, Sberlo, and Ta-Shma (these proceedings).

Cite as

Edward Pyne and Salil Vadhan. Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{pyne_et_al:LIPIcs.CCC.2021.33,
  author =	{Pyne, Edward and Vadhan, Salil},
  title =	{{Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract)}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.33},
  URN =		{urn:nbn:de:0030-drops-143070},
  doi =		{10.4230/LIPIcs.CCC.2021.33},
  annote =	{Keywords: pseudorandomness, space-bounded computation, spectral graph theory}
}
Document
Interactive Proofs for Verifying Machine Learning

Authors: Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff

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


Abstract
We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept good hypotheses, and reject bad hypotheses. Both the verifier and the prover are efficient and have access to labeled data samples from an unknown distribution. We are interested in cases where the verifier can use significantly less data than is required for (agnostic) PAC learning, or use a substantially cheaper data source (e.g., using only random samples for verification, even though learning requires membership queries). We believe that today, when data and data-driven algorithms are quickly gaining prominence, the question of verifying purported outcomes of data analyses is very well-motivated. We show three main results. First, we prove that for a specific hypothesis class, verification is significantly cheaper than learning in terms of sample complexity, even if the verifier engages with the prover only in a single-round (NP-like) protocol. Moreover, for this class we prove that single-round verification is also significantly cheaper than testing closeness to the class. Second, for the broad class of Fourier-sparse boolean functions, we show a multi-round (IP-like) verification protocol, where the prover uses membership queries, and the verifier is able to assess the result while only using random samples. Third, we show that verification is not always more efficient. Namely, we show a class of functions where verification requires as many samples as learning does, up to a logarithmic factor.

Cite as

Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive Proofs for Verifying Machine Learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2021.41,
  author =	{Goldwasser, Shafi and Rothblum, Guy N. and Shafer, Jonathan and Yehudayoff, Amir},
  title =	{{Interactive Proofs for Verifying Machine Learning}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{41:1--41:19},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.41},
  URN =		{urn:nbn:de:0030-drops-135806},
  doi =		{10.4230/LIPIcs.ITCS.2021.41},
  annote =	{Keywords: PAC learning, Fourier analysis of boolean functions, Complexity gaps, Complexity lower bounds, Goldreich-Levin algorithm, Kushilevitz-Mansour algorithm, Distribution testing}
}
  • Refine by Author
  • 13 Goldreich, Oded
  • 3 Ron, Dana
  • 3 Rothblum, Guy N.
  • 2 Ball, Marshall
  • 2 Gur, Tom
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 4 Theory of computation → Interactive proof systems
  • 3 Theory of computation → Complexity classes
  • 3 Theory of computation → Probabilistic computation
  • 3 Theory of computation → Pseudorandomness and derandomization
  • Show More...

  • Refine by Keyword
  • 6 Property Testing
  • 2 Graph algorithms
  • 2 Interactive Proofs
  • 2 Probabilistically checkable proofs
  • 2 Randomness Extraction
  • Show More...

  • Refine by Type
  • 28 document

  • Refine by Publication Year
  • 7 2021
  • 5 2022
  • 3 2019
  • 3 2020
  • 2 2006
  • Show More...

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