2 Search Results for "Dean, Thomas R."

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.58
Pseudorandom Generators for Read-Once Monotone Branching Programs

Authors: Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan

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

Abstract
Motivated by the derandomization of space-bounded computation, there has been a long line of work on constructing pseudorandom generators (PRGs) against various forms of read-once branching programs (ROBPs), with a goal of improving the O(log² n) seed length of Nisan’s classic construction [Noam Nisan, 1992] to the optimal O(log n). In this work, we construct an explicit PRG with seed length Õ(log n) for constant-width ROBPs that are monotone, meaning that the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state. This result is complementary to a line of work that gave PRGs with seed length O(log n) for (ordered) permutation ROBPs of constant width [Braverman et al., 2014; Koucký et al., 2011; De, 2011; Thomas Steinke, 2012], since the monotonicity constraint can be seen as the "opposite" of the permutation constraint. Our PRG also works for monotone ROBPs that can read the input bits in any order, which are strictly more powerful than read-once AC⁰. Our PRG achieves better parameters (in terms of the dependence on the depth of the circuit) than the best previous pseudorandom generator for read-once AC⁰, due to Doron, Hatami, and Hoza [Doron et al., 2019]. Our pseudorandom generator construction follows Ajtai and Wigderson’s approach of iterated pseudorandom restrictions [Ajtai and Wigderson, 1989; Gopalan et al., 2012]. We give a randomness-efficient width-reduction process which proves that the branching program simplifies to an O(log n)-junta after only O(log log n) independent applications of the Forbes-Kelley pseudorandom restrictions [Michael A. Forbes and Zander Kelley, 2018].
Cite as

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan. Pseudorandom Generators for Read-Once Monotone Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 58:1-58:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2021.58,
  author =	{Doron, Dean and Meka, Raghu and Reingold, Omer and Tal, Avishay and Vadhan, Salil},
  title =	{{Pseudorandom Generators for Read-Once Monotone Branching Programs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{58:1--58:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.58},
  URN =		{urn:nbn:de:0030-drops-147513},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.58},
  annote =	{Keywords: Branching programs, pseudorandom generators, constant depth circuits}
}
Document
DOI: 10.4230/DagSemProc.06301.5
Clone Detector Use Questions: A List of Desirable Empirical Studies

Authors: Thomas R. Dean, Massamiliano Di Penta, Kostas Kontogiannis, and Andrew Walenstein

Published in: Dagstuhl Seminar Proceedings, Volume 6301, Duplication, Redundancy, and Similarity in Software (2007)

Abstract
Code "clones" are similar segments of code that are frequently introduced by "scavenging" existing code, that is, reusing code by copying it and adapting it for a new use. In order to scavenge the code, the developer must be aware of it already, or must find it. Little is known about how tools - particularly search tools - impact the clone construction process, nor how developers use them for this purpose. This paper lists five outstanding research questions in this area and proposes sketches of designs for five empirical studies that might be conducted to help shed light on those questions.
Cite as

Thomas R. Dean, Massamiliano Di Penta, Kostas Kontogiannis, and Andrew Walenstein. Clone Detector Use Questions: A List of Desirable Empirical Studies. In Duplication, Redundancy, and Similarity in Software. Dagstuhl Seminar Proceedings, Volume 6301, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{dean_et_al:DagSemProc.06301.5,
  author =	{Dean, Thomas R. and Di Penta, Massamiliano and Kontogiannis, Kostas and Walenstein, Andrew},
  title =	{{Clone Detector Use Questions:  A List of Desirable Empirical Studies}},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6301},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06301.5},
  URN =		{urn:nbn:de:0030-drops-9695},
  doi =		{10.4230/DagSemProc.06301.5},
  annote =	{Keywords: Code clone, clone detector, code search, reuse, code scavenging, empirical study}
}
  • Refine by Author
  • 1 Dean, Thomas R.
  • 1 Di Penta, Massamiliano
  • 1 Doron, Dean
  • 1 Kontogiannis, Kostas
  • 1 Meka, Raghu
  • Show More...

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

  • Refine by Keyword
  • 1 Branching programs
  • 1 Code clone
  • 1 clone detector
  • 1 code scavenging
  • 1 code search
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2007
  • 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact