@inproceedings{13292, abstract = {The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This includes the decidability of language inclusion, which is the ultimate verification problem. Operator precedence grammars, automata, and logics have been investigated and used, for example, to verify programs with arithmetic expressions and exceptions (both of which are deterministic pushdown but lie outside the scope of the visibly pushdown languages). In this paper, we complete the picture and give, for the first time, an algebraic characterization of the class of OPLs in the form of a syntactic congruence that has finitely many equivalence classes exactly for the operator precedence languages. This is a generalization of the celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of the consequences, we show that universality and language inclusion for nondeterministic operator precedence automata can be solved by an antichain algorithm. Antichain algorithms avoid determinization and complementation through an explicit subset construction, by leveraging a quasi-order on words, which allows the pruning of the search space for counterexample words without sacrificing completeness. Antichain algorithms can be implemented symbolically, and these implementations are today the best-performing algorithms in practice for the inclusion of finite automata. We give a generic construction of the quasi-order needed for antichain algorithms from a finite syntactic congruence. This yields the first antichain algorithm for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem for OPLs in exponential time.}, author = {Henzinger, Thomas A and Kebis, Pavol and Mazzocchi, Nicolas Adrien and Sarac, Naci E}, booktitle = {50th International Colloquium on Automata, Languages, and Programming}, isbn = {9783959772785}, issn = {1868-8969}, location = {Paderborn, Germany}, pages = {129:1----129:20}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Regular methods for operator precedence languages}}, doi = {10.4230/LIPIcs.ICALP.2023.129}, volume = {261}, year = {2023}, } @article{13315, abstract = {How do statistical dependencies in measurement noise influence high-dimensional inference? To answer this, we study the paradigmatic spiked matrix model of principal components analysis (PCA), where a rank-one matrix is corrupted by additive noise. We go beyond the usual independence assumption on the noise entries, by drawing the noise from a low-order polynomial orthogonal matrix ensemble. The resulting noise correlations make the setting relevant for applications but analytically challenging. We provide characterization of the Bayes optimal limits of inference in this model. If the spike is rotation invariant, we show that standard spectral PCA is optimal. However, for more general priors, both PCA and the existing approximate message-passing algorithm (AMP) fall short of achieving the information-theoretic limits, which we compute using the replica method from statistical physics. We thus propose an AMP, inspired by the theory of adaptive Thouless–Anderson–Palmer equations, which is empirically observed to saturate the conjectured theoretical limit. This AMP comes with a rigorous state evolution analysis tracking its performance. Although we focus on specific noise distributions, our methodology can be generalized to a wide class of trace matrix ensembles at the cost of more involved expressions. Finally, despite the seemingly strong assumption of rotation-invariant noise, our theory empirically predicts algorithmic performance on real data, pointing at strong universality properties.}, author = {Barbier, Jean and Camilli, Francesco and Mondelli, Marco and Sáenz, Manuel}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences of the United States of America}, number = {30}, publisher = {National Academy of Sciences}, title = {{Fundamental limits in structured principal component analysis and how to reach them}}, doi = {10.1073/pnas.2302028120}, volume = {120}, year = {2023}, } @article{13316, abstract = {Although budding yeast has been extensively used as a model organism for studying organelle functions and intracellular vesicle trafficking, whether it possesses an independent endocytic early/sorting compartment that sorts endocytic cargos to the endo-lysosomal pathway or the recycling pathway has long been unclear. The structure and properties of the endocytic early/sorting compartment differ significantly between organisms; in plant cells, the trans-Golgi network (TGN) serves this role, whereas in mammalian cells a separate intracellular structure performs this function. The yeast syntaxin homolog Tlg2p, widely localizing to the TGN and endosomal compartments, is presumed to act as a Q-SNARE for endocytic vesicles, but which compartment is the direct target for endocytic vesicles remained unanswered. Here we demonstrate by high-speed and high-resolution 4D imaging of fluorescently labeled endocytic cargos that the Tlg2p-residing compartment within the TGN functions as the early/sorting compartment. After arriving here, endocytic cargos are recycled to the plasma membrane or transported to the yeast Rab5-residing endosomal compartment through the pathway requiring the clathrin adaptors GGAs. Interestingly, Gga2p predominantly localizes at the Tlg2p-residing compartment, and the deletion of GGAs has little effect on another TGN region where Sec7p is present but suppresses dynamics of the Tlg2-residing early/sorting compartment, indicating that the Tlg2p- and Sec7p-residing regions are discrete entities in the mutant. Thus, the Tlg2p-residing region seems to serve as an early/sorting compartment and function independently of the Sec7p-residing region within the TGN.}, author = {Toshima, Junko Y. and Tsukahara, Ayana and Nagano, Makoto and Tojima, Takuro and Siekhaus, Daria E and Nakano, Akihiko and Toshima, Jiro}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{The yeast endocytic early/sorting compartment exists as an independent sub-compartment within the trans-Golgi network}}, doi = {10.7554/eLife.84850}, volume = {12}, year = {2023}, } @article{13319, abstract = {We prove that the generator of the L2 implementation of a KMS-symmetric quantum Markov semigroup can be expressed as the square of a derivation with values in a Hilbert bimodule, extending earlier results by Cipriani and Sauvageot for tracially symmetric semigroups and the second-named author for GNS-symmetric semigroups. This result hinges on the introduction of a new completely positive map on the algebra of bounded operators on the GNS Hilbert space. This transformation maps symmetric Markov operators to symmetric Markov operators and is essential to obtain the required inner product on the Hilbert bimodule.}, author = {Vernooij, Matthijs and Wirth, Melchior}, issn = {1432-0916}, journal = {Communications in Mathematical Physics}, pages = {381--416}, publisher = {Springer Nature}, title = {{Derivations and KMS-symmetric quantum Markov semigroups}}, doi = {10.1007/s00220-023-04795-6}, volume = {403}, year = {2023}, } @phdthesis{13331, abstract = {The extension of extremal combinatorics to the setting of exterior algebra is a work in progress that gained attention recently. In this thesis, we study the combinatorial structure of exterior algebra by introducing a dictionary that translates the notions from the set systems into the framework of exterior algebra. We show both generalizations of celebrated Erdös--Ko--Rado theorem and Hilton--Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms. }, author = {Köse, Seyda}, issn = {2791-4585}, pages = {26}, publisher = {Institute of Science and Technology Austria}, title = {{Exterior algebra and combinatorics}}, doi = {10.15479/at:ista:13331}, year = {2023}, } @misc{13336, author = {Kleshnina, Maria}, publisher = {Zenodo}, title = {{kleshnina/stochgames_info: The effect of environmental information on evolution of cooperation in stochastic games}}, doi = {10.5281/ZENODO.8059564}, year = {2023}, } @article{13342, abstract = {Motile cells moving in multicellular organisms encounter microenvironments of locally heterogeneous mechanochemical composition. Individual compositional parameters like chemotactic signals, adhesiveness, and pore sizes are well known to be sensed by motile cells, providing individual guidance cues for cellular pathfinding. However, motile cells encounter diverse mechanochemical signals at the same time, raising the question of how cells respond to locally diverse and potentially competing signals on their migration routes. Here, we reveal that motile amoeboid cells require nuclear repositioning, termed nucleokinesis, for adaptive pathfinding in heterogeneous mechanochemical microenvironments. Using mammalian immune cells and the amoebaDictyostelium discoideum, we discover that frequent, rapid and long-distance nucleokinesis is a basic component of amoeboid pathfinding, enabling cells to reorientate quickly between locally competing cues. Amoeboid nucleokinesis comprises a two-step cell polarity switch and is driven by myosin II-forces, sliding the nucleus from a ‘losing’ to the ‘winning’ leading edge to re-adjust the nuclear to the cellular path. Impaired nucleokinesis distorts fast path adaptions and causes cellular arrest in the microenvironment. Our findings establish that nucleokinesis is required for amoeboid cell navigation. Given that motile single-cell amoebae, many immune cells, and some cancer cells utilize an amoeboid migration strategy, these results suggest that amoeboid nucleokinesis underlies cellular navigation during unicellular biology, immunity, and disease.}, author = {Kroll, Janina and Hauschild, Robert and Kuznetcov, Arthur and Stefanowski, Kasia and Hermann, Monika D. and Merrin, Jack and Shafeek, Lubuna B and Müller-Taubenberger, Annette and Renkawitz, Jörg}, issn = {1460-2075}, journal = {EMBO Journal}, publisher = {Embo Press}, title = {{Adaptive pathfinding by nucleokinesis during amoeboid migration}}, doi = {10.15252/embj.2023114557}, year = {2023}, } @unpublished{13447, abstract = {Asteroseismology has transformed stellar astrophysics. Red giant asteroseismology is a prime example, with oscillation periods and amplitudes that are readily detectable with time-domain space-based telescopes. These oscillations can be used to infer masses, ages and radii for large numbers of stars, providing unique constraints on stellar populations in our galaxy. The cadence, duration, and spatial resolution of the Roman galactic bulge time-domain survey (GBTDS) are well-suited for asteroseismology and will probe an important population not studied by prior missions. We identify photometric precision as a key requirement for realizing the potential of asteroseismology with Roman. A precision of 1 mmag per 15-min cadence or better for saturated stars will enable detections of the populous red clump star population in the Galactic bulge. If the survey efficiency is better than expected, we argue for repeat observations of the same fields to improve photometric precision, or covering additional fields to expand the stellar population reach if the photometric precision for saturated stars is better than 1 mmag. Asteroseismology is relatively insensitive to the timing of the observations during the mission, and the prime red clump targets can be observed in a single 70 day campaign in any given field. Complementary stellar characterization, particularly astrometry tied to the Gaia system, will also dramatically expand the diagnostic power of asteroseismology. We also highlight synergies to Roman GBTDS exoplanet science using transits and microlensing.}, author = {Huber, Daniel and Pinsonneault, Marc and Beck, Paul and Bedding, Timothy R. and Joss Bland-Hawthorn, Joss Bland-Hawthorn and Breton, Sylvain N. and Bugnet, Lisa Annabelle and Chaplin, William J. and Garcia, Rafael A. and Grunblatt, Samuel K. and Guzik, Joyce A. and Hekker, Saskia and Kawaler, Steven D. and Mathis, Stephane and Mathur, Savita and Metcalfe, Travis and Mosser, Benoit and Ness, Melissa K. and Piro, Anthony L. and Serenelli, Aldo and Sharma, Sanjib and Soderblom, David R. and Stassun, Keivan G. and Stello, Dennis and Tayar, Jamie and Belle, Gerard T. van and Zinn, Joel C.}, booktitle = {arXiv}, title = {{Asteroseismology with the Roman galactic bulge time-domain survey}}, doi = {10.48550/arXiv.2307.03237}, year = {2023}, } @article{13963, abstract = {The many-body localization (MBL) proximity effect is an intriguing phenomenon where a thermal bath localizes due to the interaction with a disordered system. The interplay of thermal and nonergodic behavior in these systems gives rise to a rich phase diagram, whose exploration is an active field of research. In this paper, we study a bosonic Hubbard model featuring two particle species representing the bath and the disordered system. Using state-of-the-art numerical techniques, we investigate the dynamics of the model in different regimes, based on which we obtain a tentative phase diagram as a function of coupling strength and bath size. When the bath is composed of a single particle, we observe clear signatures of a transition from an MBL proximity effect to a delocalized phase. Increasing the bath size, however, its thermalizing effect becomes stronger and eventually the whole system delocalizes in the range of moderate interaction strengths studied. In this regime, we characterize particle transport, revealing diffusive behavior of the originally localized bosons.}, author = {Brighi, Pietro and Ljubotina, Marko and Abanin, Dmitry A. and Serbyn, Maksym}, issn = {2469-9969}, journal = {Physical Review B}, number = {5}, publisher = {American Physical Society}, title = {{Many-body localization proximity effect in a two-species bosonic Hubbard model}}, doi = {10.1103/physrevb.108.054201}, volume = {108}, year = {2023}, } @article{13966, abstract = {We present a low-scaling diagrammatic Monte Carlo approach to molecular correlation energies. Using combinatorial graph theory to encode many-body Hugenholtz diagrams, we sample the Møller-Plesset (MPn) perturbation series, obtaining accurate correlation energies up to n=5, with quadratic scaling in the number of basis functions. Our technique reduces the computational complexity of the molecular many-fermion correlation problem, opening up the possibility of low-scaling, accurate stochastic computations for a wide class of many-body systems described by Hugenholtz diagrams.}, author = {Bighin, Giacomo and Ho, Quoc P and Lemeshko, Mikhail and Tscherbul, T. V.}, issn = {2469-9969}, journal = {Physical Review B}, number = {4}, publisher = {American Physical Society}, title = {{Diagrammatic Monte Carlo for electronic correlation in molecules: High-order many-body perturbation theory with low scaling}}, doi = {10.1103/PhysRevB.108.045115}, volume = {108}, year = {2023}, } @article{13969, abstract = {Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider good drawings, i.e., we require that any two edges have at most one common point which can be a common vertex or a crossing. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of a good drawing with no toothed hole. In general the number of toothed holes has to be added to the 8-approximation. In the special case of circular drawings the approximation factor is 8, this improves upon the 10-approximation of Fink et al. [14]. Our approach also works with the same approximation factor for families of pseudosegments, i.e., curves intersecting at most once. We also show how to compute a 9/2-approximation when the intersection graph of the pseudosegments is bipartite and has no toothed hole.}, author = {Arroyo Guevara, Alan M and Felsner, Stefan}, issn = {1526-1719}, journal = {Journal of Graph Algorithms and Applications}, number = {6}, pages = {433--457}, publisher = {Brown University}, title = {{Approximating the bundled crossing number}}, doi = {10.7155/jgaa.00629}, volume = {27}, year = {2023}, } @article{13970, author = {Madani, Amiera and Sletten, Eric T. and Cavedon, Cristian and Seeberger, Peter H. and Pieber, Bartholomäus}, issn = {2333-3553}, journal = {Organic Syntheses}, pages = {271--286}, publisher = {Organic Syntheses}, title = {{Visible-light-mediated oxidative debenzylation of 3-O-Benzyl-1,2:5,6-di-O-isopropylidene-α-D-glucofuranose}}, doi = {10.15227/orgsyn.100.0271}, volume = {100}, year = {2023}, } @article{13971, abstract = {When in equilibrium, thermal forces agitate molecules, which then diffuse, collide and bind to form materials. However, the space of accessible structures in which micron-scale particles can be organized by thermal forces is limited, owing to the slow dynamics and metastable states. Active agents in a passive fluid generate forces and flows, forming a bath with active fluctuations. Two unanswered questions are whether those active agents can drive the assembly of passive components into unconventional states and which material properties they will exhibit. Here we show that passive, sticky beads immersed in a bath of swimming Escherichia coli bacteria aggregate into unconventional clusters and gels that are controlled by the activity of the bath. We observe a slow but persistent rotation of the aggregates that originates in the chirality of the E. coli flagella and directs aggregation into structures that are not accessible thermally. We elucidate the aggregation mechanism with a numerical model of spinning, sticky beads and reproduce quantitatively the experimental results. We show that internal activity controls the phase diagram and the structure of the aggregates. Overall, our results highlight the promising role of active baths in designing the structural and mechanical properties of materials with unconventional phases.}, author = {Grober, Daniel and Palaia, Ivan and Ucar, Mehmet C and Hannezo, Edouard B and Šarić, Anđela and Palacci, Jérémie A}, issn = {1745-2481}, journal = {Nature Physics}, pages = {1680--1688}, publisher = {Springer Nature}, title = {{Unconventional colloidal aggregation in chiral bacterial baths}}, doi = {10.1038/s41567-023-02136-x}, volume = {19}, year = {2023}, } @article{13972, abstract = {This Special Collection is dedicated to the field of photocatalytic synthesis and contains a diverse selection of original research contributions. It includes studies on catalyst development, mechanistic investigations, method development and the use of enabling technologies, illustrating the many facets of state-of-the-art research in photocatalytic synthesis. Further, emerging topics are surveyed and discussed in three reviews and a concept article.}, author = {Næsborg, Line and Pieber, Bartholomäus and Wenger, Oliver S.}, issn = {1867-3899}, journal = {ChemCatChem}, number = {17}, publisher = {Wiley}, title = {{Special Collection: Photocatalytic synthesis}}, doi = {10.1002/cctc.202300683}, volume = {15}, year = {2023}, } @article{13976, abstract = {Conflicts and natural disasters affect entire populations of the countries involved and, in addition to the thousands of lives destroyed, have a substantial negative impact on the scientific advances these countries provide. The unprovoked invasion of Ukraine by Russia, the devastating earthquake in Turkey and Syria, and the ongoing conflicts in the Middle East are just a few examples. Millions of people have been killed or displaced, their futures uncertain. These events have resulted in extensive infrastructure collapse, with loss of electricity, transportation, and access to services. Schools, universities, and research centers have been destroyed along with decades’ worth of data, samples, and findings. Scholars in disaster areas face short- and long-term problems in terms of what they can accomplish now for obtaining grants and for employment in the long run. In our interconnected world, conflicts and disasters are no longer a local problem but have wide-ranging impacts on the entire world, both now and in the future. Here, we focus on the current and ongoing impact of war on the scientific community within Ukraine and from this draw lessons that can be applied to all affected countries where scientists at risk are facing hardship. We present and classify examples of effective and feasible mechanisms used to support researchers in countries facing hardship and discuss how these can be implemented with help from the international scientific community and what more is desperately needed. Reaching out, providing accessible training opportunities, and developing collaborations should increase inclusion and connectivity, support scientific advancements within affected communities, and expedite postwar and disaster recovery.}, author = {Wolfsberger, Walter and Chhugani, Karishma and Shchubelka, Khrystyna and Frolova, Alina and Salyha, Yuriy and Zlenko, Oksana and Arych, Mykhailo and Dziuba, Dmytro and Parkhomenko, Andrii and Smolanka, Volodymyr and Gümüş, Zeynep H. and Sezgin, Efe and Diaz-Lameiro, Alondra and Toth, Viktor R. and Maci, Megi and Bortz, Eric and Kondrashov, Fyodor and Morton, Patricia M. and Łabaj, Paweł P. and Romero, Veronika and Hlávka, Jakub and Mangul, Serghei and Oleksyk, Taras K.}, issn = {2047-217X}, journal = {GigaScience}, publisher = {Oxford University Press}, title = {{Scientists without borders: Lessons from Ukraine}}, doi = {10.1093/gigascience/giad045}, volume = {12}, year = {2023}, } @article{14037, abstract = {Traditionally, nuclear spin is not considered to affect biological processes. Recently, this has changed as isotopic fractionation that deviates from classical mass dependence was reported both in vitro and in vivo. In these cases, the isotopic effect correlates with the nuclear magnetic spin. Here, we show nuclear spin effects using stable oxygen isotopes (16O, 17O, and 18O) in two separate setups: an artificial dioxygen production system and biological aquaporin channels in cells. We observe that oxygen dynamics in chiral environments (in particular its transport) depend on nuclear spin, suggesting future applications for controlled isotope separation to be used, for instance, in NMR. To demonstrate the mechanism behind our findings, we formulate theoretical models based on a nuclear-spin-enhanced switch between electronic spin states. Accounting for the role of nuclear spin in biology can provide insights into the role of quantum effects in living systems and help inspire the development of future biotechnology solutions.}, author = {Vardi, Ofek and Maroudas-Sklare, Naama and Kolodny, Yuval and Volosniev, Artem and Saragovi, Amijai and Galili, Nir and Ferrera, Stav and Ghazaryan, Areg and Yuran, Nir and Affek, Hagit P. and Luz, Boaz and Goldsmith, Yonaton and Keren, Nir and Yochelis, Shira and Halevy, Itay and Lemeshko, Mikhail and Paltiel, Yossi}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences of the United States of America}, number = {32}, publisher = {National Academy of Sciences}, title = {{Nuclear spin effects in biological processes}}, doi = {10.1073/pnas.2300828120}, volume = {120}, year = {2023}, } @article{14039, abstract = {Membranes are essential for life. They act as semi-permeable boundaries that define cells and organelles. In addition, their surfaces actively participate in biochemical reaction networks, where they confine proteins, align reaction partners, and directly control enzymatic activities. Membrane-localized reactions shape cellular membranes, define the identity of organelles, compartmentalize biochemical processes, and can even be the source of signaling gradients that originate at the plasma membrane and reach into the cytoplasm and nucleus. The membrane surface is, therefore, an essential platform upon which myriad cellular processes are scaffolded. In this review, we summarize our current understanding of the biophysics and biochemistry of membrane-localized reactions with particular focus on insights derived from reconstituted and cellular systems. We discuss how the interplay of cellular factors results in their self-organization, condensation, assembly, and activity, and the emergent properties derived from them.}, author = {Leonard, Thomas A. and Loose, Martin and Martens, Sascha}, issn = {1878-1551}, journal = {Developmental Cell}, number = {15}, pages = {1315--1332}, publisher = {Elsevier}, title = {{The membrane surface as a platform that organizes cellular and biochemical processes}}, doi = {10.1016/j.devcel.2023.06.001}, volume = {58}, year = {2023}, } @article{14040, abstract = {Robust oxygenic photosynthesis requires a suite of accessory factors to ensure efficient assembly and repair of the oxygen-evolving photosystem two (PSII) complex. The highly conserved Ycf48 assembly factor binds to the newly synthesized D1 reaction center polypeptide and promotes the initial steps of PSII assembly, but its binding site is unclear. Here we use cryo-electron microscopy to determine the structure of a cyanobacterial PSII D1/D2 reaction center assembly complex with Ycf48 attached. Ycf48, a 7-bladed beta propeller, binds to the amino-acid residues of D1 that ultimately ligate the water-oxidising Mn4CaO5 cluster, thereby preventing the premature binding of Mn2+ and Ca2+ ions and protecting the site from damage. Interactions with D2 help explain how Ycf48 promotes assembly of the D1/D2 complex. Overall, our work provides valuable insights into the early stages of PSII assembly and the structural changes that create the binding site for the Mn4CaO5 cluster.}, author = {Zhao, Ziyu and Vercellino, Irene and Knoppová, Jana and Sobotka, Roman and Murray, James W. and Nixon, Peter J. and Sazanov, Leonid A and Komenda, Josef}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{The Ycf48 accessory factor occupies the site of the oxygen-evolving manganese cluster during photosystem II biogenesis}}, doi = {10.1038/s41467-023-40388-6}, volume = {14}, year = {2023}, } @article{14041, abstract = {Tissue morphogenesis and patterning during development involve the segregation of cell types. Segregation is driven by differential tissue surface tensions generated by cell types through controlling cell-cell contact formation by regulating adhesion and actomyosin contractility-based cellular cortical tensions. We use vertebrate tissue cell types and zebrafish germ layer progenitors as in vitro models of 3-dimensional heterotypic segregation and developed a quantitative analysis of their dynamics based on 3D time-lapse microscopy. We show that general inhibition of actomyosin contractility by the Rho kinase inhibitor Y27632 delays segregation. Cell type-specific inhibition of non-muscle myosin2 activity by overexpression of myosin assembly inhibitor S100A4 reduces tissue surface tension, manifested in decreased compaction during aggregation and inverted geometry observed during segregation. The same is observed when we express a constitutively active Rho kinase isoform to ubiquitously keep actomyosin contractility high at cell-cell and cell-medium interfaces and thus overriding the interface-specific regulation of cortical tensions. Tissue surface tension regulation can become an effective tool in tissue engineering.}, author = {Méhes, Elod and Mones, Enys and Varga, Máté and Zsigmond, Áron and Biri-Kovács, Beáta and Nyitray, László and Barone, Vanessa and Krens, Gabriel and Heisenberg, Carl-Philipp J and Vicsek, Tamás}, issn = {2399-3642}, journal = {Communications Biology}, publisher = {Springer Nature}, title = {{3D cell segregation geometry and dynamics are governed by tissue surface tension regulation}}, doi = {10.1038/s42003-023-05181-7}, volume = {6}, year = {2023}, } @article{14043, abstract = {Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form Lx=b, where L is the Laplacian matrix of a weighted graph with weights w(i,j)>0 on the edges. The solution x of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i, j) is 1/w(i, j). Kelner et al. (in: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pp 911–920, 2013. https://doi.org/10.1145/2488608.2488724) give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector–matrix-vector problem, which has been conjectured to be difficult for dynamic algorithms (Henzinger et al., in: Proceedings of the 47th Annual ACM Symposium on the Theory of Computing, pp 21–30, 2015. https://doi.org/10.1145/2746539.2746609). The conjecture implies that the data structure does not have an O(n1−ϵ) time algorithm for any ϵ>0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an O˜(m1.5) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m1+ϵ) for any ϵ>0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart.}, author = {Henzinger, Monika H and Jin, Billy and Peng, Richard and Williamson, David P.}, issn = {1432-0541}, journal = {Algorithmica}, pages = {2680--3716}, publisher = {Springer Nature}, title = {{A combinatorial cut-toggling algorithm for solving Laplacian linear systems}}, doi = {10.1007/s00453-023-01154-8}, volume = {85}, year = {2023}, }