1,354,175 research outputs found
Testing Spreading Behavior in Networks with Arbitrary Topologies
No full textPublisher Copyright: © Augusto Modanese and Yuichi Yoshida.Given the full topology of a network, how hard is it to test if it is evolving according to a local rule or is far from doing so? Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every “infected” node stays infected forever, and each “healthy” node becomes infected if and only if it has at least one infected neighbor. Our results are subdivided into two main groups: If we are testing a single time step of evolution, then the query complexity is O(∆/ε) or Õ(√n/ε) (whichever is smaller), where ∆ and n are the maximum degree of a node and the number of vertices in the underlying graph, respectively. We also give lower bounds for both one- and two-sided error testers that match our upper bounds up to ∆ = o(√n) and ∆ = O(n1/3), respectively. If ε is constant, then the first of these also holds against adaptive testers. When testing the environment over T time steps, we have two algorithms that need O(∆T−1/εT) and Õ(|E|/εT) queries, respectively, where E is the set of edges of the underlying graph. All of our algorithms are one-sided error, and all of them are also non-adaptive, with the single exception of the more complex Õ(√n/ε)-query tester for the case T = 2.Peer reviewe
General Properties of the Decay Amplitudes for Massless Particles
No full textWe derive the kinematical constraints which characterize the decay of any massless particle in flat spacetime. We show that in perturbation theory the decay probabilities of photons and Yang-Mills bosons vanish to all orders; the decay probability of the graviton vanishes to one-loop order for graviton loops and to all orders for matter loops. A general power counting argument indicates in which conditions a decay of a massless particle could be possible: the lagrangian should contain a self-coupling without derivatives and with a coupling constant of positive mass dimension
General Properties of the Decay Amplitudes for Massless Particles
No full textWe derive the kinematical constraints which characterize the decay of any massless particle in flat spacetime. We show that in perturbation theory the decay probabilities of photons and Yang-Mills bosons vanish to all orders; the decay probability of the graviton vanishes to one-loop order for graviton loops and to all orders for matter loops. A general power counting argument indicates in which conditions a decay of a massless particle could be possible: the lagrangian should contain a self-coupling without derivatives and with a coupling constant of positive mass dimension
General Properties of the Decay Amplitudes for Massless Particles
No full textWe derive the kinematical constraints which characterize the decay of any massless particle in flat spacetime. We show that in perturbation theory the decay probabilities of photons and Yang-Mills bosons vanish to all orders; the decay probability of the graviton vanishes to one-loop order for graviton loops and to all orders for matter loops. A general power counting argument indicates in which conditions a decay of a massless particle could be possible: the lagrangian should contain a self-coupling without derivatives and with a coupling constant of positive mass dimension
Sublinear-Time Probabilistic Cellular Automata
No full textWe propose and investigate a probabilistic model of sublinear-time
one-dimensional cellular automata. In particular, we modify the model of ACA
(which are cellular automata that accept if and only if all cells
simultaneously accept) so that every cell changes its state not only dependent
on the states it sees in its neighborhood but also on an unbiased coin toss of
its own. The resulting model is dubbed probabilistic ACA (PACA). We consider
one- and two-sided error versions of the model (in the same spirit as the
classes and ) and establish a separation between
the classes of languages they can recognize all the way up to
time. As a consequence, we have a lower bound for
derandomizing constant-time two-sided error PACAs (using deterministic ACAs).
We also prove that derandomization of -time PACAs (to polynomial-time
deterministic cellular automata) for various regimes of
implies non-trivial derandomization results for the class (e.g.,
). The main contribution is an almost full
characterization of the constant-time PACA classes: For one-sided error, the
class equals that of the deterministic model; that is, constant-time one-sided
error PACAs can be fully derandomized with only a constant multiplicative
overhead in time complexity. As for two-sided error, we identify a natural
class we call the linearly testable languages () and prove that
the languages decidable by constant-time two-sided error PACAs are "sandwiched"
in-between the closure of under union and intersection and the
class of locally threshold testable languages ().Comment: 27 pages, 4 figures. Appeared in STACS 2023 (corrected typo in
abstract
Aharonov–Bohm Electrodynamics in Material Media: A Scalar e.m. Field Cannot Cause Dissipation in a Medium
No full textIn the extension of Maxwell equations based on the Aharonov–Bohm Lagrangian, the e.m. field has an additional degree of freedom, namely, a scalar field generated by charge and currents that are not locally conserved. We analyze the propagation of this scalar field through two different media (a pure dielectric and an ohmic conductor) and study its property over a frequency range where the properties of the media are frequency-independent. We find that an electromagnetic (e.m.) scalar wave cannot propagate in a material medium. If a scalar wave in vacuum impinges on a material medium it is reflected, at most exciting in the medium a pure “potential” wave (which we also call a “gauge” wave) propagating at c, the speed of light in vacuum, with a vector potential whose Fourier amplitude is related to that of the scalar potential by (Formula presented.), where (Formula presented.).Fil: Minotti, Fernando Oscar. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Física del Plasma. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Física del Plasma; ArgentinaFil: Modanese, Giovanni. Free University of Bozen-Bolzano; Itali
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
No full text“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
