3 Search Results for "Rao, Sankeerth"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.33
Singularity of Random Integer Matrices with Large Entries

Authors: Sankeerth Rao Karingula and Shachar Lovett

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

Abstract
We study the singularity probability of random integer matrices. Concretely, the probability that a random n × n matrix, with integer entries chosen uniformly from {-m,…,m}, is singular. This problem has been well studied in two regimes: large n and constant m; or large m and constant n. In this paper, we extend previous techniques to handle the regime where both n,m are large. We show that the probability that such a matrix is singular is m^{-cn} for some absolute constant c > 0. We also provide some connections of our result to coding theory.
Cite as

Sankeerth Rao Karingula and Shachar Lovett. Singularity of Random Integer Matrices with Large Entries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 33:1-33:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{karingula_et_al:LIPIcs.APPROX/RANDOM.2021.33,
  author =	{Karingula, Sankeerth Rao and Lovett, Shachar},
  title =	{{Singularity of Random Integer Matrices with Large Entries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{33:1--33:16},
  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.33},
  URN =		{urn:nbn:de:0030-drops-147260},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.33},
  annote =	{Keywords: Coding Theory, Random matrix theory, Singularity probability MDS codes, Error correction codes, Littlewood Offord, Fourier Analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.13
Torus Polynomials: An Algebraic Approach to ACC Lower Bounds

Authors: Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We propose an algebraic approach to proving circuit lower bounds for ACC^0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC^0 and ACC^0 can be reformulated in this framework, implying that ACC^0 can be approximated by low-degree torus polynomials. Furthermore, as a step towards proving ACC^0 lower bounds for the majority function via our approach, we show that MAJORITY cannot be approximated by low-degree symmetric torus polynomials. We also pose several open problems related to our framework.
Cite as

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao. Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 13:1-13:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bhrushundi_et_al:LIPIcs.ITCS.2019.13,
  author =	{Bhrushundi, Abhishek and Hosseini, Kaave and Lovett, Shachar and Rao, Sankeerth},
  title =	{{Torus Polynomials: An Algebraic Approach to ACC Lower Bounds}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.13},
  URN =		{urn:nbn:de:0030-drops-101066},
  doi =		{10.4230/LIPIcs.ITCS.2019.13},
  annote =	{Keywords: Circuit complexity, ACC, lower bounds, polynomials}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.2
A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n

Authors: Daniel Kane and Sankeerth Rao

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We construct and analyze a pseudorandom generator for degree 2 boolean polynomial threshold functions. Random constructions achieve the optimal seed length of O(log n + log 1/epsilon), however the best known explicit construction of [Ilias Diakonikolas, 2010] uses a seed length of O(log n * epsilon^{-8}). In this work we give an explicit construction that uses a seed length of O(log n + (1/epsilon)^{o(1)}). Note that this improves the seed length substantially and that the dependence on the error epsilon is additive and only grows subpolynomially as opposed to the previously known multiplicative polynomial dependence. Our generator uses dimensionality reduction on a Nisan-Wigderson based pseudorandom generator given by Lu, Kabanets [Kabanets and Lu, 2018].
Cite as

Daniel Kane and Sankeerth Rao. A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 2:1-2:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kane_et_al:LIPIcs.CCC.2018.2,
  author =	{Kane, Daniel and Rao, Sankeerth},
  title =	{{A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{2:1--2:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.2},
  URN =		{urn:nbn:de:0030-drops-88861},
  doi =		{10.4230/LIPIcs.CCC.2018.2},
  annote =	{Keywords: Pseudorandomness, Polynomial Threshold Functions}
}
  • Refine by Author
  • 2 Lovett, Shachar
  • 2 Rao, Sankeerth
  • 1 Bhrushundi, Abhishek
  • 1 Hosseini, Kaave
  • 1 Kane, Daniel
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Pseudorandomness and derandomization
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 ACC
  • 1 Circuit complexity
  • 1 Coding Theory
  • 1 Error correction codes
  • 1 Fourier Analysis
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019
  • 1 2021

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact