2,722 research outputs found
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
No full textIn the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among n Boolean vectors in d dimensions. The OV Conjecture (OVC) posits that OV requires n^{2-o(1)} time to solve, for all d=omega(log n). Assuming the OVC, optimal time lower bounds have been proved for many prominent problems in P, such as Edit Distance, Frechet Distance, Longest Common Subsequence, and approximating the diameter of a graph.
We prove that OVC is true in several computational models of interest:
- For all sufficiently large n and d, OV for n vectors in {0,1}^d has branching program complexity Theta~(n * min(n,2^d)). In particular, the lower and upper bounds match up to polylog factors.
- OV has Boolean formula complexity Theta~(n * min(n,2^d)), over all complete bases of O(1) fan-in.
- OV requires Theta~(n * min(n,2^d)) wires, in formulas comprised of gates computing arbitrary symmetric functions of unbounded fan-in.
Our lower bounds basically match the best known (quadratic) lower bounds for any explicit function in those models. Analogous lower bounds hold for many related problems shown to be hard under OVC, such as Batch Partial Match, Batch Subset Queries, and Batch Hamming Nearest Neighbors, all of which have very succinct reductions to OV.
The proofs use a certain kind of input restriction that is different from typical random restrictions where variables are assigned independently. We give a sense in which independent random restrictions cannot be used to show hardness, in that OVC is false in the "average case" even for AC^0 formulas:
For all p in (0,1) there is a delta_p > 0 such that for every n and d, OV instances with input bits independently set to 1 with probability p (and 0 otherwise) can be solved with AC^0 formulas of O(n^{2-delta_p}) size, on all but a o_n(1) fraction of instances. Moreover, lim_{p - > 1}delta_p = 1
Estructura narrativa, ideología y catarsis. Eisenstein en Salvar al soldado Ryan
No full textThis paper highlights the relevance of the structural design of Saving Private Ryan (Steven Spielberg, 1998) in conveying its message, in line with S. M. Eisenstein’s theoretical principles. An analysis of its scenes has been carried out, identifying their emulation of, or “collisions” with, preceding “schemas”. The film presents events characteristic of the classical model of the World War II combat subgenre, but its articulation is unforeseen and evidences authorial action as in the critical model of Vietnam, specifically as in Apocalypse Now (Francis Ford Coppola, 1979). This contrast integrates citizens of different ideological persuasions. It also borrows the structural model and deceptive ending
to a initial enigma from Citizen Kane (Orson Welles, 1941) so as to allude to the same theme: the true essence of man, in this case of the veteran, represented by the elderly Ryan.Este artículo destaca la relevancia del diseño estructural de Salvar al Soldado Ryan (Saving Private Ryan, Steven Spielberg, 1998) para trasladar su mensaje, en línea con los principios teóricos de S. M. Eisenstein. Se ha realizado un análisis de sus escenas, identificando su emulación de “esquemas” precedentes o sus “colisiones” con ellos. La película presenta sucesos propios del modelo clásico del subgénero de combate de la Segunda Guerra Mundial, pero su articulación es azarosa y evidencia la acción autoral como en el modelo crítico de Vietnam, concretamente como en Apocalypse Now (Francis Ford Coppola, 1979). Este contraste integra en el patio de butacas a ciudadanos de diferente signo ideológico. Asimismo, recurre al modelo estructural y un desenlace engañoso próximos a los de Ciudadano Kane (Citizen Kane, Orson Welles, 1941) para aludir a su mismo tema: la verdadera esencia del hombre, en este caso del veterano, representado por el anciano Ryan.Depto. de Periodismo y Comunicación GlobalFac. de Ciencias de la InformaciónTRUEpu
Quasi-cyclic Generalized LDPC codes with low error floors
No full textIn this paper, a novel methodology for designing structured generalized LDPC (G-LDPC) codes is presented. The proposed design results in quasi-cyclic G-LDPC codes for which efficient encoding is feasible through shift-register-based circuits. The structure imposed on the bipartite graphs, together with the choice of simple component codes, leads to a class of codes suitable for fast iterative decoding. A pragmatic approach to the construction of G-LDPC codes is proposed. The approach is based on the substitution of check nodes in the protograph of a low-density parity-check code with stronger nodes based, for instance, on Hamming codes. Such a design approach, which we call LDPC code doping, leads to low-rate quasi-cyclic G-LDPC codes with excellent performance in both the error floor and waterfall regions on the additive white Gaussian noise channel
The Same Old New Normal
No full textJournal #14 from Media Rise's Quarantined Across Borders Collection by Ryan Arron D'Souza. From United Arab Emirates. Quarantined in United States, Florida.Media Rise Publications. Quarantined Across Borders Collection. Edited by Dr. Srividya "Srivi" Ramasubramanian.The author tries to make sense of the ideas and practices normalized during quarantine
How Form and Function Create Community in the Middle Landscape
No full textThe middle landscape, more commonly referred to as Suburbia, has become spatially discontinuous, lacking the cohesive union, open spaces and city centers that once defined community. Presently, the middle landscape's community spaces do not offer the opportunity for familiar and chance encounters or ritual activity. Large-scale housing development in Northern Virginia and in the mid-Atlantic region is continually segregating and ultimately destroying community and all links to the area's history.
Located in Southern Fairfax County, the newly abandoned Lorton Central and Maximum Security Prison Facility provides an opportunity to serve as a catalyst for community in this area. This thesis investigates the historic precedence for creating successful community centers. The author's personal investigation is focused upon using form and function to accomplish this vision. By adaptively reusing the existing architecture alongside new construction, the intent is to create a dense urban town center at the abandoned historic site.Master of Landscape Architectur
A Bayesian hierarchical model for risk assessment of methylmercury
No full textThis article uses a Bayesian hierarchical model to quantify the adverse health effects associated with in-utero exposure to methylmercury. By allowing for study-to-study as well as outcome-to-outcome variability, the approach provides a useful meta-analytic tool for multi-outcome, multi-study environmental risk assessments. The analysis presented here expands on the findings of a National Academy of Sciences (NAS) committee, charged with advising the United States Environmental Protection Agency (EPA) on an appropriate approach to conducting a risk assessment for methylmercury. The NAS committee, for which the senior author (Ryan) was a committee member, reviewed the findings from several conflicting studies and reported the results from a Bayesian hierarchical model that synthesized information across several studies and for several outcomes. Although the NAS committee did not suggest that the hierarchical model be used as the actual basis for a methylmercury risk assessment, the results from the model were used to justify and support the final recommendation that the risk analysis be based on data from a study conducted in the Faroe Islands, which had found an association between in-utero exposure to methylmercury and impaired neurological development. We consider a variety of statistical issues, but particularly sensitivity to model specification. © 2003 American Statistical Association and the International Biometric Society
Novel multi-electrode probe with three dimensional spatial resolution for simultaneous recording/stimulation in long-term adaptive deep brain stimulaton
No full textWhen treating neurological disorders such as Parkinson’s Disease (PD) modern technologies experience many deficiencies and/or limitations that researchers have been working towards improving. The problems that occur with modern devices are inadequate mechanical robustness, glial scarring due to tissue damage, reduced target area localization, and inability to simultaneously record/stimulate in vivo post implantation. The research presented here resolves the issues stated above, delivering the design of a novel Multi-Electrode Probe with 3-D spatial resolution and an on-board preamplification/filtering chip capable of simultaneous recording/stimulation. The probe has been modeled in Wildfire Pro/Engineer 4.0 and Finite Element Analysis (FEA) was performed in COMSOL Multiphysics 3.4. The neural chip which consists of both analog and digital circuitry was designed with Taiwan Semiconductor’s (TSMC) 0.18µm CMOS technology. The very large scale integration (VLSI) design and simulation was performed in Cadence Schematic and Spectre, respectively. The aforementioned work was done in hopes of delivering a neural probe that can eventually be used in a closed loop system for Adaptive Deep Brain Stimulation treatment.Ph.D.Includes bibliographical referencesIncludes vitaby Ryan M. Elkhol
The orthogonal vectors conjecture for branching programs and formulas
No full text© Daniel M. Kane and R. Ryan Williams. In the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among n Boolean vectors in d dimensions. The OV Conjecture (OVC) posits that OV requires n2−o(1) time to solve, for all d = ω(log n). Assuming the OVC, optimal time lower bounds have been proved for many prominent problems in P, such as Edit Distance, Frechet Distance, Longest Common Subsequence, and approximating the diameter of a graph. We prove that OVC is true in several computational models of interest: ▬ For all sufficiently large n and d, OV for n vectors in {0, 1}d has branching program complexity Θ(n · min(n, 2d)). In particular, the lower and upper bounds match up to polylog factors. ▬ OV has Boolean formula complexity Θ(n · min(n, 2d)), over all complete bases of O(1) fan-in. ▬ OV requires Θ(n · min(n, 2d)) wires, in formulas comprised of gates computing arbitrary symmetric functions of unbounded fan-in. Our lower bounds basically match the best known (quadratic) lower bounds for any explicit function in those models. Analogous lower bounds hold for many related problems shown to be hard under OVC, such as Batch Partial Match, Batch Subset Queries, and Batch Hamming Nearest Neighbors, all of which have very succinct reductions to OV. The proofs use a certain kind of input restriction that is different from typical random restrictions where variables are assigned independently. We give a sense in which independent random restrictions cannot be used to show hardness, in that OVC is false in the “average case” even for AC0 formulas: For all p ∈ (0, 1) there is a δp > 0 such that for every n and d, OV instances with input bits independently set to 1 with probability p (and 0 otherwise) can be solved with AC0 formulas of O(n2−δp ) size, on all but a on(1) fraction of instances. Moreover, limp→1 δp = 1
Corrigendum: Expression analysis of candidate genes regulating successional tooth formation in the human embryo
No full textA corrigendum on
Expression analysis of candidate genes regulating successional tooth formation in the human embryo
by Olley, R., Xavier, G. M., Seppala, M., Volponi, A. A., Geoghegan, F., Sharpe, P. T., et al. (2014). Front. Physiol. 5:445. doi: 10.3389/fphys.2014.00445
The author Ryan Olley should appear as Olley RC on the published article “Expression analysis of candidate genes regulating successional tooth formation in the human embryo.”
The original article was updated
Shifting and persosting in the face of failure: Learning from what did not work
No full textSocial justice activism demands coordinated, concentrated efforts to move the needle in a positive direction. In the author's nine years as a social justice educator, he led multiple large- and small-scale projects for social justice within higher education. In many ways, those efforts failed to create a lasting impact. In the higher education ecosystem, they also took away time from the kind of promotable work which would benefit his case for tenure and promotion. Trying - and failing - to effect institutional changes left him emotionally, psychologically, and physically exhausted. Beyond that, he suffered from feelings of loneliness, exclusion, and lack of direction. For a long time, the author blamed himself for the failure to change the institution to be a place in which he felt comfortable. He also failed to cope with these negative experiences and emotions, often seething in frustration or anger or avoiding similar situations of vulnerability or creativity. It took years for him to remember and internalize lessons of persistence and shifting appraisals in order to maintain motivation for action and survive the stressors of working within an oppressive system.Published versio
- …
