Showing 1–50 of 56 results for author: Charalampopoulos, P

Internal Pattern Matching in Small Space and Applications

Authors: Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya

Abstract: In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our main contribution is a space-time trade-off for the Internal Pattern Matching (IPM) problem, where the goal is to construct a data structure over a string $S$ of length $n$ that allows one to answer the following type of qu… ▽ More In this work, we consider pattern matching variants in small space, that is, in the read-only setting, where we want to bound the space usage on top of storing the strings. Our main contribution is a space-time trade-off for the Internal Pattern Matching (IPM) problem, where the goal is to construct a data structure over a string $S$ of length $n$ that allows one to answer the following type of queries: Compute the occurrences of a fragment $P$ of $S$ inside another fragment $T$ of $S$, provided that $|T| < 2|P|$. For any $τ\in [1 .. n/\log^2 n]$, we present a nearly-optimal $Õ(n/τ)$-size data structure that can be built in $Õ(n)$ time using $Õ(n/τ)$ extra space, and answers IPM queries in $O(τ+\log n \log^3 \log n)$ time. IPM queries have been identified as a crucial primitive operation for the analysis of algorithms on strings. In particular, the complexities of several recent algorithms for approximate pattern matching are expressed with regards to the number of calls to a small set of primitive operations that include IPM queries; our data structure allows us to port these results to the small-space setting. We further showcase the applicability of our IPM data structure by using it to obtain space-time trade-offs for the longest common substring and circular pattern matching problems in the asymmetric streaming setting. △ Less

Submitted 26 April, 2024; originally announced April 2024.

Comments: To be published in CPM 2024

Optimal Bounds for Distinct Quartics

Authors: Panagiotis Charalampopoulos, Paweł Gawrychowski, Samah Ghazawi

Abstract: A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the most basic questions is how many distinct squares, i.e., distinct strings of the form $UU$, a string of length $n$ can contain as fragments. It turns out that this is always $\mathcal{O}(n)$, and the bound cannot be imp… ▽ More A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the most basic questions is how many distinct squares, i.e., distinct strings of the form $UU$, a string of length $n$ can contain as fragments. It turns out that this is always $\mathcal{O}(n)$, and the bound cannot be improved to sublinear in $n$ [Fraenkel and Simpson, JCTA 1998]. Several similar questions about repetitions in strings have been considered, and by now we seem to have a good understanding of their repetitive structure. For higher-dimensional strings, the basic concept of periodicity has been successfully extended and applied to design efficient algorithms -- it is inherently more complex than for regular strings. Extending the notion of repetitions and understanding the repetitive structure of higher-dimensional strings is however far from complete. Quartics were introduced by Apostolico and Brimkov [TCS 2000] as analogues of squares in two dimensions. Charalampopoulos, Radoszewski, Rytter, Waleń, and Zuba [ESA 2020] proved that the number of distinct quartics in an $n\times n$ 2D string is $\mathcal{O}(n^2 \log^2 n)$ and that they can be computed in $\mathcal{O}(n^2 \log^2 n)$ time. Gawrychowski, Ghazawi, and Landau [SPIRE 2021] constructed an infinite family of $n \times n$ 2D strings with $Ω(n^2 \log n)$ distinct quartics. This brings the challenge of determining asymptotically tight bounds. Here, we settle both the combinatorial and the algorithmic aspects of this question: the number of distinct quartics in an $n\times n$ 2D string is $\mathcal{O}(n^2 \log n)$ and they can be computed in the worst-case optimal $\mathcal{O}(n^2 \log n)$ time. △ Less

Submitted 11 March, 2024; originally announced March 2024.

Comments: Abstract abridged due to arXiv requirements. 33 pages, 11 figures

The extreme coronal line emitter AT 2022fpx: Varying optical polarization properties and late-time X-ray flare

Authors: Karri I. I. Koljonen, Ioannis Liodakis, Elina Lindfors, Kari Nilsson, Thomas M. Reynolds, Panos Charalampopoulos, Konstantinos Kouroumpatzakis, Callum McCall, Helen E. Jermak, Iain A. Steele, Juan Carbajo-Hijarrubia

Abstract: Supermassive black holes disrupt passing stars, producing outbursts called tidal disruption events (TDEs). TDEs have recently gained attention due to their unique dynamics and emission processes, which are still not fully understood. Especially, the so-called optical TDEs, are of interest as they often exhibit delayed or obscured X-ray emission from the accretion disk, making the origin of the pro… ▽ More Supermassive black holes disrupt passing stars, producing outbursts called tidal disruption events (TDEs). TDEs have recently gained attention due to their unique dynamics and emission processes, which are still not fully understood. Especially, the so-called optical TDEs, are of interest as they often exhibit delayed or obscured X-ray emission from the accretion disk, making the origin of the prompt emission unclear. In this paper, we present multiband optical polarization observations and optical spectrometry of a recent TDE candidate AT 2022fpx, alongside monitoring observations in optical, ultraviolet and X-rays. The optical spectra of AT 2022fpx show Bowen fluorescence as well as highly-ionized iron emission lines, which are characteristic of extreme coronal line emitters. Additionally, the source exhibits variable but low-polarized continuum emission at the outburst peak, with a clear rotation of the polarization angle. X-ray emission observed approximately 250 days after the outburst peak in the decay appear flare-like but is consistent with constant temperature black-body emission. The overall outburst decay is slower than for typical TDEs, and resembles more the ones seen from Bowen fluorescence flares. These observations suggest that AT 2022fpx could be a key source in linking different long-lived TDE scenarios. Its unique characteristics, such as extreme coronal line emission, variable polarization, and delayed X-ray flare, can be attributed to the outer shock scenario or a clumpy torus surrounding the supermassive black hole. Further studies, especially in the context of multi-wavelength observations, are crucial to fully understand the dynamics and emission mechanisms of these intriguing astrophysical events. △ Less

Submitted 13 June, 2024; v1 submitted 7 March, 2024; originally announced March 2024.

Comments: 13 pages, 9 figures, 1 table. This article has been accepted for publication in MNRAS published by Oxford University Press on behalf of the Royal Astronomical Society. Updated to match the accepted version

Approximate Circular Pattern Matching under Edit Distance

Authors: Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba

Abstract: In the $k$-Edit Circular Pattern Matching ($k$-Edit CPM) problem, we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a positive integer threshold $k$, and we are to report all starting positions of the substrings of $T$ that are at edit distance at most $k$ from some cyclic rotation of $P$. In the decision version of the problem, we are to check if any such substring exists. Very re… ▽ More In the $k$-Edit Circular Pattern Matching ($k$-Edit CPM) problem, we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a positive integer threshold $k$, and we are to report all starting positions of the substrings of $T$ that are at edit distance at most $k$ from some cyclic rotation of $P$. In the decision version of the problem, we are to check if any such substring exists. Very recently, Charalampopoulos et al. [ESA 2022] presented $O(nk^2)$-time and $O(nk \log^3 k)$-time solutions for the reporting and decision versions of $k$-Edit CPM, respectively. Here, we show that the reporting and decision versions of $k$-Edit CPM can be solved in $O(n+(n/m) k^6)$ time and $O(n+(n/m) k^5 \log^3 k)$ time, respectively, thus obtaining the first algorithms with a complexity of the type $O(n+(n/m) \mathrm{poly}(k))$ for this problem. Notably, our algorithms run in $O(n)$ time when $m=Ω(k^6)$ and are superior to the previous respective solutions when $m=ω(k^4)$. We provide a meta-algorithm that yields efficient algorithms in several other interesting settings, such as when the strings are given in a compressed form (as straight-line programs), when the strings are dynamic, or when we have a quantum computer. We obtain our solutions by exploiting the structure of approximate circular occurrences of $P$ in $T$, when $T$ is relatively short w.r.t. $P$. Roughly speaking, either the starting positions of approximate occurrences of rotations of $P$ form $O(k^4)$ intervals that can be computed efficiently, or some rotation of $P$ is almost periodic (is at a small edit distance from a string with small period). Dealing with the almost periodic case is the most technically demanding part of this work; we tackle it using properties of locked fragments (originating from [Cole and Hariharan, SICOMP 2002]). △ Less

Submitted 22 February, 2024; originally announced February 2024.

Comments: Full version of a paper accepted to STACS 2024

Pattern Matching with Mismatches and Wildcards

Authors: Gabriel Bathie, Panagiotis Charalampopoulos, Tatiana Starikovskaya

Abstract: In this work, we address the problem of approximate pattern matching with wildcards. Given a pattern $P$ of length $m$ containing $D$ wildcards, a text $T$ of length $n$, and an integer $k$, our objective is to identify all fragments of $T$ within Hamming distance $k$ from $P$. Our primary contribution is an algorithm with runtime $O(n+(D+k)(G+k)\cdot n/m)$ for this problem. Here, $G \le D$ repr… ▽ More In this work, we address the problem of approximate pattern matching with wildcards. Given a pattern $P$ of length $m$ containing $D$ wildcards, a text $T$ of length $n$, and an integer $k$, our objective is to identify all fragments of $T$ within Hamming distance $k$ from $P$. Our primary contribution is an algorithm with runtime $O(n+(D+k)(G+k)\cdot n/m)$ for this problem. Here, $G \le D$ represents the number of maximal wildcard fragments in $P$. We derive this algorithm by elaborating in a non-trivial way on the ideas presented by [Charalampopoulos et al., FOCS'20] for pattern matching with mismatches (without wildcards). Our algorithm improves over the state of the art when $D$, $G$, and $k$ are small relative to $n$. For instance, if $m = n/2$, $k=G=n^{2/5}$, and $D=n^{3/5}$, our algorithm operates in $O(n)$ time, surpassing the $Ω(n^{6/5})$ time requirement of all previously known algorithms. In the case of exact pattern matching with wildcards ($k=0$), we present a much simpler algorithm with runtime $O(n+DG\cdot n/m)$ that clearly illustrates our main technical innovation: the utilisation of positions of $P$ that do not belong to any fragment of $P$ with a density of wildcards much larger than $D/m$ as anchors for the sought (approximate) occurrences. Notably, our algorithm outperforms the best-known $O(n\log m)$-time FFT-based algorithms of [Cole and Hariharan, STOC'02] and [Clifford and Clifford, IPL'04] if $DG = o(m\log m)$. We complement our algorithmic results with a structural characterization of the $k$-mismatch occurrences of $P$. We demonstrate that in a text of length $O(m)$, these occurrences can be partitioned into $O((D+k)(G+k))$ arithmetic progressions. Additionally, we construct an infinite family of examples with $Ω((D+k)k)$ arithmetic progressions of occurrences, leveraging a combinatorial result on progression-free sets [Elkin, SODA'10]. △ Less

Submitted 21 May, 2024; v1 submitted 12 February, 2024; originally announced February 2024.

Comments: This version contains a fix in the proof of Theorem 3.10 and other minor changes

The enigmatic double-peaked stripped-envelope SN 2023aew

Authors: Tuomas Kangas, Hanindyo Kuncarayakti, Takashi Nagao, Rubina Kotak, Erkki Kankare, Morgan Fraser, Heloise Stevance, Seppo Mattila, Kei'ichi Maeda, Maximilian Stritzinger, Peter Lundqvist, Nancy Elias-Rosa, Lucía Ferrari, Gastón Folatelli, Christopher Frohmaier, Lluís Galbany, Miho Kawabata, Eleni Koutsiona, Tomás E. Müller-Bravo, Lara Piscarreta, Miika Pursiainen, Avinash Singh, Kenta Taguchi, Rishabh Singh Teja, Giorgio Valerin , et al. (7 additional authors not shown)

Abstract: We present optical and near-infrared photometry and spectroscopy of SN 2023aew and our findings on its remarkable properties. This event, initially resembling a Type IIb supernova (SN), rebrightens dramatically $\sim$90 d after the first peak, at which time its spectrum transforms into that of a SN Ic. The slowly evolving spectrum specifically resembles a post-peak SN~Ic with relatively low line v… ▽ More We present optical and near-infrared photometry and spectroscopy of SN 2023aew and our findings on its remarkable properties. This event, initially resembling a Type IIb supernova (SN), rebrightens dramatically $\sim$90 d after the first peak, at which time its spectrum transforms into that of a SN Ic. The slowly evolving spectrum specifically resembles a post-peak SN~Ic with relatively low line velocities even during the second rise. The second peak, reached 119 d after the first peak, is both more luminous ($M_r = -18.75\pm0.04$ mag) and much broader than those of typical SNe Ic. Blackbody fits to SN 2023aew indicate that the photosphere shrinks almost throughout its observed evolution, and the second peak is caused by an increasing temperature. Bumps in the light curve after the second peak suggest interaction with circumstellar matter (CSM) or possibly accretion. We consider several scenarios for producing the unprecedented behavior of SN 2023aew. Two separate SNe, either unrelated or from the same binary system, require either an incredible coincidence or extreme fine-tuning. A pre-SN eruption followed by a SN requires an extremely powerful, SN-like eruption (consistent with $\sim$10$^{51}$ erg) and is also disfavored. We therefore consider only the first peak a true stellar explosion. The observed evolution is difficult to reproduce if the second peak is dominated by interaction with a distant CSM shell. A delayed internal heating mechanism is more likely, but emerging embedded interaction with a CSM disk should be accompanied by CSM lines in the spectrum, which are not observed, and is difficult to hide long enough. A magnetar central engine requires a delayed onset to explain the long time between the peaks. Delayed fallback accretion onto a black hole may present the most promising scenario, but we cannot definitively establish the power source. △ Less

Submitted 17 June, 2024; v1 submitted 30 January, 2024; originally announced January 2024.

Comments: 21 pages + 14 appendix pages, 16 figures + 6 appendix figures. Accepted by A&A

The fast transient AT 2023clx in the nearby LINER galaxy NGC 3799, as a tidal disruption event of a very low-mass star

Authors: P. Charalampopoulos, R. Kotak, T. Wevers, G. Leloudas, T. Kravtsov, P. Ramsden, T. M. Reynolds, A. Aamer, J. P. Anderson, I. Arcavi, Y. -Z. Cai, T. -W. Chen, M. Dennefeld, L. Galbany, M. Gromadzki, C. P. Gutiérrez, N. Ihanec, T. Kangas, E. Kankare, E. Kool, A. Lawrence, L. Makrygianni, S. Mattila, T. E. Müller-Bravo, M. Nicholl , et al. (7 additional authors not shown)

Abstract: We present an extensive analysis of the optical and UV properties of AT2023clx, the closest TDE to date, that occurred in the nucleus of the interacting LINER galaxy, NGC3799 (z=0.01107). From several standard methods, we estimate the mass of the central SMBH to be ~ 10^6 Msol. After correcting for the host reddening (E(B-V) = 0.177 mag) we measured its peak absolute g-band magnitude to be -18.25\… ▽ More We present an extensive analysis of the optical and UV properties of AT2023clx, the closest TDE to date, that occurred in the nucleus of the interacting LINER galaxy, NGC3799 (z=0.01107). From several standard methods, we estimate the mass of the central SMBH to be ~ 10^6 Msol. After correcting for the host reddening (E(B-V) = 0.177 mag) we measured its peak absolute g-band magnitude to be -18.25\pm0.05 mag, and its peak bolometric luminosity to be L_pk=(3.24\pm0.36)x10^43erg/s, making AT2023clx an intermediate luminosity TDE. The first distinctive feature of AT2023clx is that it rose to peak within only 10.4\pm2.5 days, making it the fastest rising TDE to date. Our SMBH mass estimate rules out the possibility of an intermediate mass BH as the reason of the fast rise. Dense spectral follow-up revealed a blue continuum that cools slowly and broad Balmer and HeII lines as well as weak HeI emission, features that are typically seen in TDEs. A flat Balmer decrement (~ 1.58) suggests that the lines are collisionally excited rather than being produced via photoionisation, as in typical active galactic nuclei. A second distinctive feature, seen for the first time in TDE spectra, is a sharp, narrow emission peak at a rest wavelength of ~6353 A. This feature is clearly visible up to 10d post-peak; we attribute it to clumpy material preceding the bulk outflow, and manifested as a high-velocity component of Ha (-9584km/s). The third distinctive feature is a break observed in the near-UV light curves that is reflected as a dip in the temperature evolution around ~18-28 days post-peak. Combining these findings, we propose a scenario for AT2023clx involving the disruption of a very low-mass star (<=0.1Msol) with an outflow launched in our line-of-sight with disruption properties that led to circularisation and prompt and efficient accretion disc formation, observed through a low-density photosphere. △ Less

Submitted 22 January, 2024; originally announced January 2024.

Comments: Submitted to A&A. Comments are welcome!

Light-Curve Structure and Halpha Line Formation in the Tidal Disruption Event AT 2019azh

Authors: Sara Faris, Iair Arcavi, Lydia Makrygianni, Daichi Hiramatsu, Giacomo Terreran, Joseph Farah, D. Andrew Howell, Curtis McCully, Megan Newsome, Estefania Padilla Gonzalez, Craig Pellegrino, K. Azalee Bostroem, Wiam Abojanb, Marco C. Lam, Lina Tomasella, Thomas G. Brink, Alexei V. Filippenko, K. Decker French, Peter Clark, Or Graur, Giorgos Leloudas, Mariusz Gromadzki, Joseph P. Anderson, Matt Nicholl, Claudia P. Gutierrez , et al. (11 additional authors not shown)

Abstract: AT 2019azh is a H+He tidal disruption event (TDE) with one of the most extensive ultraviolet and optical datasets available to date. We present our photometric and spectroscopic observations of this event starting several weeks before and out to approximately two years after g-band peak brightness and combine them with public photometric data. This extensive dataset robustly reveals a change in th… ▽ More AT 2019azh is a H+He tidal disruption event (TDE) with one of the most extensive ultraviolet and optical datasets available to date. We present our photometric and spectroscopic observations of this event starting several weeks before and out to approximately two years after g-band peak brightness and combine them with public photometric data. This extensive dataset robustly reveals a change in the light-curve slope and a bump in the rising light curve of a TDE for the first time, which may indicate more than one dominant emission mechanism contributing to the pre-peak light curve. We further confirm the relation seen in previous TDEs whereby the redder emission peaks later than the bluer emission. The post-peak bolometric light curve of AT 2019azh is better described by an exponential decline than by the canonical t^{-5/3} (and in fact any) power-law decline. We find a possible mid-infrared excess around peak optical luminosity, but cannot determine its origin. In addition, we provide the earliest measurements of the Halpha emission-line evolution and find no significant time delay between the peak of the V-band light curve and that of the Halpha luminosity. These results can be used to constrain future models of TDE line formation and emission mechanisms in general. More pre-peak 1-2 day cadence observations of TDEs are required to determine whether the characteristics observed here are common among TDEs. More importantly, detailed emission models are needed to fully exploit such observations for understanding the emission physics of TDEs. △ Less

Submitted 6 December, 2023; originally announced December 2023.

Comments: Submitted to ApJ

Monthly quasi-periodic eruptions from repeated stellar disruption by a massive black hole

Authors: P. A. Evans, C. J. Nixon, S. Campana, P. Charalampopoulos, D. A. Perley, A. A. Breeveld, K. L. Page, S. R. Oates, R. A. J. Eyles-Ferris, D. B. Malesani, L. Izzo, M. R. Goad, P. T. O'Brien, J. P. Osborne, B. Sbarufatti

Abstract: In recent years, searches of archival X-ray data have revealed galaxies exhibiting nuclear quasi-periodic eruptions with periods of several hours. These are reminiscent of the tidal disruption of a star by a supermassive black hole, and the repeated, partial stripping of a white dwarf in an eccentric orbit around a ~10^5 solar mass black hole provides an attractive model. A separate class of perio… ▽ More In recent years, searches of archival X-ray data have revealed galaxies exhibiting nuclear quasi-periodic eruptions with periods of several hours. These are reminiscent of the tidal disruption of a star by a supermassive black hole, and the repeated, partial stripping of a white dwarf in an eccentric orbit around a ~10^5 solar mass black hole provides an attractive model. A separate class of periodic nuclear transients, with significantly longer timescales, have recently been discovered optically, and may arise from the partial stripping of a main-sequence star by a ~10^7 solar mass black hole. No clear connection between these classes has been made. We present the discovery of an X-ray nuclear transient which shows quasi-periodic outbursts with a period of weeks. We discuss possible origins for the emission, and propose that this system bridges the two existing classes outlined above. This discovery was made possible by the rapid identification, dissemination and follow up of an X-ray transient found by the new live \swift-XRT transient detector, demonstrating the importance of low-latency, sensitive searches for X-ray transients. △ Less

Submitted 5 September, 2023; originally announced September 2023.

Comments: To be published in Nature Astronomy at 1600 BST on September 7th. This version for arXiv includes the main article, Methods and Supplementary Information combined into a single file

Delayed Appearance and Evolution of Coronal Lines in the TDE AT2019qiz

Authors: P. Short, A. Lawrence, M. Nicholl, M. Ward, T. M. Reynolds, S. Mattila, C. Yin, I. Arcavi, A. Carnall, P. Charalampopoulos, M. Gromadzki, P. G. Jonker, S. Kim, G. Leloudas, I. Mandel, F. Onori, M. Pursiainen, S. Schulze, C. Villforth, T. Wevers

Abstract: Tidal disruption events (TDEs) occur when a star gets torn apart by a supermassive black hole as it crosses its tidal radius. We present late-time optical and X-ray observations of the nuclear transient AT2019qiz, which showed the typical signs of an optical-UV transient class commonly believed to be TDEs. Optical spectra were obtained 428, 481 and 828 rest-frame days after optical lightcurve peak… ▽ More Tidal disruption events (TDEs) occur when a star gets torn apart by a supermassive black hole as it crosses its tidal radius. We present late-time optical and X-ray observations of the nuclear transient AT2019qiz, which showed the typical signs of an optical-UV transient class commonly believed to be TDEs. Optical spectra were obtained 428, 481 and 828 rest-frame days after optical lightcurve peak, and a UV/X-ray observation coincided with the later spectrum. The optical spectra show strong coronal emission lines, including [Fe VII], [Fe X], [Fe XI] and [Fe XIV]. The Fe lines rise and then fall, except [Fe XIV] which appears late and rises. We observe increasing flux of narrow H-alpha and H-beta and a decrease in broad H-alpha flux. The coronal lines have FWHMs ranging from ~150 - 300km/s, suggesting they originate from a region between the broad and narrow line emitting gas. Between the optical flare and late-time observation, the X-ray spectrum softens dramatically. The 0.3-1 keV X-ray flux increases by a factor of ~50 while the hard X-ray flux decreases by a factor of ~6. WISE fluxes also rose over the same period, indicating the presence of an infrared echo. With AT2017gge, AT2019qiz is one of two examples of a spectroscopically-confirmed optical-UV TDE showing delayed coronal line emission, supporting speculations that Extreme Coronal Line Emitters in quiescent galaxies can be echos of unobserved past TDEs. We argue that the coronal lines, narrow lines, and infrared emission arise from the illumination of pre-existing material likely related to either a previous TDE or AGN activity. △ Less

Submitted 25 July, 2023; originally announced July 2023.

AT2022aedm and a new class of luminous, fast-cooling transients in elliptical galaxies

Authors: M. Nicholl, S. Srivastav, M. D. Fulton, S. Gomez, M. E. Huber, S. R. Oates, P. Ramsden, L. Rhodes, S. J. Smartt, K. W. Smith, A. Aamer, J. P. Anderson, F. E. Bauer, E. Berger, T. de Boer, K. C. Chambers, P. Charalampopoulos, T. -W. Chen, R. P. Fender, M. Fraser, H. Gao, D. A. Green, L. Galbany, B. P. Gompertz, M. Gromadzki , et al. (27 additional authors not shown)

Abstract: We present the discovery and extensive follow-up of a remarkable fast-evolving optical transient, AT2022aedm, detected by the Asteroid Terrestrial impact Last Alert Survey (ATLAS). AT2022aedm exhibited a rise time of $9\pm1$ days in the ATLAS $o$-band, reaching a luminous peak with $M_g\approx-22$ mag. It faded by 2 magnitudes in $g$-band during the next 15 days. These timescales are consistent wi… ▽ More We present the discovery and extensive follow-up of a remarkable fast-evolving optical transient, AT2022aedm, detected by the Asteroid Terrestrial impact Last Alert Survey (ATLAS). AT2022aedm exhibited a rise time of $9\pm1$ days in the ATLAS $o$-band, reaching a luminous peak with $M_g\approx-22$ mag. It faded by 2 magnitudes in $g$-band during the next 15 days. These timescales are consistent with other rapidly evolving transients, though the luminosity is extreme. Most surprisingly, the host galaxy is a massive elliptical with negligible current star formation. X-ray and radio observations rule out a relativistic AT2018cow-like explosion. A spectrum in the first few days after explosion showed short-lived He II emission resembling young core-collapse supernovae, but obvious broad supernova features never developed; later spectra showed only a fast-cooling continuum and narrow, blue-shifted absorption lines, possibly arising in a wind with $v\approx2700$ km s$^{-1}$. We identify two further transients in the literature (Dougie in particular, as well as AT2020bot) that share similarities in their luminosities, timescales, colour evolution and largely featureless spectra, and propose that these may constitute a new class of transients: luminous fast-coolers (LFCs). All three events occurred in passive galaxies at offsets of $\sim4-10$ kpc from the nucleus, posing a challenge for progenitor models involving massive stars or massive black holes. The light curves and spectra appear to be consistent with shock breakout emission, though usually this mechanism is associated with core-collapse supernovae. The encounter of a star with a stellar mass black hole may provide a promising alternative explanation. △ Less

Submitted 21 August, 2023; v1 submitted 5 July, 2023; originally announced July 2023.

Comments: Accepted in ApJL

SN 2023emq: a flash-ionised Ibn supernova with possible CIII emissio

Authors: M. Pursiainen, G. Leloudas, S. Schulze, P. Charalampopoulos, C. R. Angus, J. P. Anderson, F. Bauer, T. -W. Chen, L. Galbany, M. Gromadzki, C. P. Gutiérrez, C. Inserra, J. Lyman, T. E. Müller-Bravo, M. Nicholl, S. J. Smartt, L. Tartaglia, P. Wiseman, D. R. Young

Abstract: SN 2023emq is a fast-evolving transient initially classified as a rare Type Icn supernova (SN), interacting with a H- and He-free circumstellar medium (CSM) around maximum light. Subsequent spectroscopy revealed the unambiguous emergence of narrow He lines, confidently placing SN 2023emq in the more common Type Ibn class. Photometrically SN 2023emq has several uncommon properties regardless of its… ▽ More SN 2023emq is a fast-evolving transient initially classified as a rare Type Icn supernova (SN), interacting with a H- and He-free circumstellar medium (CSM) around maximum light. Subsequent spectroscopy revealed the unambiguous emergence of narrow He lines, confidently placing SN 2023emq in the more common Type Ibn class. Photometrically SN 2023emq has several uncommon properties regardless of its class, including its extreme initial decay (faster than > 90% of Ibn/Icn SNe) and sharp transition in the decline rate from 0.20 mag/d to 0.07 mag/d at +20 d. The bolometric light curve can be modelled as CSM interaction with 0.32M_Sun of ejecta and 0.12M_Sun of CSM, with 0.006M_Sun of nickel, as expected of fast interacting SNe. Furthermore, broad-band polarimetry at +8.7 days (P = 0.55 +/- 0.30%) is consistent with spherical symmetry. A discovery of a transitional Icn/Ibn SN would be unprecedented and would give valuable insights into the nature of mass loss suffered by the progenitor just before death, but we favour an interpretation that SN 2023emq is a type Ibn SN that exhibited flash-ionised features in the earliest spectrum, as the features are not an exact match with other SNe Icn to date. However, the feature at 5700Å, in the region of C III and N II emission, is significantly stronger in SN 2023emq than in the few other flash-ionised Type Ibn SNe, and if it is related to C III, it possibly implies a continuum of properties between the two classes. △ Less

Submitted 27 November, 2023; v1 submitted 16 June, 2023; originally announced June 2023.

Comments: Accepted to ApJL on 22/11/2023

Broad-emission-line dominated hydrogen-rich luminous supernovae

Authors: P. J. Pessi, J. P. Anderson, G. Folatelli, L. Dessart, S. González-Gaitán, A. Möller, C. P. Gutiérrez, S. Mattila, T. M. Reynolds, P. Charalampopoulos, A. V. Filippenko, L. Galbany, A. Gal-Yam, M. Gromadzki, D. Hiramatsu, D. A. Howell, C. Inserra, E. Kankare, R. Lunnan, L. Martinez, C. McCully, N. Meza, T. E. Müller-Bravo, M. Nicholl, C. Pellegrino , et al. (5 additional authors not shown)

Abstract: Hydrogen-rich Type II supernovae (SNe II) are the most frequently observed class of core-collapse SNe (CCSNe). However, most studies that analyse large samples of SNe II lack events with absolute peak magnitudes brighter than -18.5 mag at rest-frame optical wavelengths. Thanks to modern surveys, the detected number of such luminous SNe II (LSNe II) is growing. There exist several mechanisms that c… ▽ More Hydrogen-rich Type II supernovae (SNe II) are the most frequently observed class of core-collapse SNe (CCSNe). However, most studies that analyse large samples of SNe II lack events with absolute peak magnitudes brighter than -18.5 mag at rest-frame optical wavelengths. Thanks to modern surveys, the detected number of such luminous SNe II (LSNe II) is growing. There exist several mechanisms that could produce luminous SNe II. The most popular propose either the presence of a central engine (a magnetar gradually spinning down or a black hole accreting fallback material) or the interaction of supernova ejecta with circumstellar material (CSM) that turns kinetic energy into radiation energy. In this work, we study the light curves and spectral series of a small sample of six LSNe II that show peculiarities in their H$α$ profile, to attempt to understand the underlying powering mechanism. We favour an interaction scenario with CSM that is not dense enough to be optically thick to electron scattering on large scales -- thus, no narrow emission lines are observed. This conclusion is based on the observed light curve (higher luminosity, fast decline, blue colours) and spectral features (lack of persistent narrow lines, broad H$α$ emission, lack of H$α$ absorption, weak or nonexistent metal lines) together with comparison to other luminous events available in the literature. We add to the growing evidence that transients powered by ejecta-CSM interaction do not necessarily display persistent narrow emission lines. △ Less

Submitted 15 June, 2023; originally announced June 2023.

Comments: 27 pages, 16 figures, accepted for publication in MNRAS

The broad-lined Type-Ic supernova SN 2022xxf with extraordinary two-humped light curves

Authors: H. Kuncarayakti, J. Sollerman, L. Izzo, K. Maeda, S. Yang, S. Schulze, C. R. Angus, M. Aubert, K. Auchettl, M. Della Valle, L. Dessart, K. Hinds, E. Kankare, M. Kawabata, P. Lundqvist, T. Nakaoka, D. Perley, S. I. Raimundo, N. L. Strotjohann, K. Taguchi, Y. -Z. Cai, P. Charalampopoulos, Q. Fang, M. Fraser, C. P. Gutierrez , et al. (38 additional authors not shown)

Abstract: We report on our study of supernova (SN) 2022xxf based on observations obtained during the first four months of its evolution. The light curves (LCs) display two humps of similar maximum brightness separated by 75 days, unprecedented for a broad-lined (BL) Type Ic supernova (SN IcBL). SN 2022xxf is the most nearby SN IcBL to date (in NGC 3705, $z = 0.0037$, at a distance of about 20 Mpc). Optical… ▽ More We report on our study of supernova (SN) 2022xxf based on observations obtained during the first four months of its evolution. The light curves (LCs) display two humps of similar maximum brightness separated by 75 days, unprecedented for a broad-lined (BL) Type Ic supernova (SN IcBL). SN 2022xxf is the most nearby SN IcBL to date (in NGC 3705, $z = 0.0037$, at a distance of about 20 Mpc). Optical and near-infrared photometry and spectroscopy are used to identify the energy source powering the LC. Nearly 50 epochs of high signal-to-noise-ratio spectroscopy were obtained within 130 days, comprising an unparalleled dataset for a SN IcBL, and one of the best-sampled SN datasets to date. The global spectral appearance and evolution of SN 2022xxf points to typical SN Ic/IcBL, with broad features (up to $\sim14000$ km s$^{-1}$) and a gradual transition from the photospheric to the nebular phase. However, narrow emission lines (corresponding to $\sim1000-2500$ km s$^{-1}$) are present in the spectra from the time of the second rise, suggesting slower-moving circumstellar material (CSM). These lines are subtle, in comparison to the typical strong narrow lines of CSM-interacting SNe, for example, Type IIn, Ibn, and Icn, but some are readily noticeable at late times such as in Mg I $λ$5170 and [O I] $λ$5577. Unusually, the near-infrared spectra show narrow line peaks in a number of features formed by ions of O and Mg. We infer the presence of CSM that is free of H and He. We propose that the radiative energy from the ejecta-CSM interaction is a plausible explanation for the second LC hump. This interaction scenario is supported by the color evolution, which progresses to the blue as the light curve evolves along the second hump, and the slow second rise and subsequent rapid LC drop. (Abstract abridged) △ Less

Submitted 14 August, 2023; v1 submitted 29 March, 2023; originally announced March 2023.

Comments: Accepted version

Journal ref: A&A 678, A209 (2023)

Multiwavelength observations of the extraordinary accretion event AT2021lwx

Authors: P. Wiseman, Y. Wang, S. Hönig, N. Castro-Segura, P. Clark, C. Frohmaier, M. D. Fulton, G. Leloudas, M. Middleton, T. E. Müller-Bravo, A. Mummery, M. Pursiainen, S. J. Smartt, K. Smith, M. Sullivan, J. P. Anderson, J. A. Acosta Pulido, P. Charalampopoulos, M. Banerji, M. Dennefeld, L. Galbany, M. Gromadzki, C. P. Gutiérrez, N. Ihanec, E. Kankare , et al. (21 additional authors not shown)

Abstract: We present observations from X-ray to mid-infrared wavelengths of the most energetic non-quasar transient ever observed, AT2021lwx. Our data show a single optical brightening by a factor $>100$ to a luminosity of $7\times10^{45}$ erg s$^{-1}$, and a total radiated energy of $1.5\times10^{53}$ erg, both greater than any known optical transient. The decline is smooth and exponential and the ultra-vi… ▽ More We present observations from X-ray to mid-infrared wavelengths of the most energetic non-quasar transient ever observed, AT2021lwx. Our data show a single optical brightening by a factor $>100$ to a luminosity of $7\times10^{45}$ erg s$^{-1}$, and a total radiated energy of $1.5\times10^{53}$ erg, both greater than any known optical transient. The decline is smooth and exponential and the ultra-violet - optical spectral energy distribution resembles a black body with temperature $1.2\times10^4$ K. Tentative X-ray detections indicate a secondary mode of emission, while a delayed mid-infrared flare points to the presence of dust surrounding the transient. The spectra are similar to recently discovered optical flares in known active galactic nuclei but lack some characteristic features. The lack of emission for the previous seven years is inconsistent with the short-term, stochastic variability observed in quasars, while the extreme luminosity and long timescale of the transient disfavour the disruption of a single solar-mass star. The luminosity could be generated by the disruption of a much more massive star, but the likelihood of such an event occurring is small. A plausible scenario is the accretion of a giant molecular cloud by a dormant black hole of $10^8 - 10^9$ solar masses. AT2021lwx thus represents an extreme extension of the known scenarios of black hole accretion. △ Less

Submitted 31 March, 2023; v1 submitted 8 March, 2023; originally announced March 2023.

Comments: 11 pages, 5 figures, Accepted for publication in MNRAS

Optimal Heaviest Induced Ancestors

Authors: Panagiotis Charalampopoulos, Bartłomiej Dudek, Paweł Gawrychowski, Karol Pokorski

Abstract: We revisit the Heaviest Induced Ancestors (HIA) problem that was introduced by Gagie, Gawrychowski, and Nekrich [CCCG 2013] and has a number of applications in string algorithms. Let $T_1$ and $T_2$ be two rooted trees whose nodes have weights that are increasing in all root-to-leaf paths, and labels on the leaves, such that no two leaves of a tree have the same label. A pair of nodes… ▽ More We revisit the Heaviest Induced Ancestors (HIA) problem that was introduced by Gagie, Gawrychowski, and Nekrich [CCCG 2013] and has a number of applications in string algorithms. Let $T_1$ and $T_2$ be two rooted trees whose nodes have weights that are increasing in all root-to-leaf paths, and labels on the leaves, such that no two leaves of a tree have the same label. A pair of nodes $(u, v)\in T_1 \times T_2$ is \emph{induced} if and only if there is a label shared by leaf-descendants of $u$ and $v$. In an HIA query, given nodes $x \in T_1$ and $y \in T_2$, the goal is to find an induced pair of nodes $(u, v)$ of the maximum total weight such that $u$ is an ancestor of~$x$ and $v$ is an ancestor of $y$. Let $n$ be the upper bound on the sizes of the two trees. It is known that no data structure of size $\tilde{\mathcal{O}}(n)$ can answer HIA queries in $o(\log n / \log \log n)$ time [Charalampopoulos, Gawrychowski, Pokorski; ICALP 2020]. This (unconditional) lower bound is a $\operatorname{polyloglog} n$ factor away from the query time of the fastest $\tilde{\mathcal{O}}(n)$-size data structure known to date for the HIA problem [Abedin, Hooshmand, Ganguly, Thankachan; Algorithmica 2022]. In this work, we resolve the query-time complexity of the HIA problem for the near-linear space regime by presenting a data structure that can be built in $\tilde{\mathcal{O}}(n)$ time and answers HIA queries in $\mathcal{O}(\log n/\log\log n)$ time. As a direct corollary, we obtain an $\tilde{\mathcal{O}}(n)$-size data structure that maintains the LCS of a static string and a dynamic string, both of length at most $n$, in time optimal for this space regime. The main ingredients of our approach are fractional cascading and the utilization of an $\mathcal{O}(\log n/ \log\log n)$-depth tree decomposition. △ Less

Submitted 2 February, 2023; originally announced February 2023.

Modeling continuum polarization levels of tidal disruption events based on the collision-induced outflow mode

Authors: Panos Charalampopoulos, Mattia Bulla, Clement Bonnerot, Giorgos Leloudas

Abstract: TDEs have been observed in the optical and UV for more than a decade but the underlying emission mechanism still remains a puzzle. It has been suggested that viewing angle effects could potentially explain their large photometric and spectroscopic diversity. Polarization is indeed sensitive to the viewing angle and the first polarimetry studies of TDEs are now available, calling for a theoretical… ▽ More TDEs have been observed in the optical and UV for more than a decade but the underlying emission mechanism still remains a puzzle. It has been suggested that viewing angle effects could potentially explain their large photometric and spectroscopic diversity. Polarization is indeed sensitive to the viewing angle and the first polarimetry studies of TDEs are now available, calling for a theoretical interpretation. In this study, we model the continuum polarization levels of TDEs using the radiative transfer code POSSIS and the collision-induced outflow (CIO) TDE emission scenario where unbound shocked gas originating from a debris stream intersection point offset from the black hole, reprocesses the hard emission from the accretion flow into UV and optical bands. We explore two different cases of peak mass fallback rates M'p (~3 and ~0.3 Msol/yr) while varying the following geometrical parameters: the distance R_int from the black hole (BH) to the intersection point, the radius of the photosphere around the BH R_ph, on the surface of which the photons are generated, and the opening angle Deltheta (anisotropic emission). For the high mass fallback rate case, we find for every viewing angle polarization levels below one (P<1%) and P<0.5% for 10/12 simulations. The absolute value of polarization reaches its maximum (P_max) for equatorial viewing angles. For the low mass fallback rate case, the maximum value predicted is P~8.8% and P_max is reached for intermediate viewing angles. We find that the polarization depends strongly on i) the optical depths at the central regions set by the different M'p values and ii) the viewing angle. Finally, by comparing our model predictions to polarization observations of a few TDEs, we attempt to constrain their observed viewing angles and we show that multi-epoch polarimetric observations can become a key factor in constraining the viewing angle of TDEs. △ Less

Submitted 9 December, 2022; originally announced December 2022.

Comments: Accepted for publication in Astronomy and Astrophysics journal; 20 pages

Journal ref: A&A 670, A150 (2023)

The rise and fall of the iron-strong nuclear transient PS16dtm

Authors: T. Petrushevska, G. Leloudas, D. Ilic, M. Bronikowski, P. Charalampopoulos, G. K. Jaisawal, E. Paraskeva, M. Pursiainen, N. Rakic, S. Schulze, K. Taggart, C. K. Wedderkopp, J. P. Anderson, T. de Boer, K. Chambers, T. W. Chen, G. Damljanovic, M. Fraser, H. Gao, A. Gomboc, M. Gromadzki, N. Ihanec, K. Maguire, B. Marcun, T. E. Muller-Bravo , et al. (8 additional authors not shown)

Abstract: Thanks to the advent of large-scale optical surveys, a diverse set of flares from the nuclear regions of galaxies has recently been discovered. These include the disruption of stars by supermassive black holes at the centers of galaxies - nuclear transients known as tidal disruption events (TDEs). Active galactic nuclei (AGN) can show extreme changes in the brightness and emission line intensities… ▽ More Thanks to the advent of large-scale optical surveys, a diverse set of flares from the nuclear regions of galaxies has recently been discovered. These include the disruption of stars by supermassive black holes at the centers of galaxies - nuclear transients known as tidal disruption events (TDEs). Active galactic nuclei (AGN) can show extreme changes in the brightness and emission line intensities, often referred to as changing-look AGN (CLAGN). Given the physical and observational similarities, the interpretation and distinction of nuclear transients as CLAGN or TDEs remains difficult. One of the obstacles of making progress in the field is the lack of well-sampled data of long-lived nuclear outbursts in AGN. Here, we study PS16dtm, a nuclear transient in a Narrow Line Seyfert 1 (NLSy1) galaxy, which has been proposed to be a TDE candidate. Our aim is to study the spectroscopic and photometric properties of PS16dtm, in order to better understand the outbursts originating in NLSy1 galaxies. Our extensive multiwavelength follow-up that spans around 2000 days includes photometry and spectroscopy in the UV/optical, as well as mid-infrared (MIR) and X-ray observations. Furthermore, we improved an existing semiempirical model in order to reproduce the spectra and study the evolution of the spectral lines. The UV/optical light curve shows a double peak at $\sim50$ and $\sim100$ days after the first detection, and it declines and flattens afterward, reaching preoutburst levels after 2000 days of monitoring. The MIR light curve rises almost simultaneously with the optical, but unlike the UV/optical which is approaching the preoutburst levels in the last epochs of our observations, the MIR emission is still rising at the time of writing. The optical spectra show broad Balmer features and the strongest broad Fe II emission ever detected in a nuclear transient. [abridged] △ Less

Submitted 25 November, 2022; originally announced November 2022.

Comments: Accepted for publication in A&A, 19 pages and 18 figures

The Birth of a Relativistic Jet Following the Disruption of a Star by a Cosmological Black Hole

Authors: Dheeraj R. Pasham, Matteo Lucchini, Tanmoy Laskar, Benjamin P. Gompertz, Shubham Srivastav, Matt Nicholl, Stephen J. Smartt, James C. A. Miller-Jones, Kate D. Alexander, Rob Fender, Graham P. Smith, Michael D. Fulton, Gulab Dewangan, Keith Gendreau, Eric R. Coughlin, Lauren Rhodes, Assaf Horesh, Sjoert van Velzen, Itai Sfaradi, Muryel Guolo, N. Castro Segura, Aysha Aamer, Joseph P. Anderson, Iair Arcavi, Sean J. Brennan , et al. (41 additional authors not shown)

Abstract: A black hole can launch a powerful relativistic jet after it tidally disrupts a star. If this jet fortuitously aligns with our line of sight, the overall brightness is Doppler boosted by several orders of magnitude. Consequently, such on-axis relativistic tidal disruption events (TDEs) have the potential to unveil cosmological (redshift $z>$1) quiescent black holes and are ideal test beds to under… ▽ More A black hole can launch a powerful relativistic jet after it tidally disrupts a star. If this jet fortuitously aligns with our line of sight, the overall brightness is Doppler boosted by several orders of magnitude. Consequently, such on-axis relativistic tidal disruption events (TDEs) have the potential to unveil cosmological (redshift $z>$1) quiescent black holes and are ideal test beds to understand the radiative mechanisms operating in super-Eddington jets. Here, we present multi-wavelength (X-ray, UV, optical, and radio) observations of the optically discovered transient \target at $z=1.193$. Its unusual X-ray properties, including a peak observed luminosity of $\gtrsim$10$^{48}$ erg s$^{-1}$, systematic variability on timescales as short as 1000 seconds, and overall duration lasting more than 30 days in the rest-frame are traits associated with relativistic TDEs. The X-ray to radio spectral energy distributions spanning 5-50 days after discovery can be explained as synchrotron emission from a relativistic jet (radio), synchrotron self-Compton (X-rays), and thermal emission similar to that seen in low-redshift TDEs (UV/optical). Our modeling implies a beamed, highly relativistic jet akin to blazars but requires extreme matter-domination, i.e, high ratio of electron-to-magnetic field energy densities in the jet, and challenges our theoretical understanding of jets. △ Less

Submitted 29 November, 2022; originally announced November 2022.

Comments: To appear in Nature Astronomy on 30th November 2022. Also see here for an animation explaining the result: https://youtu.be/MQHdSbxuznY

A very luminous jet from the disruption of a star by a massive black hole

Authors: Igor Andreoni, Michael W. Coughlin, Daniel A. Perley, Yuhan Yao, Wenbin Lu, S. Bradley Cenko, Harsh Kumar, Shreya Anand, Anna Y. Q. Ho, Mansi M. Kasliwal, Antonio de Ugarte Postigo, Ana Sagues-Carracedo, Steve Schulze, D. Alexander Kann, S. R. Kulkarni, Jesper Sollerman, Nial Tanvir, Armin Rest, Luca Izzo, Jean J. Somalwar, David L. Kaplan, Tomas Ahumada, G. C. Anupama, Katie Auchettl, Sudhanshu Barway , et al. (56 additional authors not shown)

Abstract: Tidal disruption events (TDEs) are bursts of electromagnetic energy released when supermassive black holes (SMBHs) at the centers of galaxies violently disrupt a star that passes too close. TDEs provide a new window to study accretion onto SMBHs; in some rare cases, this accretion leads to launching of a relativistic jet, but the necessary conditions are not fully understood. The best studied jett… ▽ More Tidal disruption events (TDEs) are bursts of electromagnetic energy released when supermassive black holes (SMBHs) at the centers of galaxies violently disrupt a star that passes too close. TDEs provide a new window to study accretion onto SMBHs; in some rare cases, this accretion leads to launching of a relativistic jet, but the necessary conditions are not fully understood. The best studied jetted TDE to date is Swift J1644+57, which was discovered in gamma-rays, but was too obscured by dust to be seen at optical wavelengths. Here we report the optical discovery of AT2022cmc, a rapidly fading source at cosmological distance (redshift z=1.19325) whose unique lightcurve transitioned into a luminous plateau within days. Observations of a bright counterpart at other wavelengths, including X-rays, sub-millimeter, and radio, supports the interpretation of AT2022cmc as a jetted TDE containing a synchrotron "afterglow", likely launched by a SMBH with spin $a \gtrsim 0.3$. Using 4 years of Zwicky Transient Facility (ZTF) survey data, we calculate a rate of $0.02 ^{+ 0.04 }_{- 0.01 }$ Gpc$^{-3}$ yr$^{-1}$ for on-axis jetted TDEs based on the luminous, fast-fading red component, thus providing a measurement complementary to the rates derived from X-ray and radio observations. Correcting for the beaming angle effects, this rate confirms that about 1% of TDEs have relativistic jets. Optical surveys can use AT2022cmc as a prototype to unveil a population of jetted TDEs. △ Less

Submitted 29 November, 2022; originally announced November 2022.

Comments: Accepted for publication in Nature

AT 2020wey and the class of faint and fast Tidal Disruption Events

Authors: Panos Charalampopoulos, Miika Pursiainen, Giorgos Leloudas, Iair Arcavi, Megan Newsome, Steve Schulze, Jamison Burke, Matt Nicholl

Abstract: We present an analysis of the optical and UV properties of AT 2020wey, a faint and fast tidal disruption event (TDE) at 124.3 Mpc. The light curve of the object peaked at an absolute magnitude of $M_{g} = -17.45$ mag and a maximum bolometric luminosity of $L_{\rm peak}=(8.74\pm0.69)\times10^{42}$ erg s$^{-1}$, making it comparably faint with iPTF16fnl, the faintest TDE to date. The time from the l… ▽ More We present an analysis of the optical and UV properties of AT 2020wey, a faint and fast tidal disruption event (TDE) at 124.3 Mpc. The light curve of the object peaked at an absolute magnitude of $M_{g} = -17.45$ mag and a maximum bolometric luminosity of $L_{\rm peak}=(8.74\pm0.69)\times10^{42}$ erg s$^{-1}$, making it comparably faint with iPTF16fnl, the faintest TDE to date. The time from the last non-detection to the $g$-band peak is 22.94 $\pm$ 2.03 days and the rise is well described by $L\propto t^{1.8}$. The decline of the bolometric light curve is described by a sharp exponential decay steeper than the canonical $t^{-5/3}$ power law, making AT 2020wey the fastest declining TDE to date. Multi-wavelength fits to the light curve indicate a complete disruption of a star of $M_*=0.11M_{\odot}$ by a black hole of $M_{\rm BH}=10^{6.46}M_{\odot}$. Our spectroscopic dataset reveals broad ($\sim10^{4}$ km s$^{-1}$) Balmer and He II $λ$4686 lines, with H$α$ reaching its peak with a lag of $\sim8.2$ days compared to the continuum. In contrast to previous faint and fast TDEs, there are no obvious Bowen fluorescence lines in the spectra of AT 2020wey. There is a strong correlation between the MOSFIT-derived black hole masses of TDEs and their decline rate. However, AT 2020wey is an outlier in this correlation, which could indicate that its fast early decline may be dictated by a different physical mechanism than fallback. After performing a volumetric correction to a sample of 30 TDEs observed between 2018 and 2020, we conclude that faint TDEs are not rare by nature and that they should constitute up to $\sim$ 50 - 60 % of the entire population and their numbers could alleviate some of the tension between the observed and theoretical TDE rate estimates. We calculate the optical TDE luminosity function and we find a steep power-law relation $dN/dL_{g} \propto {L_{g}}^{-2.36}$. △ Less

Submitted 30 March, 2023; v1 submitted 26 September, 2022; originally announced September 2022.

Comments: Accepted for publication to A&A (21/02/2023)

Journal ref: A&A 673, A95 (2023)

Approximate Circular Pattern Matching

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba

Abstract: We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a threshold $k>0$, and we are to report all starting positions of fragments of $T$ (called occurrences) that are at distance at most $k$ from some cyclic rotation of $P$. In the decision version of the problem, we are to c… ▽ More We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a threshold $k>0$, and we are to report all starting positions of fragments of $T$ (called occurrences) that are at distance at most $k$ from some cyclic rotation of $P$. In the decision version of the problem, we are to check if any such occurrence exists. All previous results for approximate CPM were either average-case upper bounds or heuristics, except for the work of Charalampopoulos et al. [CKP$^+$, JCSS'21], who considered only the Hamming distance. For the reporting version of the approximate CPM problem, under the Hamming distance we improve upon the main algorithm of [CKP$^+$, JCSS'21] from ${\cal O}(n+(n/m)\cdot k^4)$ to ${\cal O}(n+(n/m)\cdot k^3\log\log k)$ time; for the edit distance, we give an ${\cal O}(nk^2)$-time algorithm. We also consider the decision version of the approximate CPM problem. Under the Hamming distance, we obtain an ${\cal O}(n+(n/m)\cdot k^2\log k/\log\log k)$-time algorithm, which nearly matches the algorithm by Chan et al. [CGKKP, STOC'20] for the standard counterpart of the problem. Under the edit distance, the ${\cal O}(nk\log^3 k)$ runtime of our algorithm nearly matches the ${\cal O}(nk)$ runtime of the Landau-Vishkin algorithm [LV, J. Algorithms'89]. As a stepping stone, we propose ${\cal O}(nk\log^3 k)$-time algorithm for the Longest Prefix $k'$-Approximate Match problem, proposed by Landau et al. [LMS, SICOMP'98], for all $k'\in \{1,\dots,k\}$. We give a conditional lower bound that suggests a polynomial separation between approximate CPM under the Hamming distance over the binary alphabet and its non-circular counterpart. We also show that a strongly subquadratic-time algorithm for the decision version of approximate CPM under edit distance would refute SETH. △ Less

Submitted 18 August, 2022; originally announced August 2022.

Comments: Accepted to ESA 2022. Abstract abridged to meet arXiv requirements

An asymmetric electron-scattering photosphere around optical tidal disruption events

Authors: Giorgos Leloudas, Mattia Bulla, Aleksandar Cikota, Lixin Dai, Lars L. Thomsen, Justyn R. Maund, Panos Charalampopoulos, Nathaniel Roth, Iair Arcavi, Katie Auchettl, Daniele B. Malesani, Matt Nicholl, Enrico Ramirez-Ruiz

Abstract: A star crossing the tidal radius of a supermassive black hole will be spectacularly ripped apart with an accompanying burst of radiation. A few tens of such tidal disruption events (TDEs) have now been identified in the optical wavelengths, but the exact origin of the strong optical emission remains inconclusive. Here we report polarimetric observations of three TDEs. The continuum polarization is… ▽ More A star crossing the tidal radius of a supermassive black hole will be spectacularly ripped apart with an accompanying burst of radiation. A few tens of such tidal disruption events (TDEs) have now been identified in the optical wavelengths, but the exact origin of the strong optical emission remains inconclusive. Here we report polarimetric observations of three TDEs. The continuum polarization is independent of wavelength, while emission lines are partially depolarized. These signatures are consistent with optical photons being scattered and polarized in an envelope of free electrons. An almost axisymmetric photosphere viewed from different angles is in broad agreement with the data, but there is also evidence for deviations from axial symmetry before the peak of the flare and significant time evolution at early times, compatible with the rapid formation of an accretion disk. By combining a super-Eddington accretion model with a radiative transfer code we generate predictions for the degree of polarization as a function of disk mass and viewing angle, and we show that the predicted levels are compatible with the observations, for extended reprocessing envelopes of $\sim$1000 gravitational radii. Spectropolarimetry therefore constitutes a new observational test for TDE models, and opens an important new line of exploration in the study of TDEs. △ Less

Submitted 14 July, 2022; originally announced July 2022.

Comments: Author's version of paper to appear in Nature Astronomy. In the journal version the detailed discussion on the ISP determination will be moved from the Methods section to a Supplementary Information section. 58 pages in double spacing format, including 5 Figures, 10 Extended Data Figures and 2 Tables

The nuclear transient AT 2017gge: a tidal disruption event in a dusty and gas-rich environment and the awakening of a dormant SMBH

Authors: F. Onori, G. Cannizzaro, P. G. Jonker, M. Kim, M. Nicholl, S. Mattila, T. M. Reynolds, M. Fraser, T. Wevers, E. Brocato, J. P. Anderson, R. Carini, P. Charalampopoulos, P. Clark, M. Gromadzki, C. P. Gutiérrez, N. Ihanec, C. Inserra, A. Lawrence, G. Leloudas, P. Lundqvist, T. E. Müller-Bravo, S. Piranomonte, M. Pursiainen, K. A. Rybicki , et al. (6 additional authors not shown)

Abstract: We present the results from a dense multi-wavelength (optical/UV, near-infrared (IR), and X-ray) follow-up campaign of the nuclear transient AT2017gge, covering a total of 1698 days from the transient's discovery. The bolometric lightcurve, the black body temperature and radius, the broad H and He I $λ$5876 emission lines and their evolution with time, are all consistent with a tidal disruption ev… ▽ More We present the results from a dense multi-wavelength (optical/UV, near-infrared (IR), and X-ray) follow-up campaign of the nuclear transient AT2017gge, covering a total of 1698 days from the transient's discovery. The bolometric lightcurve, the black body temperature and radius, the broad H and He I $λ$5876 emission lines and their evolution with time, are all consistent with a tidal disruption event (TDE) nature. A soft X-ray flare is detected with a delay of $\sim$200 days with respect to the optical/UV peak and it is rapidly followed by the emergence of a broad He II $λ$4686 and by a number of long-lasting high ionization coronal emission lines. This indicate a clear connection between a TDE flare and the appearance of extreme coronal line emission (ECLEs). An IR echo, resulting from dust re-radiation of the optical/UV TDE light is observed after the X-ray flare and the associated near-IR spectra show a transient broad feature in correspondence of the He I $λ$10830 and, for the first time in a TDE, a transient high-ionization coronal NIR line (the [Fe XIII] $λ$10798) is also detected. The data are well explained by a scenario in which a TDE occurs in a gas and dust rich environment and its optical/UV, soft X-ray, and IR emission have different origins and locations. The optical emission may be produced by stellar debris stream collisions prior to the accretion disk formation, which is instead responsible for the soft X-ray flare, emitted after the end of the circularization process. △ Less

Submitted 9 September, 2022; v1 submitted 31 May, 2022; originally announced June 2022.

Comments: Accepted for publication in MNRAS

Faster Pattern Matching under Edit Distance

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz

Abstract: We consider the approximate pattern matching problem under the edit distance. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to find the starting positions of all substrings of $T$ that can be transformed to $P$ with at most $k$ edits. More than 20 years ago, Cole and Hariharan [SODA'98, J. Comput.'02] gave an $\mathcal{O}(n+k^4 \cdot n/ m)$-time algo… ▽ More We consider the approximate pattern matching problem under the edit distance. Given a text $T$ of length $n$, a pattern $P$ of length $m$, and a threshold $k$, the task is to find the starting positions of all substrings of $T$ that can be transformed to $P$ with at most $k$ edits. More than 20 years ago, Cole and Hariharan [SODA'98, J. Comput.'02] gave an $\mathcal{O}(n+k^4 \cdot n/ m)$-time algorithm for this classic problem, and this runtime has not been improved since. Here, we present an algorithm that runs in time $\mathcal{O}(n+k^{3.5} \sqrt{\log m \log k} \cdot n/m)$, thus breaking through this long-standing barrier. In the case where $n^{1/4+\varepsilon} \leq k \leq n^{2/5-\varepsilon}$ for some arbitrarily small positive constant $\varepsilon$, our algorithm improves over the state-of-the-art by polynomial factors: it is polynomially faster than both the algorithm of Cole and Hariharan and the classic $\mathcal{O}(kn)$-time algorithm of Landau and Vishkin [STOC'86, J. Algorithms'89]. We observe that the bottleneck case of the alternative $\mathcal{O}(n+k^4 \cdot n/m)$-time algorithm of Charalampopoulos, Kociumaka, and Wellnitz [FOCS'20] is when the text and the pattern are (almost) periodic. Our new algorithm reduces this case to a new dynamic problem (Dynamic Puzzle Matching), which we solve by building on tools developed by Tiskin [SODA'10, Algorithmica'15] for the so-called seaweed monoid of permutation matrices. Our algorithm relies only on a small set of primitive operations on strings and thus also applies to the fully-compressed setting (where text and pattern are given as straight-line programs) and to the dynamic setting (where we maintain a collection of strings under creation, splitting, and concatenation), improving over the state of the art. △ Less

Submitted 6 April, 2022; originally announced April 2022.

Comments: 94 pages, 7 figures

An elliptical accretion disk following the tidal disruption event AT 2020zso

Authors: T. Wevers, M. Nicholl, M. Guolo, P. Charalampopoulos, M. Gromadzki, T. M. Reynolds, E. Kankare, G. Leloudas, J. P. Anderson, I. Arcavi, G. Cannizzaro, T. W. Chen, N. Ihanec, C. Inserra, C. P. Gutiérrez, P. G. Jonker, A. Lawrence, M. R. Magee, T. E. Müller-Bravo, F. Onori, E. Ridley, S. Schulze, P. Short, D. Hiramatsu, M. Newsome , et al. (3 additional authors not shown)

Abstract: [Abridged] We classify AT 2020zso as a TDE based on the blackbody evolution inferred from UV/optical photometric observations, and spectral line content and evolution. We identify transient, double-peaked Bowen (N III), He I, He II and Halpha emission lines. We model medium resolution optical spectroscopy of the He II (after careful deblending of the N III contribution) and Halpha lines during the… ▽ More [Abridged] We classify AT 2020zso as a TDE based on the blackbody evolution inferred from UV/optical photometric observations, and spectral line content and evolution. We identify transient, double-peaked Bowen (N III), He I, He II and Halpha emission lines. We model medium resolution optical spectroscopy of the He II (after careful deblending of the N III contribution) and Halpha lines during the rise, peak and early decline of the light curve using relativistic, elliptical accretion disk models. We find that the spectral evolution before peak can be explained by optical depth effects consistent with an outflowing, optically thick Eddington envelope. Around peak the envelope reaches its maximum extent (approximately 10^15 or 3000-6000 gravitational radii for an inferred black hole mass of 5-10 10^5) and becomes optically thin. The Halpha and He II emission lines at and after peak can be reproduced with a highly inclined (i=85+-5 degrees), highly elliptical (e=0.97+-0.01) and relatively compact (Rin = several 100 Rg and Rout = several 1000 Rg ) accretion disk. Overall, the line profiles suggest a highly elliptical geometry for the new accretion flow, consistent with theoretical expectations of newly formed TDE disks. We quantitatively confirm, for the first time, the high inclination nature of a Bowen (and X-ray dim) TDE, consistent with the unification picture of TDEs where the inclination largely determines the observational appearance. Rapid line profile variations rule out the binary SMBH hypothesis as the origin of the eccentricity; these results thus provide a direct link between a TDE in an AGN and the eccentric accretion disk. We illustrate for the first time how optical spectroscopy can be used to constrain the black hole spin, through (the lack of) disk precession signatures (changes in inferred inclination) - and rule out high black hole spin values (a < 0.8). △ Less

Submitted 7 June, 2022; v1 submitted 16 February, 2022; originally announced February 2022.

Comments: 20 pages, 15 figures and 5 tables. Accepted for publication in A&A. The spectra will be made publicly available through WISErep

Journal ref: A&A 666, A6 (2022)

SN 2018bsz: a Type I superluminous supernova with aspherical circumstellar material

Authors: M. Pursiainen, G. Leloudas, E. Paraskeva, A. Cikota, J. P. Anderson, C. R. Angus, S. Brennan, M. Bulla, E. Camacho-Iñiguez, P. Charalampopoulos, T. -W. Chen, M. Delgado Mancheño, M. Fraser, C. Frohmaier, L. Galbany, C. P. Gutiérrez, M. Gromadzki, C. Inserra, J. Maund, T. E. Müller-Bravo, S. Muñoz Torres, M. Nicholl, F. Onori, F. Patat, P. J. Pessi , et al. (4 additional authors not shown)

Abstract: We present a spectroscopic analysis of Type I superluminous supernova (SLSN-I), SN 2018bsz. While it closely resembles SLSNe-I, the multi-component H$α$ line appearing at $\sim30$ d post-maximum is the most atypical. The H$α$ is characterised by two emission components, one at $+3000$ km/s and a second at $-7500$ km/s, with a third, near-zero velocity component appearing after a delay. The blue an… ▽ More We present a spectroscopic analysis of Type I superluminous supernova (SLSN-I), SN 2018bsz. While it closely resembles SLSNe-I, the multi-component H$α$ line appearing at $\sim30$ d post-maximum is the most atypical. The H$α$ is characterised by two emission components, one at $+3000$ km/s and a second at $-7500$ km/s, with a third, near-zero velocity component appearing after a delay. The blue and central components can be described by Gaussian profiles of intermediate width, but the red component is significantly broader and Lorentzian. The blue component evolves towards lower velocity before fading at $100$ d post-peak, concurrently with a light curve break. Multi-component profiles are observed in other hydrogen lines including Pa$β$, and in lines of Ca II and He I. Spectropolarimetry obtained before (10.2 d) and after (38.4 d) the appearance of the H lines show a large shift on the Stokes $Q$ -- $U$ plane consistent with SN 2018bsz undergoing radical changes in its geometry. Assuming the SN is almost unpolarised at 10.2 d, the continuum polarisation at 38.4 d reaches $P \sim1.8\%$ implying a highly asymmetric configuration. We propose that the observed evolution of SN 2018bsz can be explained by highly aspherical CSM. After the SN explosion, the CSM is quickly overtaken by the ejecta, but as the photosphere starts to recede, the different CSM regions re-emerge producing the peculiar line profiles. Based on the first appearance of H$α$, we can constrain the distance of the CSM to be less than $430$ AU, or even lower ($<87$ AU) if the pre-peak plateau is related to an eruption that created the CSM. The presence of CSM has been inferred for other SLSNe-I. However, it is not clear whether the rare properties of SN 2018bsz can be generalised for SLSNe-I or whether they are the result of an uncommon evolutionary path, possibly involving a binary companion. △ Less

Submitted 29 June, 2022; v1 submitted 3 February, 2022; originally announced February 2022.

Comments: Accepted to A&A on 22/06/2022

Journal ref: A&A 666, A30 (2022)

SN 2020acat: A purr-fect example of a fast rising Type IIb Supernova

Authors: K. Medler, P. A. Mazzali, J. Teffs, C. Ashall, J. P. Anderson, I. Arcavi, S. Benetti, K. A. Bostroem, J. Burke, Y. -Z. Cai, P. Charalampopoulos, N. Elias-Rosa, M. Ergon, L. Galbany, M. Gromadzki, D. Hiramatsu, D. A. Howell, C. Inserra, P. Lundqvist, C. McCully, T. Müller-Bravo, M. Newsome, M. Nicholl, E. Padilla Gonzalez, E. Paraskeva , et al. (9 additional authors not shown)

Abstract: The Ultra-Violet (UV) and Near Infrared (NIR) photometric and optical spectroscopic observations of SN 2020acat covering $\sim \! \! 250$ days after explosion are presented here. Using the fast rising photometric observations, spanning from the UV to NIR wavelengths, a pseudo-bolometric light curve was constructed and compared to several other well-observed Type IIb supernovae (SNe IIb). SN 2020ac… ▽ More The Ultra-Violet (UV) and Near Infrared (NIR) photometric and optical spectroscopic observations of SN 2020acat covering $\sim \! \! 250$ days after explosion are presented here. Using the fast rising photometric observations, spanning from the UV to NIR wavelengths, a pseudo-bolometric light curve was constructed and compared to several other well-observed Type IIb supernovae (SNe IIb). SN 2020acat displayed a very short rise time reaching a peak luminosity of $\mathrm{Log_{10}}(L) = 42.49 \pm 0.15 \, \mathrm{erg \, s^{-1}}$ in only $\sim \! \! 14.6 \pm 0.3$ days. From modelling of the pseudo-bolometric light curve, we estimated a total mass of $^{56} \mathrm{Ni}$ synthesised by SN 2020acat of $0.13 \pm 0.02 \, \mathrm{M_{\odot}}$, with an ejecta mass of $2.3 \pm 0.3 \, \mathrm{M_{\odot}}$ and a kinetic energy of $1.2 \pm 0.2 \times 10^{51}$ erg. The optical spectra of SN 2020acat display hydrogen signatures well into the transitional period ($\gtrsim 100$ days), between the photospheric and the nebular phases. The spectra also display a strong feature around $4900 \, Å$ that cannot be solely accounted for by the presence of the $\mathrm{Fe_{II}}$ $5018$ line. We suggest that the $\mathrm{Fe_{II}}$ feature was augmented by $\mathrm{He_{I}}$ $5016$ and possibly by the presence of $\mathrm{N_{II}}$ $5005$. From both photometric and spectroscopic analysis, we inferred that the progenitor of SN\,2020acat was an intermediate mass compact star with a $M_\mathrm{ZAMS}$ of $18 - 22 \, \mathrm{M_{\odot}}$. △ Less

Submitted 18 January, 2022; originally announced January 2022.

Comments: 18 pages, 13 figures

A detailed spectroscopic study of Tidal Disruption Events

Authors: P. Charalampopoulos, G. Leloudas, D. B. Malesani, T. Wevers, I. Arcavi, M. Nicholl, M. Pursiainen, A. Lawrence, J. P. Anderson, S. Benetti, G. Cannizzaro, T. -W. Chen, L. Galbany, M. Gromadzki, C. P. Gutiérrez, C. Inserra, P. G. Jonker, T. E. Müller-Bravo, F. Onori, P. Short, J. Sollerman, D. R. Young

Abstract: Spectroscopically, TDEs are characterized by broad ( 10$^{4}$ km/s) emission lines and show large diversity as well as different line profiles. After carefully and consistently performing a series of data reduction tasks including host galaxy light subtraction, we present here the first detailed, spectroscopic population study of 16 optical/UV TDEs. We report a time lag between the peaks of the op… ▽ More Spectroscopically, TDEs are characterized by broad ( 10$^{4}$ km/s) emission lines and show large diversity as well as different line profiles. After carefully and consistently performing a series of data reduction tasks including host galaxy light subtraction, we present here the first detailed, spectroscopic population study of 16 optical/UV TDEs. We report a time lag between the peaks of the optical light-curves and the peak luminosity of H$α$ spanning between 7 - 45 days. If interpreted as light-echoes, these lags correspond to distances of 2 - 12 x 10$^{16}$ cm, one to two orders of magnitudes larger than the estimated blackbody radii (R$_{\rm BB}$) of the same TDEs and we discuss the possible origin of this surprisingly large discrepancy. We also report time lags for the peak luminosity of He I $λ$5876 line; smaller than the ones of H$α$ for H TDEs and similar or larger for N III Bowen TDEs. We report that N III Bowen TDEs have lower H$α$ velocity widths compared to the rest of the TDEs in our sample and we also find that a strong X-ray to optical ratio might imply weakening of the line widths. Furthermore, we study the evolution of line luminosities and ratios with respect to their radii (R$_{\rm BB}$) and temperatures (T$_{\rm BB}$). We find a linear relationship between H$α$ luminosity and the R$_{\rm BB}$ and potentially an inverse power-law relation with T$_{\rm BB}$ leading to weaker H$α$ emission for T$_{\rm BB}$ $\geq$ 25000 K. The He II/He I ratio becomes large at the same temperatures possibly pointing to an ionization effect. The He II/H$α$ ratio becomes larger as the photospheric radius recedes, implying a stratified photosphere where Helium lies deeper than Hydrogen. We suggest that the large diversity of the spectroscopic features seen in TDEs along with their X-ray properties, can potentially be attributed to viewing angle effects. △ Less

Submitted 25 March, 2022; v1 submitted 31 August, 2021; originally announced September 2021.

Comments: Published in A&A (part of 2022 A&A Highlights). 31 pages (10 of the Appendix), 21 Figures

Journal ref: A&A 659, A34 (2022)

Internal Shortest Absent Word Queries in Constant Time and Linear Space

Authors: Golnaz Badkobeh, Panagiotis Charalampopoulos, Dmitry Kosolobov, Solon P. Pissis

Abstract: Given a string $T$ of length $n$ over an alphabet $Σ\subset \{1,2,\ldots,n^{O(1)}\}$ of size $σ$, we are to preprocess $T$ so that given a range $[i,j]$, we can return a representation of a shortest string over $Σ$ that is absent in the fragment $T[i]\cdots T[j]$ of $T$. We present an $O(n)$-space data structure that answers such queries in constant time and can be constructed in $O(n\log_σn)$ tim… ▽ More Given a string $T$ of length $n$ over an alphabet $Σ\subset \{1,2,\ldots,n^{O(1)}\}$ of size $σ$, we are to preprocess $T$ so that given a range $[i,j]$, we can return a representation of a shortest string over $Σ$ that is absent in the fragment $T[i]\cdots T[j]$ of $T$. We present an $O(n)$-space data structure that answers such queries in constant time and can be constructed in $O(n\log_σn)$ time. △ Less

Submitted 3 June, 2021; originally announced June 2021.

Comments: 13 pages, 1 figure, 4 tables

Faster Algorithms for Longest Common Substring

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski

Abstract: In the classic longest common substring (LCS) problem, we are given two strings $S$ and $T$, each of length at most $n$, over an alphabet of size $σ$, and we are asked to find a longest string occurring as a fragment of both $S$ and $T$. Weiner, in his seminal paper that introduced the suffix tree, presented an $\mathcal{O}(n \log σ)$-time algorithm for this problem [SWAT 1973]. For polynomially-b… ▽ More In the classic longest common substring (LCS) problem, we are given two strings $S$ and $T$, each of length at most $n$, over an alphabet of size $σ$, and we are asked to find a longest string occurring as a fragment of both $S$ and $T$. Weiner, in his seminal paper that introduced the suffix tree, presented an $\mathcal{O}(n \log σ)$-time algorithm for this problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an $\mathcal{O}(n)$-time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in $\mathcal{O}(n \log σ/\log n )$ space and read in $\mathcal{O}(n \log σ/\log n )$ time. We show that, in this model, we can compute an LCS in time $\mathcal{O}(n \log σ/ \sqrt{\log n})$, which is sublinear in $n$ if $σ=2^{o(\sqrt{\log n})}$ (in particular, if $σ=\mathcal{O}(1)$), using optimal space $\mathcal{O}(n \log σ/\log n)$. We then lift our ideas to the problem of computing a $k$-mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of $S$ that occurs in $T$ with at most $k$ mismatches. Thankachan et al.~showed how to compute a $k$-mismatch LCS in $\mathcal{O}(n \log^k n)$ time for $k=\mathcal{O}(1)$ [J. Comput. Biol. 2016]. We show an $\mathcal{O}(n \log^{k-1/2} n)$-time algorithm, for any constant $k>0$ and irrespective of the alphabet size, using $\mathcal{O}(n)$ space as the previous approaches. We thus notably break through the well-known $n \log^k n$ barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. [STOC 2004] for string indexing with $k$ errors. △ Less

Submitted 7 May, 2021; originally announced May 2021.

An Almost Optimal Edit Distance Oracle

Authors: Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann

Abstract: We consider the problem of preprocessing two strings $S$ and $T$, of lengths $m$ and $n$, respectively, in order to be able to efficiently answer the following queries: Given positions $i,j$ in $S$ and positions $a,b$ in $T$, return the optimal alignment of $S[i \mathinner{.\,.} j]$ and $T[a \mathinner{.\,.} b]$. Let $N=mn$. We present an oracle with preprocessing time $N^{1+o(1)}$ and space… ▽ More We consider the problem of preprocessing two strings $S$ and $T$, of lengths $m$ and $n$, respectively, in order to be able to efficiently answer the following queries: Given positions $i,j$ in $S$ and positions $a,b$ in $T$, return the optimal alignment of $S[i \mathinner{.\,.} j]$ and $T[a \mathinner{.\,.} b]$. Let $N=mn$. We present an oracle with preprocessing time $N^{1+o(1)}$ and space $N^{1+o(1)}$ that answers queries in $\log^{2+o(1)}N$ time. In other words, we show that we can query the alignment of every two substrings in almost the same time it takes to compute just the alignment of $S$ and $T$. Our oracle uses ideas from our distance oracle for planar graphs [STOC 2019] and exploits the special structure of the alignment graph. Conditioned on popular hardness conjectures, this result is optimal up to subpolynomial factors. Our results apply to both edit distance and longest common subsequence (LCS). The best previously known oracle with construction time and size $\mathcal{O}(N)$ has slow $Ω(\sqrt{N})$ query time [Sakai, TCS 2019], and the one with size $N^{1+o(1)}$ and query time $\log^{2+o(1)}N$ (using a planar graph distance oracle) has slow $Ω(N^{3/2})$ construction time [Long & Pettie, SODA 2021]. We improve both approaches by roughly a $\sqrt N$ factor. △ Less

Submitted 4 March, 2021; originally announced March 2021.

Fault-Tolerant Distance Labeling for Planar Graphs

Authors: Aviv Bar-Natan, Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann

Abstract: In fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph $G$ such that from the labels of any three vertices $u,v,f$ we can infer the $u$-to-$v$ distance in the graph $G\setminus \{f\}$. We show that any directed weighted planar graph (and in fact any graph in a graph family with $O(\sqrt{n})$-size separators, such as minor-free graphs) admits fault-tolerant di… ▽ More In fault-tolerant distance labeling we wish to assign short labels to the vertices of a graph $G$ such that from the labels of any three vertices $u,v,f$ we can infer the $u$-to-$v$ distance in the graph $G\setminus \{f\}$. We show that any directed weighted planar graph (and in fact any graph in a graph family with $O(\sqrt{n})$-size separators, such as minor-free graphs) admits fault-tolerant distance labels of size $O(n^{2/3})$. We extend these labels in a way that allows us to also count the number of shortest paths, and provide additional upper and lower bounds for labels and oracles for counting shortest paths. △ Less

Submitted 14 February, 2021; originally announced February 2021.

Pattern Masking for Dictionary Matching

Authors: Panagiotis Charalampopoulos, Huiping Chen, Peter Christen, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski

Abstract: In the Pattern Masking for Dictionary Matching (PMDM) problem, we are given a dictionary $\mathcal{D}$ of $d$ strings, each of length $\ell$, a query string $q$ of length $\ell$, and a positive integer $z$, and we are asked to compute a smallest set $K\subseteq\{1,\ldots,\ell\}$, so that if $q[i]$, for all $i\in K$, is replaced by a wildcard, then $q$ matches at least $z$ strings from… ▽ More In the Pattern Masking for Dictionary Matching (PMDM) problem, we are given a dictionary $\mathcal{D}$ of $d$ strings, each of length $\ell$, a query string $q$ of length $\ell$, and a positive integer $z$, and we are asked to compute a smallest set $K\subseteq\{1,\ldots,\ell\}$, so that if $q[i]$, for all $i\in K$, is replaced by a wildcard, then $q$ matches at least $z$ strings from $\mathcal{D}$. The PMDM problem lies at the heart of two important applications featured in large-scale real-world systems: record linkage of databases that contain sensitive information, and query term dropping. In both applications, solving PMDM allows for providing data utility guarantees as opposed to existing approaches. We first show, through a reduction from the well-known $k$-Clique problem, that a decision version of the PMDM problem is NP-complete, even for strings over a binary alphabet. We present a data structure for PMDM that answers queries over $\mathcal{D}$ in time $\mathcal{O}(2^{\ell/2}(2^{\ell/2}+τ)\ell)$ and requires space $\mathcal{O}(2^{\ell}d^2/τ^2+2^{\ell/2}d)$, for any parameter $τ\in[1,d]$. We also approach the problem from a more practical perspective. We show an $\mathcal{O}((d\ell)^{k/3}+d\ell)$-time and $\mathcal{O}(d\ell)$-space algorithm for PMDM if $k=|K|=\mathcal{O}(1)$. We generalize our exact algorithm to mask multiple query strings simultaneously. We complement our results by showing a two-way polynomial-time reduction between PMDM and the Minimum Union problem [Chlamtáč et al., SODA 2017]. This gives a polynomial-time $\mathcal{O}(d^{1/4+ε})$-approximation algorithm for PMDM, which is tight under plausible complexity conjectures. △ Less

Submitted 8 March, 2024; v1 submitted 29 June, 2020; originally announced June 2020.

Comments: Published in Algorithmica. Abstract abridged due to arXiv requirements

The Number of Repetitions in 2D-Strings

Authors: Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, Wiktor Zuba

Abstract: The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to two-dimensional strings. We consider two types of repetitions in 2D-strings: 2D-runs and quartics (quartics are a 2D-version of squares in standard strings). Amir et al. introduced 2D-runs, showed that there are $O(n^3)$ of them in an $n \times n$ 2D-string and presented a simple constru… ▽ More The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to two-dimensional strings. We consider two types of repetitions in 2D-strings: 2D-runs and quartics (quartics are a 2D-version of squares in standard strings). Amir et al. introduced 2D-runs, showed that there are $O(n^3)$ of them in an $n \times n$ 2D-string and presented a simple construction giving a lower bound of $Ω(n^2)$ for their number (TCS 2020). We make a significant step towards closing the gap between these bounds by showing that the number of 2D-runs in an $n \times n$ 2D-string is $O(n^2 \log^2 n)$. In particular, our bound implies that the $O(n^2\log n + \textsf{output})$ run-time of the algorithm of Amir et al. for computing 2D-runs is also $O(n^2 \log^2 n)$. We expect this result to allow for exploiting 2D-runs algorithmically in the area of 2D pattern matching. A quartic is a 2D-string composed of $2 \times 2$ identical blocks (2D-strings) that was introduced by Apostolico and Brimkov (TCS 2000), where by quartics they meant only primitively rooted quartics, i.e. built of a primitive block. Here our notion of quartics is more general and analogous to that of squares in 1D-strings. Apostolico and Brimkov showed that there are $O(n^2 \log^2 n)$ occurrences of primitively rooted quartics in an $n \times n$ 2D-string and that this bound is attainable. Consequently the number of distinct primitively rooted quartics is $O(n^2 \log^2 n)$. Here, we prove that the number of distinct general quartics is also $O(n^2 \log^2 n)$. This extends the rich combinatorial study of the number of distinct squares in a 1D-string, that was initiated by Fraenkel and Simpson (J. Comb. Theory A 1998), to two dimensions. Finally, we show some algorithmic applications of 2D-runs. (Abstract shortened due to arXiv requirements.) △ Less

Submitted 29 June, 2020; originally announced June 2020.

Comments: To appear in the ESA 2020 proceedings

An outflow powers the optical rise of the nearby, fast-evolving tidal disruption event AT2019qiz

Authors: M. Nicholl, T. Wevers, S. R. Oates, K. D. Alexander, G. Leloudas, F. Onori, A. Jerkstrand, S. Gomez, S. Campana, I. Arcavi, P. Charalampopoulos, M. Gromadzki, N. Ihanec, P. G. Jonker, A. Lawrence, I. Mandel, S. Schulze, P. Short, J. Burke, C. McCully, D. Hiramatsu, D. A. Howell, C. Pellegrino, H. Abbot, J. P. Anderson , et al. (20 additional authors not shown)

Abstract: At 66 Mpc, AT2019qiz is the closest optical tidal disruption event (TDE) to date, with a luminosity intermediate between the bulk of the population and iPTF16fnl. Its proximity allowed a very early detection and triggering of multiwavelength and spectroscopic follow-up well before maximum light. The velocity dispersion of the host galaxy and fits to the TDE light curve indicate a black hole mass… ▽ More At 66 Mpc, AT2019qiz is the closest optical tidal disruption event (TDE) to date, with a luminosity intermediate between the bulk of the population and iPTF16fnl. Its proximity allowed a very early detection and triggering of multiwavelength and spectroscopic follow-up well before maximum light. The velocity dispersion of the host galaxy and fits to the TDE light curve indicate a black hole mass $\approx 10^6$ M$_\odot$, disrupting a star of $\approx 1$ M$_\odot$. Comprehensive UV, optical and X-ray data shows that the early optical emission is dominated by an outflow, with a luminosity evolution $L \propto t^2$, consistent with a photosphere expanding at constant velocity ($\gtrsim 2000$ km s$^{-1}$), and a line-forming region producing initially blueshifted H and He II profiles with $v=3000-10000$ km s$^{-1}$. The fastest optical ejecta approach the velocity inferred from radio detections (modelled in a forthcoming companion paper from K.~D.~Alexander et al.), thus the same outflow may be responsible for both the fast optical rise and the radio emission -- the first time this connection has been observed in a TDE. The light curve rise begins $29 \pm 2$ days before maximum light, peaking when the photosphere reaches the radius where optical photons can escape. The photosphere then undergoes a sudden transition, first cooling at constant radius then contracting at constant temperature. At the same time, the blueshifts disappear from the spectrum and Bowen fluorescence lines (N III) become prominent, implying a source of far-UV photons, while the X-ray light curve peaks at $\approx 10^{41}$ erg s$^{-1}$. Assuming that these X-rays are from prompt accretion, the size and mass of the outflow are consistent with the reprocessing layer needed to explain the large optical to X-ray ratio in this and other optical TDEs, possibly favouring accretion-powered over collision-powered outflow models. △ Less

Submitted 14 September, 2020; v1 submitted 3 June, 2020; originally announced June 2020.

Comments: Accepted for publication in MNRAS

Dynamic Longest Common Substring in Polylogarithmic Time

Authors: Panagiotis Charalampopoulos, Paweł Gawrychowski, Karol Pokorski

Abstract: The longest common substring problem consists in finding a longest string that appears as a (contiguous) substring of two input strings. We consider the dynamic variant of this problem, in which we are to maintain two dynamic strings $S$ and $T$, each of length at most $n$, that undergo substitutions of letters, in order to be able to return a longest common substring after each substitution. Rece… ▽ More The longest common substring problem consists in finding a longest string that appears as a (contiguous) substring of two input strings. We consider the dynamic variant of this problem, in which we are to maintain two dynamic strings $S$ and $T$, each of length at most $n$, that undergo substitutions of letters, in order to be able to return a longest common substring after each substitution. Recently, Amir et al. [ESA 2019] presented a solution for this problem that needs only $\tilde{\mathcal{O}}(n^{2/3})$ time per update. This brought the challenge of determining whether there exists a faster solution with polylogarithmic update time, or (as is the case for other dynamic problems), we should expect a polynomial (conditional) lower bound. We answer this question by designing a significantly faster algorithm that processes each substitution in amortized $\log^{\mathcal{O}(1)} n$ time with high probability. Our solution relies on exploiting the local consistency of the parsing of a collection of dynamic strings due to Gawrychowski et al. [SODA 2018], and on maintaining two dynamic trees with labeled bicolored leaves, so that after each update we can report a pair of nodes, one from each tree, of maximum combined weight, which have at least one common leaf-descendant of each color. We complement this with a lower bound of $Ω(\log n/ \log\log n)$ for the update time of any polynomial-size data structure that maintains the LCS of two dynamic strings, and the same lower bound for the update time of any data structure of size $\tilde{\mathcal{O}}(n)$ that maintains the LCS of a static and a dynamic string. Both lower bounds hold even allowing amortization and randomization. △ Less

Submitted 3 June, 2020; originally announced June 2020.

Comments: Full version of a paper that is to appear in the ICALP 2020 proceedings

Counting Distinct Patterns in Internal Dictionary Matching

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

Abstract: We consider the problem of preprocessing a text $T$ of length $n$ and a dictionary $\mathcal{D}$ in order to be able to efficiently answer queries $CountDistinct(i,j)$, that is, given $i$ and $j$ return the number of patterns from $\mathcal{D}$ that occur in the fragment $T[i \mathinner{.\,.} j]$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of… ▽ More We consider the problem of preprocessing a text $T$ of length $n$ and a dictionary $\mathcal{D}$ in order to be able to efficiently answer queries $CountDistinct(i,j)$, that is, given $i$ and $j$ return the number of patterns from $\mathcal{D}$ that occur in the fragment $T[i \mathinner{.\,.} j]$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$. This way, the dictionary takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total length, which could be $Θ(n\cdot d)$. An $\tilde{\mathcal{O}}(n+d)$-size data structure that answers $CountDistinct(i,j)$ queries $\mathcal{O}(\log n)$-approximately in $\tilde{\mathcal{O}}(1)$ time was recently proposed in a work that introduced internal dictionary matching [ISAAC 2019]. Here we present an $\tilde{\mathcal{O}}(n+d)$-size data structure that answers $CountDistinct(i,j)$ queries $2$-approximately in $\tilde{\mathcal{O}}(1)$ time. Using range queries, for any $m$, we give an $\tilde{\mathcal{O}}(\min(nd/m,n^2/m^2)+d)$-size data structure that answers $CountDistinct(i,j)$ queries exactly in $\tilde{\mathcal{O}}(m)$ time. We also consider the special case when the dictionary consists of all square factors of the string. We design an $\mathcal{O}(n \log^2 n)$-size data structure that allows us to count distinct squares in a text fragment $T[i \mathinner{.\,.} j]$ in $\mathcal{O}(\log n)$ time. △ Less

Submitted 12 May, 2020; originally announced May 2020.

Comments: Accepted to CPM 2020

Faster Approximate Pattern Matching: A Unified Approach

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz

Abstract: Approximate pattern matching is a natural and well-studied problem on strings: Given a text $T$, a pattern $P$, and a threshold $k$, find (the starting positions of) all substrings of $T$ that are at distance at most $k$ from $P$. We consider the two most fundamental string metrics: the Hamming distance and the edit distance. Under the Hamming distance, we search for substrings of $T$ that have at… ▽ More Approximate pattern matching is a natural and well-studied problem on strings: Given a text $T$, a pattern $P$, and a threshold $k$, find (the starting positions of) all substrings of $T$ that are at distance at most $k$ from $P$. We consider the two most fundamental string metrics: the Hamming distance and the edit distance. Under the Hamming distance, we search for substrings of $T$ that have at most $k$ mismatches with $P$, while under the edit distance, we search for substrings of $T$ that can be transformed to $P$ with at most $k$ edits. Exact occurrences of $P$ in $T$ have a very simple structure: If we assume for simplicity that $|T| \le 3|P|/2$ and trim $T$ so that $P$ occurs both as a prefix and as a suffix of $T$, then both $P$ and $T$ are periodic with a common period. However, an analogous characterization for the structure of occurrences with up to $k$ mismatches was proved only recently by Bringmann et al. [SODA'19]: Either there are $O(k^2)$ $k$-mismatch occurrences of $P$ in $T$, or both $P$ and $T$ are at Hamming distance $O(k)$ from strings with a common period $O(m/k)$. We tighten this characterization by showing that there are $O(k)$ $k$-mismatch occurrences in the case when the pattern is not (approximately) periodic, and we lift it to the edit distance setting, where we tightly bound the number of $k$-edit occurrences by $O(k^2)$ in the non-periodic case. Our proofs are constructive and let us obtain a unified framework for approximate pattern matching for both considered distances. We showcase the generality of our framework with results for the fully-compressed setting (where $T$ and $P$ are given as a straight-line program) and for the dynamic setting (where we extend a data structure of Gawrychowski et al. [SODA'18]). △ Less

Submitted 16 November, 2020; v1 submitted 17 April, 2020; originally announced April 2020.

Comments: 74 pages, 7 figures, FOCS'20

The Tidal Disruption Event AT 2018hyz I: Double-peaked emission lines and a flat Balmer decrement

Authors: P. Short, M. Nicholl, A. Lawrence, S. Gomez, I. Arcavi, T. Wevers, G. Leloudas, S. Schulze, J. P. Anderson, E. Berger, P. K. Blanchard, J. Burke, N. Castro Segura, P. Charalampopoulos, R. Chornock, L. Galbany, M. Gromadzki, L. J. Herzog, D. Hiramatsu, Keith Horne, G. Hosseinzadeh, D. Andrew Howell, N. Ihanec, C. Inserra, E. Kankare , et al. (6 additional authors not shown)

Abstract: We present results from spectroscopic observations of AT 2018hyz, a transient discovered by the ASAS-SN survey at an absolute magnitude of $M_V\sim -20.2$ mag, in the nucleus of a quiescent galaxy with strong Balmer absorption lines. AT 2018hyz shows a blue spectral continuum and broad emission lines, consistent with previous TDE candidates. High cadence follow-up spectra show broad Balmer lines a… ▽ More We present results from spectroscopic observations of AT 2018hyz, a transient discovered by the ASAS-SN survey at an absolute magnitude of $M_V\sim -20.2$ mag, in the nucleus of a quiescent galaxy with strong Balmer absorption lines. AT 2018hyz shows a blue spectral continuum and broad emission lines, consistent with previous TDE candidates. High cadence follow-up spectra show broad Balmer lines and He I in early spectra, with He II making an appearance after $\sim70-100$ days. The Balmer lines evolve from a smooth broad profile, through a boxy, asymmetric double-peaked phase consistent with accretion disc emission, and back to smooth at late times. The Balmer lines are unlike typical AGN in that they show a flat Balmer decrement (H$α$/H$β\sim1.5$), suggesting the lines are collisionally excited rather than being produced via photo-ionisation. The flat Balmer decrement together with the complex profiles suggest that the emission lines originate in a disc chromosphere, analogous to those seen in cataclysmic variables. The low optical depth of material due to a possible partial disruption may be what allows us to observe these double-peaked, collisionally excited lines. The late appearance of He II may be due to an expanding photosphere or outflow, or late-time shocks in debris collisions. △ Less

Submitted 24 September, 2020; v1 submitted 11 March, 2020; originally announced March 2020.

Comments: Published in MNRAS. Accompanied by companion paper Gomez et al. (2020)

Internal Dictionary Matching

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Abstract: We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary $\mathcal{D}$ in fragments of a given string $T$ of length $n$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$. This way, $\mathcal{D}$ takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total len… ▽ More We introduce data structures answering queries concerning the occurrences of patterns from a given dictionary $\mathcal{D}$ in fragments of a given string $T$ of length $n$. The dictionary is internal in the sense that each pattern in $\mathcal{D}$ is given as a fragment of $T$. This way, $\mathcal{D}$ takes space proportional to the number of patterns $d=|\mathcal{D}|$ rather than their total length, which could be $Θ(n\cdot d)$. In particular, we consider the following types of queries: reporting and counting all occurrences of patterns from $\mathcal{D}$ in a fragment $T[i..j]$ and reporting distinct patterns from $\mathcal{D}$ that occur in $T[i..j]$. We show how to construct, in $\mathcal{O}((n+d) \log^{\mathcal{O}(1)} n)$ time, a data structure that answers each of these queries in time $\mathcal{O}(\log^{\mathcal{O}(1)} n+|output|)$. The case of counting patterns is much more involved and needs a combination of a locally consistent parsing with orthogonal range searching. Reporting distinct patterns, on the other hand, uses the structure of maximal repetitions in strings. Finally, we provide tight---up to subpolynomial factors---upper and lower bounds for the case of a dynamic dictionary. △ Less

Submitted 25 September, 2019; originally announced September 2019.

Comments: A short version of this paper was accepted for presentation at ISAAC 2019

Weighted Shortest Common Supersequence Problem Revisited

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

Abstract: A weighted string, also known as a position weight matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSCS) problem, introduced by Amir et al. [SPIRE 2011], that is, the SCS problem on weighted strings. In the WSCS problem, we are given two weighted strings $W_1$ and $W_2$ and a threshold $\mathit{Freq}$ on probability, and… ▽ More A weighted string, also known as a position weight matrix, is a sequence of probability distributions over some alphabet. We revisit the Weighted Shortest Common Supersequence (WSCS) problem, introduced by Amir et al. [SPIRE 2011], that is, the SCS problem on weighted strings. In the WSCS problem, we are given two weighted strings $W_1$ and $W_2$ and a threshold $\mathit{Freq}$ on probability, and we are asked to compute the shortest (standard) string $S$ such that both $W_1$ and $W_2$ match subsequences of $S$ (not necessarily the same) with probability at least $\mathit{Freq}$. Amir et al. showed that this problem is NP-complete if the probabilities, including the threshold $\mathit{Freq}$, are represented by their logarithms (encoded in binary). We present an algorithm that solves the WSCS problem for two weighted strings of length $n$ over a constant-sized alphabet in $\mathcal{O}(n^2\sqrt{z} \log{z})$ time. Notably, our upper bound matches known conditional lower bounds stating that the WSCS problem cannot be solved in $\mathcal{O}(n^{2-\varepsilon})$ time or in $\mathcal{O}^*(z^{0.5-\varepsilon})$ time unless there is a breakthrough improving upon long-standing upper bounds for fundamental NP-hard problems (CNF-SAT and Subset Sum, respectively). We also discover a fundamental difference between the WSCS problem and the Weighted Longest Common Subsequence (WLCS) problem, introduced by Amir et al. [JDA 2010]. We show that the WLCS problem cannot be solved in $\mathcal{O}(n^{f(z)})$ time, for any function $f(z)$, unless $\mathrm{P}=\mathrm{NP}$. △ Less

Submitted 25 September, 2019; originally announced September 2019.

Comments: Accepted to SPIRE'19

Circular Pattern Matching with $k$ Mismatches

Authors: Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

Abstract: The $k$-mismatch problem consists in computing the Hamming distance between a pattern $P$ of length $m$ and every length-$m$ substring of a text $T$ of length $n$, if this distance is no more than $k$. In many real-world applications, any cyclic rotation of $P$ is a relevant pattern, and thus one is interested in computing the minimal distance of every length-$m$ substring of $T$ and any cyclic ro… ▽ More The $k$-mismatch problem consists in computing the Hamming distance between a pattern $P$ of length $m$ and every length-$m$ substring of a text $T$ of length $n$, if this distance is no more than $k$. In many real-world applications, any cyclic rotation of $P$ is a relevant pattern, and thus one is interested in computing the minimal distance of every length-$m$ substring of $T$ and any cyclic rotation of $P$. This is the circular pattern matching with $k$ mismatches ($k$-CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the $k$-CPM problem. Specifically, we show an $O(nk)$-time algorithm and an $O(n+\frac{n}{m}\,k^4)$-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the $k$-mismatch problem [Bringmann et al., SODA 2019]. A preliminary version of this work appeared at FCT 2019. In this version we improve the time complexity of the main algorithm from $O(n+\frac{n}{m}\,k^5)$ to $O(n+\frac{n}{m}\,k^4)$. △ Less

Submitted 13 January, 2020; v1 submitted 3 July, 2019; originally announced July 2019.

Comments: Extended version of a paper from FCT 2019

The spectral evolution of AT 2018dyb and the presence of metal lines in tidal disruption events

Authors: Giorgos Leloudas, Lixin Dai, Iair Arcavi, Paul M. Vreeswijk, Brenna Mockler, Rupak Roy, Daniele B. Malesani, Steve Schulze, Thomas Wevers, Morgan Fraser, Enrico Ramirez-Ruiz, Katie Auchettl, Jamison Burke, Giacomo Cannizzaro, Panos Charalampopoulos, Ting-Wan Chen, Aleksandar Cikota, Massimo Della Valle, Lluis Galbany, Mariusz Gromadzki, Kasper E. Heintz, Daichi Hiramatsu, Peter G. Jonker, Zuzanna Kostrzewa-Rutkowska, Kate Maguire , et al. (7 additional authors not shown)

Abstract: We present light curves and spectra of the tidal disruption event (TDE) ASASSN-18pg / AT 2018dyb spanning a period of one year. The event shows a plethora of strong emission lines, including the Balmer series, He II, He I and metal lines of O III $λ$3760 and N III $λλ$ 4100, 4640 (blended with He II). The latter lines are consistent with originating from the Bowen fluorescence mechanism. By analyz… ▽ More We present light curves and spectra of the tidal disruption event (TDE) ASASSN-18pg / AT 2018dyb spanning a period of one year. The event shows a plethora of strong emission lines, including the Balmer series, He II, He I and metal lines of O III $λ$3760 and N III $λλ$ 4100, 4640 (blended with He II). The latter lines are consistent with originating from the Bowen fluorescence mechanism. By analyzing literature spectra of past events, we conclude that these lines are common in TDEs. The spectral diversity of optical TDEs is thus larger than previously thought and includes N-rich events besides H- and He-rich events. We study how the spectral lines evolve with time, by means of their width, relative strength, and velocity offsets. The velocity width of the lines starts at $\sim$ 13000 km s$^{-1}$ and decreases with time. The ratio of He II to N III increases with time. The same is true for ASASSN-14li, which has a very similar spectrum to AT 2018dyb but its lines are narrower by a factor of $>$2. We estimate a black hole mass of $M_{\rm BH}$ = $3.3^{+5.0}_{-2.0}\times 10^6$ $M_{\odot}$ by using the $M$-$σ$ relation. This is consistent with the black hole mass derived using the MOSFiT transient fitting code. The detection of strong Bowen lines in the optical spectrum is an indirect proof for extreme ultraviolet and (reprocessed) X-ray radiation and favors an accretion origin for the TDE optical luminosity. A model where photons escape after multiple scatterings through a super-Eddington thick disk and its optically thick wind, viewed at an angle close to the disk plane, is consistent with the observations. △ Less

Submitted 17 January, 2020; v1 submitted 7 March, 2019; originally announced March 2019.

Comments: Accepted version. Updated with new photometry and spectra, including an X-shooter spectrum used to determine the BH mass. Two more figures added and line measurements tabulated. No significant scientific updates and the conclusions remain unaffected

Almost Optimal Distance Oracles for Planar Graphs

Authors: Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes, Oren Weimann

Abstract: We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, sub-polynomial or arbitrarily small polynomial factors from the naïve linear space, constant query-time lower bound. These tradeoffs include: (i) an oracle with space $\tilde{O}(n^{1+ε})$ and query… ▽ More We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are within polylogarithmic, sub-polynomial or arbitrarily small polynomial factors from the naïve linear space, constant query-time lower bound. These tradeoffs include: (i) an oracle with space $\tilde{O}(n^{1+ε})$ and query-time $\tilde{O}(1)$ for any constant $ε>0$, (ii) an oracle with space $\tilde{O}(n)$ and query-time $\tilde{O}(n^ε)$ for any constant $ε>0$, and (iii) an oracle with space $n^{1+o(1)}$ and query-time $n^{o(1)}$. △ Less

Submitted 5 November, 2018; originally announced November 2018.

Efficient Computation of Sequence Mappability

Authors: Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Juliusz Straszyński

Abstract: In the $(k,m)$-mappability problem, for a given sequence $T$ of length $n$, the goal is to compute a table whose $i$th entry is the number of indices $j \ne i$ such that the length-$m$ substrings of $T$ starting at positions $i$ and $j$ have at most $k$ mismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of $k=1$. We present… ▽ More In the $(k,m)$-mappability problem, for a given sequence $T$ of length $n$, the goal is to compute a table whose $i$th entry is the number of indices $j \ne i$ such that the length-$m$ substrings of $T$ starting at positions $i$ and $j$ have at most $k$ mismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of $k=1$. We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for $k=\mathcal{O}(1)$, works in $\mathcal{O}(n)$ space and, with high probability, in $\mathcal{O}(n \cdot \min\{m^k,\log^k n\})$ time. Our algorithm requires a careful adaptation of the $k$-errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the all-pairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop $\mathcal{O}(n^2)$-time algorithms to compute all $(k,m)$-mappability tables for a fixed $m$ and all $k\in \{0,\ldots,m\}$ or a fixed $k$ and all $m\in\{k,\ldots,n\}$. Finally, we show that, for $k,m = Θ(\log n)$, the $(k,m)$-mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper that was presented at SPIRE 2018. △ Less

Submitted 16 June, 2021; v1 submitted 31 July, 2018; originally announced July 2018.

Comments: Accepted to SPIRE 2018

ACM Class: F.2.2

Exact Distance Oracles for Planar Graphs with Failing Vertices

Authors: Panagiotis Charalampopoulos, Shay Mozes, Benjamin Tebeka

Abstract: We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex $u$, a target vertex $v$ and a set $X$ of $k$ failed vertices, such an oracle returns the length of a shortest $u$-to-$v$ path that avoids all vertices in $X$. We propose oracles that can handle any number $k$ of failures. We show several tradeoffs between space, query… ▽ More We consider exact distance oracles for directed weighted planar graphs in the presence of failing vertices. Given a source vertex $u$, a target vertex $v$ and a set $X$ of $k$ failed vertices, such an oracle returns the length of a shortest $u$-to-$v$ path that avoids all vertices in $X$. We propose oracles that can handle any number $k$ of failures. We show several tradeoffs between space, query time, and preprocessing time. In particular, for a directed weighted planar graph with $n$ vertices and any constant $k$, we show an $\tilde{\mathcal{O}}(n)$-size, $\tilde{\mathcal{O}}(\sqrt{n})$-query-time oracle. We then present a space vs. query time tradeoff: for any $q \in \lbrack 1,\sqrt n \rbrack$, we propose an oracle of size $n^{k+1+o(1)}/q^{2k}$ that answers queries in $\tilde{\mathcal{O}}(q)$ time. For single vertex failures ($k=1$), our $n^{2+o(1)}/q^2$-size, $\tilde{\mathcal{O}}(q)$-query-time oracle improves over the previously best known tradeoff of Baswana et al. [SODA 2012] by polynomial factors for $q \geq n^t$, for any $t \in (0,1/2]$. For multiple failures, no planarity exploiting results were previously known. A preliminary version of this work was presented in SODA 2019. In this version, we show improved space vs. query time tradeoffs relying on the recently proposed almost optimal distance oracles for planar graphs [Charalampopoulos et al., STOC 2019; Long and Pettie, SODA 2021]. △ Less

Submitted 30 August, 2021; v1 submitted 16 July, 2018; originally announced July 2018.

Comments: Improved space vs. query time tradeoffs

Alignment-free sequence comparison using absent words

Authors: Panagiotis Charalampopoulos, Maxime Crochemore, Gabriele Fici, Robert Mercas, Solon P. Pissis

Abstract: Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are… ▽ More Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not occur in the sequence. An absent word is {\em minimal} if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering {\em all} their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences. We also present an algorithm that, given a word $x$ of length $n$, computes the largest integer for which all factors of $x$ of that length occur in some minimal absent word of $x$ in time and space $\cO(n)$. Finally, we show that the known asymptotic upper bound on the number of minimal absent words of a word is tight. △ Less

Submitted 7 June, 2018; originally announced June 2018.

Comments: Extended version of "Linear-Time Sequence Comparison Using Minimal Absent Words & Applications" Proc. LATIN 2016, arxiv:1506.04917

Longest Common Substring Made Fully Dynamic

Authors: Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski

Abstract: In the longest common substring (LCS) problem, we are given two strings $S$ and $T$, each of length at most $n$, and we are asked to find a longest string occurring as a fragment of both $S$ and $T$. This is a classical and well-studied problem in computer science with a known $\mathcal{O}(n)$-time solution. In the fully dynamic version of the problem, edit operations are allowed in either of the… ▽ More In the longest common substring (LCS) problem, we are given two strings $S$ and $T$, each of length at most $n$, and we are asked to find a longest string occurring as a fragment of both $S$ and $T$. This is a classical and well-studied problem in computer science with a known $\mathcal{O}(n)$-time solution. In the fully dynamic version of the problem, edit operations are allowed in either of the two strings, and we are asked to report an LCS after each such operation. We present the first solution to this problem that requires sublinear time per edit operation. In particular, we show how to return an LCS in $\tilde{\mathcal{O}}(n^{2/3})$ time (or $\tilde{\mathcal{O}}(\sqrt{n})$ time if edits are allowed in only one of the two strings) after each operation using $\tilde{\mathcal{O}}(n)$ space. This line of research was recently initiated by the authors [SPIRE 2017] in a somewhat restricted dynamic variant. An $\tilde{\mathcal{O}}(n)$-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in $\tilde{\mathcal{O}}(1)$ time was presented. At CPM 2018, three papers studied analogously restricted dynamic variants of problems on strings. We show that our techniques can be used to obtain fully dynamic algorithms for several classical problems on strings, namely, computing the longest repeat, the longest palindrome and the longest Lyndon substring of a string. The only previously known sublinear-time dynamic algorithms for problems on strings were obtained for maintaining a dynamic collection of strings for comparison queries and for pattern matching with the most recent advances made by Gawrychowski et al. [SODA 2018] and by Clifford et al. [STACS 2018]. △ Less

Submitted 16 July, 2018; v1 submitted 23 April, 2018; originally announced April 2018.

Linear-Time Algorithm for Long LCF with $k$ Mismatches

Authors: Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Abstract: In the Longest Common Factor with $k$ Mismatches (LCF$_k$) problem, we are given two strings $X$ and $Y$ of total length $n$, and we are asked to find a pair of maximal-length factors, one of $X$ and the other of $Y$, such that their Hamming distance is at most $k$. Thankachan et al. show that this problem can be solved in $\mathcal{O}(n \log^k n)$ time and $\mathcal{O}(n)$ space for constant $k$.… ▽ More In the Longest Common Factor with $k$ Mismatches (LCF$_k$) problem, we are given two strings $X$ and $Y$ of total length $n$, and we are asked to find a pair of maximal-length factors, one of $X$ and the other of $Y$, such that their Hamming distance is at most $k$. Thankachan et al. show that this problem can be solved in $\mathcal{O}(n \log^k n)$ time and $\mathcal{O}(n)$ space for constant $k$. We consider the LCF$_k$($\ell$) problem in which we assume that the sought factors have length at least $\ell$, and the LCF$_k$($\ell$) problem for $\ell=Ω(\log^{2k+2} n)$, which we call the Long LCF$_k$ problem. We use difference covers to reduce the Long LCF$_k$ problem to a task involving $m=\mathcal{O}(n/\log^{k+1}n)$ synchronized factors. The latter can be solved in $\mathcal{O}(m \log^{k+1}m)$ time, which results in a linear-time algorithm for Long LCF$_k$. In general, our solution to LCF$_k$($\ell$) for arbitrary $\ell$ takes $\mathcal{O}(n + n \log^{k+1} n/\sqrt{\ell})$ time. △ Less

Submitted 18 February, 2018; originally announced February 2018.

Comments: submitted to CPM 2018