2 Search Results for "Agrawal, Rohit"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.59
Samplers and Extractors for Unbounded Functions

Authors: Rohit Agrawal

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

Abstract
Błasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions f from {0,1}^m to the real numbers such that f(U_m) has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact averaging samplers for the broader class of subexponential functions) that match the best known constructions of averaging samplers for [0,1]-bounded functions in the regime of parameters where the approximation error epsilon and failure probability delta are subconstant. Our constructions are established via an extension of the standard notion of randomness extractor (Nisan and Zuckerman, JCSS'96) where the error is measured by an arbitrary divergence rather than total variation distance, and a generalization of Zuckerman’s equivalence (Random Struct. Alg.'97) between extractors and samplers. We believe that the framework we develop, and specifically the notion of an extractor for the Kullback-Leibler (KL) divergence, are of independent interest. In particular, KL-extractors are stronger than both standard extractors and subgaussian samplers, but we show that they exist with essentially the same parameters (constructively and non-constructively) as standard extractors.
Cite as

Rohit Agrawal. Samplers and Extractors for Unbounded Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 59:1-59:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{agrawal:LIPIcs.APPROX-RANDOM.2019.59,
  author =	{Agrawal, Rohit},
  title =	{{Samplers and Extractors for Unbounded Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{59:1--59:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.59},
  URN =		{urn:nbn:de:0030-drops-112749},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.59},
  annote =	{Keywords: averaging samplers, subgaussian samplers, randomness extractors, Kullback-Leibler divergence}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.6
Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees

Authors: Ramprasad Saptharishi and Anamay Tengse

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [Guillaume Lagarde et al., 2016] and Lagarde, Limaye and Srinivasan [Guillaume Lagarde et al., 2017]) and give the following constructions: - An explicit hitting set of quasipolynomial size for UPT circuits, - An explicit hitting set of quasipolynomial size for FewPT circuits (circuits with constantly many parse tree shapes), - An explicit hitting set of polynomial size for UPT circuits (of known parse tree shape), when a parameter of preimage-width is bounded by a constant. The above three results are extensions of the results of [Manindra Agrawal et al., 2015], [Rohit Gurjar et al., 2015] and [Rohit Gurjar et al., 2016] to the setting of UPT circuits, and hence also generalize their results in the commutative world from read-once oblivious algebraic branching programs (ROABPs) to UPT-set-multilinear circuits. The main idea is to study shufflings of non-commutative polynomials, which can then be used to prove suitable depth reduction results for UPT circuits and thereby allow a careful translation of the ideas in [Manindra Agrawal et al., 2015], [Rohit Gurjar et al., 2015] and [Rohit Gurjar et al., 2016].
Cite as

Ramprasad Saptharishi and Anamay Tengse. Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{saptharishi_et_al:LIPIcs.FSTTCS.2018.6,
  author =	{Saptharishi, Ramprasad and Tengse, Anamay},
  title =	{{Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.6},
  URN =		{urn:nbn:de:0030-drops-99050},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.6},
  annote =	{Keywords: Unambiguous Circuits, Read-once Oblivious ABPs, Polynomial Identity Testing, Lower Bounds, Algebraic Circuit Complexity}
}
  • Refine by Author
  • 1 Agrawal, Rohit
  • 1 Saptharishi, Ramprasad
  • 1 Tengse, Anamay

  • Refine by Classification
  • 1 Mathematics of computing → Information theory
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Expander graphs and randomness extractors
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Algebraic Circuit Complexity
  • 1 Kullback-Leibler divergence
  • 1 Lower Bounds
  • 1 Polynomial Identity Testing
  • 1 Read-once Oblivious ABPs
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019

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