197,343 research outputs found
Evans Library-Richard Pyne Coll. - 3
No full textEvans Library-Richard Pyne Coll.photograph date: Unknow
Residence and gardens, M. Taylor Pyne Estate, Princeton, N.J.
No full textM. Taylor Pyne Estate, Princeton, New Jersey, circa 1915-1930. Postcard number: A75850
Combustion and Society: A Fire-Centred History of Energy Use
No full textFire is a force that links everyday human activities to some of the most powerful energetic movements of the Earth. Drawing together the energy-centred social theory of Georges Bataille, the fire-centred environmental history of Stephen Pyne, and the work of a number of ‘pyrotechnology’ scholars, the paper proposes that the generalized study of combustion is a key to contextualizing human energetic practices within a broader ‘economy’ of terrestrial and cosmic energy flows. We examine the relatively recent turn towards fossil-fuelled ‘internal combustion’ in the light of a much longer human history of ‘broadcast’ burning of vegetation and of artisanal pyrotechnologies – the use of heat to transform diverse materials. A combustion-centred analysis, it is argued, brings human collective life into closer contact with the geochemical and geologic conditions of earthly existence, while also pointing to the significance of explorative, experimental and even playful dispositions towards energy and matter. © 2014, SAGE Publications. All rights reserved
Hitting Sets for Regular Branching Programs
No full textWe construct improved hitting set generators (HSGs) for ordered (read-once) regular branching programs in two parameter regimes. First, we construct an explicit ε-HSG for unbounded-width regular branching programs with a single accept state with seed length Õ(log n ⋅ log(1/ε)), where n is the length of the program. Second, we construct an explicit ε-HSG for width-w length-n regular branching programs with seed length Õ(log n ⋅ (√{log(1/ε)} + log w) + log(1/ε)). For context, the "baseline" in this area is the pseudorandom generator (PRG) by Nisan (Combinatorica 1992), which fools ordered (possibly non-regular) branching programs with seed length O(log(wn/ε) ⋅ log n). For regular programs, the state-of-the-art PRG, by Braverman, Rao, Raz, and Yehudayoff (FOCS 2010, SICOMP 2014), has seed length Õ(log(w/ε) ⋅ log n), which beats Nisan’s seed length when log(w/ε) = o(log n). Taken together, our two new constructions beat Nisan’s seed length in all parameter regimes except when log w and log(1/ε) are both Ω(log n) (for the construction of HSGs for regular branching programs with a single accept vertex).
Extending work by Reingold, Trevisan, and Vadhan (STOC 2006), we furthermore show that an explicit HSG for regular branching programs with a single accept vertex with seed length o(log² n) in the regime log w = Θ(log(1/ε)) = Θ(log n) would imply improved HSGs for general ordered branching programs, which would be a major breakthrough in derandomization. Pyne and Vadhan (CCC 2021) recently obtained such parameters for the special case of permutation branching programs
Blair Hall, Henry Hall and Pyne Hall, Princeton University, Princeton, New Jersey, circa 1951-1970
No full textBlair Hall, Henry Hall and Pyne Hall, Princeton University, Princeton, New Jersey, circa 1951-1970. Caption reads: "Princeton University. Princeton, Mercer County, New Jersey. This scene shows the dormitories of Blair Hall, center, Henry Hall, left, and Pyne Hall, right. The gates in the foreground were given in memory of M. Hartley Dodge, Jr., Class of 1930." Postcard number: 66557
Pseudorandom Linear Codes Are List-Decodable to Capacity
No full textWe introduce a novel family of expander-based error correcting codes. These codes can be sampled with randomness linear in the block-length, and achieve list decoding capacity (among other local properties). Our expander-based codes can be made starting from any family of sufficiently low-bias codes, and as a consequence, we give the first construction of a family of algebraic codes that can be sampled with linear randomness and achieve list-decoding capacity. We achieve this by introducing the notion of a pseudorandom puncturing of a code, where we select n indices of a base code C ⊂ _q^m in a correlated fashion. Concretely, whereas a random linear code (i.e. a truly random puncturing of the Hadamard code) requires O(n log(m)) random bits to sample, we sample a pseudorandom linear code with O(n + log (m)) random bits by instantiating our pseudorandom puncturing as a length n random walk on an exapnder graph on [m]. In particular, we extend a result of Guruswami and Mosheiff (FOCS 2022) and show that a pseudorandom puncturing of a small-bias code satisfies the same local properties as a random linear code with high probability. As a further application of our techniques, we also show that pseudorandom puncturings of Reed-Solomon codes are list-recoverable beyond the Johnson bound, extending a result of Lund and Potukuchi (RANDOM 2020). We do this by instead analyzing properties of codes with large distance, and show that pseudorandom puncturings still work well in this regime
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
No full textWe prove that the Impagliazzo-Nisan-Wigderson [Impagliazzo et al., 1994] pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of Õ(log d + log n ⋅ log(1/ε)), assuming the program has only one accepting vertex in the final layer. Here, n is the length of the program, d is the degree (equivalently, the alphabet size), and ε is the error of the PRG. In contrast, we show that a randomly chosen generator requires seed length Ω(n log d) to fool such unbounded-width programs. Thus, this is an unusual case where an explicit construction is "better than random."
Except when the program’s width w is very small, this is an improvement over prior work. For example, when w = poly(n) and d = 2, the best prior PRG for permutation branching programs was simply Nisan’s PRG [Nisan, 1992], which fools general ordered branching programs with seed length O(log(wn/ε) log n). We prove a seed length lower bound of Ω̃(log d + log n ⋅ log(1/ε)) for fooling these unbounded-width programs, showing that our seed length is near-optimal. In fact, when ε ≤ 1/log n, our seed length is within a constant factor of optimal. Our analysis of the INW generator uses the connection between the PRG and the derandomized square of Rozenman and Vadhan [Rozenman and Vadhan, 2005] and the recent analysis of the latter in terms of unit-circle approximation by Ahmadinejad et al. [Ahmadinejad et al., 2020]
- …
