3 Search Results for "Karnin, Zohar"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.87
Tensor Reconstruction Beyond Constant Rank

Authors: Shir Peleg, Amir Shpilka, and Ben Lee Volk

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

Abstract
We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results: 1) A deterministic algorithm that reconstructs polynomials computed by Σ^{[k]}⋀^{[d]}Σ circuits in time poly(n,d,c) ⋅ poly(k)^{k^{k^{10}}}, 2) A randomized algorithm that reconstructs polynomials computed by multilinear Σ^{[k]}∏^{[d]}Σ circuits in time poly(n,d,c) ⋅ k^{k^{k^{k^{O(k)}}}}, 3) A randomized algorithm that reconstructs polynomials computed by set-multilinear Σ^{[k]}∏^{[d]}Σ circuits in time poly(n,d,c) ⋅ k^{k^{k^{k^{O(k)}}}}, where c = log q if 𝔽 = 𝔽_q is a finite field, and c equals the maximum bit complexity of any coefficient of f if 𝔽 is infinite. Prior to our work, polynomial time algorithms for the case when the rank, k, is constant, were given by Bhargava, Saraf and Volkovich [Vishwas Bhargava et al., 2021]. Another contribution of this work is correcting an error from a paper of Karnin and Shpilka [Zohar Shay Karnin and Amir Shpilka, 2009] (with some loss in parameters) that also affected Theorem 1.6 of [Vishwas Bhargava et al., 2021]. Consequently, the results of [Zohar Shay Karnin and Amir Shpilka, 2009; Vishwas Bhargava et al., 2021] continue to hold, with a slightly worse setting of parameters. For fixing the error we systematically study the relation between syntactic and semantic notions of rank of Σ Π Σ circuits, and the corresponding partitions of such circuits. We obtain our improved running time by introducing a technique for learning rank preserving coordinate-subspaces. Both [Zohar Shay Karnin and Amir Shpilka, 2009] and [Vishwas Bhargava et al., 2021] tried all choices of finding the "correct" coordinates, which, due to the size of the set, led to having a fast growing function of k at the exponent of n. We manage to find these spaces in time that is still growing fast with k, yet it is only a fixed polynomial in n.
Cite as

Shir Peleg, Amir Shpilka, and Ben Lee Volk. Tensor Reconstruction Beyond Constant Rank. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 87:1-87:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{peleg_et_al:LIPIcs.ITCS.2024.87,
  author =	{Peleg, Shir and Shpilka, Amir and Volk, Ben Lee},
  title =	{{Tensor Reconstruction Beyond Constant Rank}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{87:1--87:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.87},
  URN =		{urn:nbn:de:0030-drops-196157},
  doi =		{10.4230/LIPIcs.ITCS.2024.87},
  annote =	{Keywords: Algebraic circuits, reconstruction, tensor decomposition, tensor rank}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.7
𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices

Authors: Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Random subspaces X of ℝⁿ of dimension proportional to n are, with high probability, well-spread with respect to the 𝓁₂-norm. Namely, every nonzero x ∈ X is "robustly non-sparse" in the following sense: x is ε ‖x‖₂-far in 𝓁₂-distance from all δ n-sparse vectors, for positive constants ε, δ bounded away from 0. This "𝓁₂-spread" property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and corresponds to X being a Euclidean section of the 𝓁₁ unit ball. Explicit 𝓁₂-spread subspaces of dimension Ω(n), however, are unknown, and the best known explicit constructions (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of certain sparse matrices. Motivated by this, we study the spread properties of the kernels of sparse random matrices. We prove that with high probability such subspaces contain vectors x that are o(1)⋅‖x‖₂-close to o(n)-sparse with respect to the 𝓁₂-norm, and in particular are not 𝓁₂-spread. This is strikingly different from the case of random LDPC codes, whose distance is asymptotically almost as good as that of (dense) random linear codes. On the other hand, for p < 2 we prove that such subspaces are 𝓁_p-spread with high probability. The spread property of sparse random matrices thus exhibits a threshold behavior at p = 2. Our proof for p < 2 moreover shows that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the 𝓁_p norm, and in fact this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the 𝓁₁ norm [Berinde et al., 2008]. Instantiating this with suitable explicit expanders, we obtain the first explicit constructions of 𝓁_p-RIP matrices for 1 ≤ p < p₀, where 1 < p₀ < 2 is an absolute constant.
Cite as

Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.CCC.2022.7,
  author =	{Guruswami, Venkatesan and Manohar, Peter and Mosheiff, Jonathan},
  title =	{{𝓁\underlinep-Spread and Restricted Isometry Properties of Sparse Random Matrices}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.7},
  URN =		{urn:nbn:de:0030-drops-165695},
  doi =		{10.4230/LIPIcs.CCC.2022.7},
  annote =	{Keywords: Spread Subspaces, Euclidean Sections, Restricted Isometry Property, Sparse Matrices}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.34
Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification

Authors: Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, and Roy Schwartz

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multi-label classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multi-label classification problem, the metric multi-labeling problem, which captures the above applications. We present a (true) O(log{k})-approximation for the general case of metric multi-labeling and a tight 2-approximation for the special case where there is no limit on the number of labels that can be assigned to an object.
Cite as

Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, and Roy Schwartz. Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2017.34,
  author =	{Chen, Shahar and Di Castro, Dotan and Karnin, Zohar and Lewin-Eytan, Liane and Naor, Joseph (Seffi) and Schwartz, Roy},
  title =	{{Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.34},
  URN =		{urn:nbn:de:0030-drops-74612},
  doi =		{10.4230/LIPIcs.ICALP.2017.34},
  annote =	{Keywords: approximation algorithms, randomized rounding, dependent rounding, metric labeling, classification}
}
  • Refine by Author
  • 1 Chen, Shahar
  • 1 Di Castro, Dotan
  • 1 Guruswami, Venkatesan
  • 1 Karnin, Zohar
  • 1 Lewin-Eytan, Liane
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Pseudorandomness and derandomization
  • 1 Theory of computation → Random projections and metric embeddings

  • Refine by Keyword
  • 1 Algebraic circuits
  • 1 Euclidean Sections
  • 1 Restricted Isometry Property
  • 1 Sparse Matrices
  • 1 Spread Subspaces
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2017
  • 1 2022
  • 1 2024

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