Search Results

Documents authored by Moshkovitz, Dana

Document
DOI: 10.4230/LIPIcs.CCC.2024.5
Explicit Time and Space Efficient Encoders Exist Only with Random Access

Authors: Joshua Cook and Dana Moshkovitz

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time n^{1 + o(1)} and space polylog(n) provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [Divsalar et al., 1998] and the codes described in [Gál et al., 2013]. To construct our codes, we also give explicit, efficiently invertible, lossless condensers with constant entropy gap and polylogarithmic seed length. In contrast to encoders with random access to the message, we show that encoders with sequential access to the message can not run in almost linear time and polylogarithmic space. Our notion of sequential access is much stronger than streaming access.
Cite as

Joshua Cook and Dana Moshkovitz. Explicit Time and Space Efficient Encoders Exist Only with Random Access. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 5:1-5:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.CCC.2024.5,
  author =	{Cook, Joshua and Moshkovitz, Dana},
  title =	{{Explicit Time and Space Efficient Encoders Exist Only with Random Access}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{5:1--5:54},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.5},
  URN =		{urn:nbn:de:0030-drops-204015},
  doi =		{10.4230/LIPIcs.CCC.2024.5},
  annote =	{Keywords: Time-Space Trade Offs, Error Correcting Codes, Encoders, Explicit Constructions, Streaming Lower Bounds, Sequential Access, Time-Space Lower Bounds, Lossless Condensers, Invertible Condensers, Condensers}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.39
Regularization of Low Error PCPs and an Application to MCSP

Authors: Shuichi Hirahara and Dana Moshkovitz

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
In a regular PCP the verifier queries each proof symbol in the same number of tests. This number is called the degree of the proof, and it is at least 1/(sq) where s is the soundness error and q is the number of queries. It is incredibly useful to have regularity and reduced degree in PCP. There is an expander-based transformation by Papadimitriou and Yannakakis that transforms any PCP with a constant number of queries and constant soundness error to a regular PCP with constant degree. There are also transformations for low error projection and unique PCPs. Other PCPs are constructed especially to be regular. In this work we show how to regularize and reduce degree of PCPs with a possibly large number of queries and low soundness error. As an application, we prove NP-hardness of an unweighted variant of the collective minimum monotone satisfying assignment problem, which was introduced by Hirahara (FOCS'22) to prove NP-hardness of MCSP^* (the partial function variant of the Minimum Circuit Size Problem) under randomized reductions. We present a simplified proof and sufficient conditions under which MCSP^* is NP-hard under the standard notion of reduction: MCSP^* is NP-hard under deterministic polynomial-time many-one reductions if there exists a function in E that satisfies certain direct sum properties.
Cite as

Shuichi Hirahara and Dana Moshkovitz. Regularization of Low Error PCPs and an Application to MCSP. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ISAAC.2023.39,
  author =	{Hirahara, Shuichi and Moshkovitz, Dana},
  title =	{{Regularization of Low Error PCPs and an Application to MCSP}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.39},
  URN =		{urn:nbn:de:0030-drops-193411},
  doi =		{10.4230/LIPIcs.ISAAC.2023.39},
  annote =	{Keywords: PCP theorem, regularization, Minimum Circuit Size Problem}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.55
Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE

Authors: Joshua Cook and Dana Moshkovitz

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

Abstract
We prove that for some constant a > 1, for all k ≤ a, MATIME[n^{k+o(1)}]/1 ⊄ SIZE[O(n^k)], for some specific o(1) function. This is a super linear polynomial circuit lower bound. Previously, Santhanam [Santhanam, 2007] showed that there exists a constant c > 1 such that for all k > 1: MATIME[n^{ck}]/1 ⊄ SIZE[O(n^k)]. Inherently to Santhanam’s proof, c is a large constant and there is no upper bound on c. Using ideas from Murray and Williams [Murray and Williams, 2018], one can show for all k > 1: MATIME [n^{10 k²}]/1 ⊄ SIZE[O(n^k)]. To prove this result, we construct the first PCP for SPACE[n] with quasi-linear verifier time: our PCP has a Õ(n) time verifier, Õ(n) space prover, O(log(n)) queries, and polynomial alphabet size. Prior to this work, PCPs for SPACE[O(n)] had verifiers that run in Ω(n²) time. This PCP also proves that NE has MIP verifiers which run in time Õ(n).
Cite as

Joshua Cook and Dana Moshkovitz. Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 55:1-55:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.APPROX/RANDOM.2023.55,
  author =	{Cook, Joshua and Moshkovitz, Dana},
  title =	{{Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{55:1--55:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.55},
  URN =		{urn:nbn:de:0030-drops-188805},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.55},
  annote =	{Keywords: MA, PCP, Circuit Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.64
Reduction from Non-Unique Games to Boolean Unique Games

Authors: Ronen Eldan and Dana Moshkovitz

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

Abstract
We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap 1-δ vs. 1-Cδ, for any C > 1, and sufficiently small δ > 0) to the problem of proving a PCP Theorem for a certain non-unique game. In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., without a proof of soundness). The current work is the first to provide an efficient reduction along with a proof of soundness. The non-unique game we reduce from is similar to non-unique games for which PCP theorems are known. Our proof relies on a new concentration theorem for functions in Gaussian space that are restricted to a random hyperplane. We bound the typical Euclidean distance between the low degree part of the restriction of the function to the hyperplane and the restriction to the hyperplane of the low degree part of the function.
Cite as

Ronen Eldan and Dana Moshkovitz. Reduction from Non-Unique Games to Boolean Unique Games. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 64:1-64:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eldan_et_al:LIPIcs.ITCS.2022.64,
  author =	{Eldan, Ronen and Moshkovitz, Dana},
  title =	{{Reduction from Non-Unique Games to Boolean Unique Games}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{64:1--64:25},
  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.64},
  URN =		{urn:nbn:de:0030-drops-156605},
  doi =		{10.4230/LIPIcs.ITCS.2022.64},
  annote =	{Keywords: Unique Games Conjecture, hyperplane encoding, concentration of measure, low degree testing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.24
Near-Optimal Cayley Expanders for Abelian Groups

Authors: Akhil Jalan and Dana Moshkovitz

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
We give an efficient deterministic algorithm that outputs an expanding generating set for any finite abelian group. The size of the generating set is close to the randomized construction of Alon and Roichman [Alon and Roichman, 1994], improving upon various deterministic constructions in both the dependence on the dimension and the spectral gap. By obtaining optimal dependence on the dimension we resolve a conjecture of Azar, Motwani, and Naor [Azar et al., 1998] in the affirmative. Our technique is an extension of the bias amplification technique of Ta-Shma [Ta-Shma, 2017], who used random walks on expanders to obtain expanding generating sets over the additive group of 𝔽₂ⁿ. As a consequence, we obtain (i) randomness-efficient constructions of almost k-wise independent variables, (ii) a faster deterministic algorithm for the Remote Point Problem, (iii) randomness-efficient low-degree tests, and (iv) randomness-efficient verification of matrix multiplication.
Cite as

Akhil Jalan and Dana Moshkovitz. Near-Optimal Cayley Expanders for Abelian Groups. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jalan_et_al:LIPIcs.FSTTCS.2021.24,
  author =	{Jalan, Akhil and Moshkovitz, Dana},
  title =	{{Near-Optimal Cayley Expanders for Abelian Groups}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.24},
  URN =		{urn:nbn:de:0030-drops-155359},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.24},
  annote =	{Keywords: Cayley graphs, Expander walks, Epsilon-biased sets, Derandomization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.31
Randomness Efficient Noise Stability and Generalized Small Bias Sets

Authors: Dana Moshkovitz, Justin Oh, and David Zuckerman

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
We present a randomness efficient version of the linear noise operator T_ρ from boolean function analysis by constructing a sparse linear operator on the space of boolean functions {0,1}ⁿ → {0,1} with similar eigenvalue profile to T_ρ. The linear operator we construct is a direct consequence of a generalization of ε-biased sets to the product distribution 𝒟_p on {0,1}ⁿ where the marginal of each coordinate is p = 1/2-1/2ρ. Such a generalization is a small support distribution that fools linear tests when the input of the test comes from 𝒟_p instead of the uniform distribution. We give an explicit construction of such a distribution that requires log n + O_{p}(log log n + log1/(ε)) bits of uniform randomness to sample from, where the p subscript hides O(log² 1/p) factors. When p and ε are constant, this yields a support size nearly linear in n, whereas previous best known constructions only guarantee a size of poly(n). Furthermore, our construction implies an explicitly constructible "sparse" noisy hypercube graph that is a small set expander.
Cite as

Dana Moshkovitz, Justin Oh, and David Zuckerman. Randomness Efficient Noise Stability and Generalized Small Bias Sets. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{moshkovitz_et_al:LIPIcs.FSTTCS.2020.31,
  author =	{Moshkovitz, Dana and Oh, Justin and Zuckerman, David},
  title =	{{Randomness Efficient Noise Stability and Generalized Small Bias Sets}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.31},
  URN =		{urn:nbn:de:0030-drops-132721},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.31},
  annote =	{Keywords: pseudorandomness, derandomization, epsilon biased sets, noise stability}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.28
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning

Authors: Dana Moshkovitz and Michal Moshkovitz

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses graph. We prove that any hypothesis class whose hypotheses graph is mixing cannot be learned using less than Omega(log^2 |H|) memory bits unless the learner uses at least a large number |H|^Omega(1) labeled examples. Our work builds on a combinatorial framework that we suggested in a previous work for proving lower bounds on space bounded learning. The strong lower bound is obtained by defining a new notion of pseudorandomness, the entropy sampler. Raz obtained a similar result using different ideas.
Cite as

Dana Moshkovitz and Michal Moshkovitz. Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{moshkovitz_et_al:LIPIcs.ITCS.2018.28,
  author =	{Moshkovitz, Dana and Moshkovitz, Michal},
  title =	{{Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.28},
  URN =		{urn:nbn:de:0030-drops-83374},
  doi =		{10.4230/LIPIcs.ITCS.2018.28},
  annote =	{Keywords: learning, space bound, mixing, certainty, entropy sampler}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.42
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian

Authors: Dana Moshkovitz, Govind Ramnarayan, and Henry Yuen

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

Abstract
In this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (STOC'95) proved an impossibility result for randomness-efficient parallel repetition for two prover games with small degree, i.e., when each prover has only few possibilities for the question of the other prover. In recent years, there have been indications that randomness-efficient parallel repetition (also called derandomized parallel repetition) might be possible for games with large degree, circumventing the impossibility result of Feige and Kilian. In particular, Dinur and Meir (CCC'11) construct games with large degree whose repetition can be derandomized using a theorem of Impagliazzo, Kabanets and Wigderson (SICOMP'12). However, obtaining derandomized parallel repetition theorems that would yield optimal inapproximability results has remained elusive. This paper presents an explanation for the current impasse in progress, by proving a limitation on derandomized parallel repetition. We formalize two properties which we call "fortification-friendliness" and "yields robust embeddings". We show that any proof of derandomized parallel repetition achieving almost-linear blow-up cannot both (a) be fortification-friendly and (b) yield robust embeddings. Unlike Feige and Kilian, we do not require the small degree assumption. Given that virtually all existing proofs of parallel repetition, including the derandomized parallel repetition result of Dinur and Meir, share these two properties, our no-go theorem highlights a major barrier to achieving almost-linear derandomized parallel repetition.
Cite as

Dana Moshkovitz, Govind Ramnarayan, and Henry Yuen. A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 42:1-42:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{moshkovitz_et_al:LIPIcs.APPROX-RANDOM.2016.42,
  author =	{Moshkovitz, Dana and Ramnarayan, Govind and Yuen, Henry},
  title =	{{A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{42:1--42:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.42},
  URN =		{urn:nbn:de:0030-drops-66657},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.42},
  annote =	{Keywords: Derandomization, parallel repetition, Feige-Killian, fortification}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.396
Approximating Dense Max 2-CSPs

Authors: Pasin Manurangsi and Dana Moshkovitz

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

Abstract
In this paper, we present a polynomial-time algorithm that approximates sufficiently high-value Max 2-CSPs on sufficiently dense graphs to within O(N^epsilon) approximation ratio for any constant epsilon > 0. Using this algorithm, we also achieve similar results for free games, projection games on sufficiently dense random graphs, and the Densest k-Subgraph problem with sufficiently dense optimal solution. Note, however, that algorithms with similar guarantees to the last algorithm were in fact discovered prior to our work by Feige et al. and Suzuki and Tokuyama. In addition, our idea for the above algorithms yields the following by-product: a quasi-polynomial time approximation scheme (QPTAS) for satisfiable dense Max 2-CSPs with better running time than the known algorithms.
Cite as

Pasin Manurangsi and Dana Moshkovitz. Approximating Dense Max 2-CSPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 396-415, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{manurangsi_et_al:LIPIcs.APPROX-RANDOM.2015.396,
  author =	{Manurangsi, Pasin and Moshkovitz, Dana},
  title =	{{Approximating Dense Max 2-CSPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{396--415},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.396},
  URN =		{urn:nbn:de:0030-drops-53149},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.396},
  annote =	{Keywords: Max 2-CSP, Dense Graphs, Densest k-Subgraph, QPTAS, Free Games, Projection Games}
}
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