More Like this
-
Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time (dm + N)1+o(1) · poly(m, d, log |F|) for all m ∈ N and all sufficiently large d ∈ N. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most d^{o(1)} and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than d^{o(1)}. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously knownalgorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri–Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in d of bounded height.more » « less
-
more » « less
Abstract We present the results of processing the effects of the powerful gamma-ray burst GRB221009A captured by the charged particle detectors (electrostatic analyzers and solid-state detectors) on board spacecraft at different points in the heliosphere on 2022 October 9. To follow the GRB221009A propagation through the heliosphere, we used the electron and proton flux measurements from solar missions Solar Orbiter and STEREO-A; Earth’s magnetosphere and solar wind missions THEMIS and Wind; meteorological satellites POES15, POES19, and MetOp3; and MAVEN—a NASA mission orbiting Mars. GRB221009A had a structure of four bursts: the less intense Pulse 1—the triggering impulse—was detected by gamma-ray observatories at
T 0= 13:16:59 UT (near the Earth); the most intense Pulses 2 and 3 were detected on board all the spacecraft from the list; and Pulse 4 was detected in more than 500 s after Pulse 1. Due to their different scientific objectives, the spacecraft, whose data were used in this study, were separated by more than 1 au (Solar Orbiter and MAVEN). This enabled the tracking of GRB221009A as it was propagating across the heliosphere. STEREO-A was the first to register Pulse 2 and 3 of the GRB, almost 100 s before their detection by spacecraft in the vicinity of Earth. MAVEN detected GRB221009A Pulses 2, 3, and 4 at the orbit of Mars about 237 s after their detection near Earth. By processing the observed time delays, we show that the source location of the GRB221009A was at R.A. 288.°5, decl. 18.°5 ± 2° (J2000).
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
