3 Search Results for "Luby, Michael"

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.56
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits

Authors: Rocco A. Servedio and Li-Yang Tan

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

Abstract
We study correlation bounds and pseudorandom generators for depth-two circuits that consist of a SYM-gate (computing an arbitrary symmetric function) or THR-gate (computing an arbitrary linear threshold function) that is fed by S {AND} gates. Such circuits were considered in early influential work on unconditional derandomization of Luby, Velickovi{c}, and Wigderson [Michael Luby et al., 1993], who gave the first non-trivial PRG with seed length 2^{O(sqrt{log(S/epsilon)})} that epsilon-fools these circuits. In this work we obtain the first strict improvement of [Michael Luby et al., 1993]'s seed length: we construct a PRG that epsilon-fools size-S {SYM,THR} oAND circuits over {0,1}^n with seed length 2^{O(sqrt{log S})} + polylog(1/epsilon), an exponential (and near-optimal) improvement of the epsilon-dependence of [Michael Luby et al., 1993]. The above PRG is actually a special case of a more general PRG which we establish for constant-depth circuits containing multiple SYM or THR gates, including as a special case {SYM,THR} o AC^0 circuits. These more general results strengthen previous results of Viola [Viola, 2006] and essentially strengthen more recent results of Lovett and Srinivasan [Lovett and Srinivasan, 2011]. Our improved PRGs follow from improved correlation bounds, which are transformed into PRGs via the Nisan-Wigderson "hardness versus randomness" paradigm [Nisan and Wigderson, 1994]. The key to our improved correlation bounds is the use of a recent powerful multi-switching lemma due to Håstad [Johan Håstad, 2014].
Cite as

Rocco A. Servedio and Li-Yang Tan. Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{servedio_et_al:LIPIcs.APPROX-RANDOM.2018.56,
  author =	{Servedio, Rocco A. and Tan, Li-Yang},
  title =	{{Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{56:1--56:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  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.2018.56},
  URN =		{urn:nbn:de:0030-drops-94601},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.56},
  annote =	{Keywords: Pseudorandom generators, correlation bounds, constant-depth circuits}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.52
Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time

Authors: Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study the problem of approximately solving positive linear programs (LPs). This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research, such as many resource allocation problems, solving non-negative linear systems, computing tomography, single/multi commodity flows on graphs, etc. For the special cases of pure packing or pure covering LPs, recent result by Allen-Zhu and Orecchia [Allen/Zhu/Orecchia, SODA'15] gives O˜(1/(epsilon^3))-time parallel algorithm, which breaks the longstanding O˜(1/(epsilon^4)) running time bound by the seminal work of Luby and Nisan [Luby/Nisan, STOC'93]. We present new parallel algorithm with running time O˜(1/(epsilon^3)) for the more general mixed packing and covering LPs, which improves upon the O˜(1/(epsilon^4))-time algorithm of Young [Young, FOCS'01; Young, arXiv 2014]. Our work leverages the ideas from both the optimization oriented approach [Allen/Zhu/Orecchia, SODA'15; Wang/Mahoney/Mohan/Rao, arXiv 2015], as well as the more combinatorial approach with phases [Young, FOCS'01; Young, arXiv 2014]. In addition, our algorithm, when directly applied to pure packing or pure covering LPs, gives a improved running time of O˜(1/(epsilon^2)).
Cite as

Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mahoney_et_al:LIPIcs.ICALP.2016.52,
  author =	{Mahoney, Michael W. and Rao, Satish and Wang, Di and Zhang, Peng},
  title =	{{Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^\{-3\}) Time}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.52},
  URN =		{urn:nbn:de:0030-drops-63335},
  doi =		{10.4230/LIPIcs.ICALP.2016.52},
  annote =	{Keywords: Mixed packing and covering, Linear program, Approximation algorithm, Parallel algorithm}
}
Document
DOI: 10.4230/DagSemRep.14
Randomized Algorithms (Dagstuhl Seminar 9124)

Authors: Marek Karpinski, Michael Luby, and Umesh Vazirani

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Marek Karpinski, Michael Luby, and Umesh Vazirani. Randomized Algorithms (Dagstuhl Seminar 9124). Dagstuhl Seminar Report 14, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1991)

Copy BibTex To Clipboard

@TechReport{karpinski_et_al:DagSemRep.14,
  author =	{Karpinski, Marek and Luby, Michael and Vazirani, Umesh},
  title =	{{Randomized Algorithms (Dagstuhl Seminar 9124)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1991},
  type = 	{Dagstuhl Seminar Report},
  number =	{14},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.14},
  URN =		{urn:nbn:de:0030-drops-149022},
  doi =		{10.4230/DagSemRep.14},
}
  • Refine by Author
  • 1 Karpinski, Marek
  • 1 Luby, Michael
  • 1 Mahoney, Michael W.
  • 1 Rao, Satish
  • 1 Servedio, Rocco A.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Linear program
  • 1 Mixed packing and covering
  • 1 Parallel algorithm
  • 1 Pseudorandom generators
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 1991
  • 1 2016
  • 1 2018

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