@article{10940, abstract = {Magnetic-field-resilient superconducting circuits enable sensing applications and hybrid quantum computing architectures involving spin or topological qubits and electromechanical elements, as well as studying flux noise and quasiparticle loss. We investigate the effect of in-plane magnetic fields up to 1 T on the spectrum and coherence times of thin-film three-dimensional aluminum transmons. Using a copper cavity, unaffected by strong magnetic fields, we can probe solely the effect of magnetic fields on the transmons. We present data on a single-junction and a superconducting-quantum-interference-device (SQUID) transmon that are cooled down in the same cavity. As expected, the transmon frequencies decrease with increasing field, due to suppression of the superconducting gap and a geometric Fraunhofer-like contribution. Nevertheless, the thin-film transmons show strong magnetic field resilience: both transmons display microsecond coherence up to at least 0.65 T, and T1 remains above 1μs over the entire measurable range. SQUID spectroscopy is feasible up to 1 T, the limit of our magnet. We conclude that thin-film aluminum Josephson junctions are suitable hardware for superconducting circuits in the high-magnetic-field regime.}, author = {Krause, J. and Dickel, C. and Vaal, E. and Vielmetter, M. and Feng, J. and Bounds, R. and Catelani, G. and Fink, Johannes M and Ando, Yoichi}, issn = {2331-7019}, journal = {Physical Review Applied}, number = {3}, publisher = {American Physical Society}, title = {{Magnetic field resilience of three-dimensional transmons with thin-film Al/AlOx/Al Josephson junctions approaching 1 T}}, doi = {10.1103/PhysRevApplied.17.034032}, volume = {17}, year = {2022}, } @article{10945, abstract = {Mica-titania pearlescent pigments (MTs) were previously coated with organic molecules to obtain combination pigments (CPs) for achieving certain improvements or functionalities. Anthocyanins (ACNs) are molecules that can be extracted from natural resources and exhibit color changes via pH modifications of the enclosing medium. The purpose of the study was to produce a new series of CPs by depositing ACNs on MTs at different pH values, to observe the changes in color, and to associate these changes to thermogravimetrically determined deposition efficiencies in light of spectral differences. The extraction and deposition methods were based on aqueous chemistry and were straightforward. The ACN deposition generally increased with increasing pH and correlated with the consistency between the charges of the MT surfaces and the dominant ACN species at a specific pH value. The fluorescence of the CPs was inversely correlated with the deposition quantities invoking the possibility of a quenching effect.}, author = {Çoruh, Mehmet Orkun and Gündüz, Güngör and Çolak, Üner and Maviş, Bora}, issn = {2079-6447}, journal = {Colorants}, number = {2}, pages = {149--164}, publisher = {MDPI}, title = {{pH-dependent coloring of combination effect pigments with anthocyanins from Brassica oleracea var. capitata F. rubra}}, doi = {10.3390/colorants1020010}, volume = {1}, year = {2022}, } @article{11051, abstract = {Nuclear pore complexes (NPCs) bridge the nucleus and the cytoplasm and are indispensable for crucial cellular activities, such as bidirectional molecular trafficking and gene transcription regulation. The discovery of long-lived proteins (LLPs) in NPCs from postmitotic cells raises the exciting possibility that the maintenance of NPC integrity might play an inherent role in lifelong cell function. Age-dependent deterioration of NPCs and loss of nuclear integrity have been linked to age-related decline in postmitotic cell function and degenerative diseases. In this review, we discuss our current understanding of NPC maintenance in proliferating and postmitotic cells, and how malfunction of nucleoporins (Nups) might contribute to the pathogenesis of various neurodegenerative and cardiovascular diseases.}, author = {Liu, Jinqiang and HETZER, Martin W}, issn = {0962-8924}, journal = {Trends in Cell Biology}, keywords = {Cell Biology}, number = {3}, pages = {P216--227}, publisher = {Elsevier}, title = {{Nuclear pore complex maintenance and implications for age-related diseases}}, doi = {10.1016/j.tcb.2021.10.001}, volume = {32}, year = {2022}, } @phdthesis{11128, abstract = {Although we often see studies focusing on simple or even discrete traits in studies of colouration, the variation of “appearance” phenotypes found in nature is often more complex, continuous and high-dimensional. Therefore, we developed automated methods suitable for large datasets of genomes and images, striving to account for their complex nature, while minimising human bias. We used these methods on a dataset of more than 20, 000 plant SNP genomes and corresponding fower images from a hybrid zone of two subspecies of Antirrhinum majus with distinctly coloured fowers to improve our understanding of the genetic nature of the fower colour in our study system. Firstly, we use the advantage of large numbers of genotyped plants to estimate the haplotypes in the main fower colour regulating region. We study colour- and geography-related characteristics of the estimated haplotypes and how they connect to their relatedness. We show discrepancies from the expected fower colour distributions given the genotype and identify particular haplotypes leading to unexpected phenotypes. We also confrm a signifcant defcit of the double recessive recombinant and quite surprisingly, we show that haplotypes of the most frequent parental type are much less variable than others. Secondly, we introduce our pipeline capable of processing tens of thousands of full fower images without human interaction and summarising each image into a set of informative scores. We show the compatibility of these machine-measured fower colour scores with the previously used manual scores and study impact of external efect on the resulting scores. Finally, we use the machine-measured fower colour scores to ft and examine a phenotype cline across the hybrid zone in Planoles using full fower images as opposed to discrete, manual scores and compare it with the genotypic cline.}, author = {Matejovicova, Lenka}, isbn = {978-3-99078-016-9}, issn = {2663-337X}, pages = {112}, publisher = {Institute of Science and Technology Austria}, title = {{Genetic basis of flower colour as a model for adaptive evolution}}, doi = {10.15479/at:ista:11128}, year = {2022}, } @article{11135, abstract = {We consider a correlated NxN Hermitian random matrix with a polynomially decaying metric correlation structure. By calculating the trace of the moments of the matrix and using the summable decay of the cumulants, we show that its operator norm is stochastically dominated by one.}, author = {Reker, Jana}, issn = {2010-3271}, journal = {Random Matrices: Theory and Applications}, keywords = {Discrete Mathematics and Combinatorics, Statistics, Probability and Uncertainty, Statistics and Probability, Algebra and Number Theory}, number = {4}, publisher = {World Scientific}, title = {{On the operator norm of a Hermitian random matrix with correlated entries}}, doi = {10.1142/s2010326322500368}, volume = {11}, year = {2022}, } @article{11142, abstract = {SnTe is a promising Pb-free thermoelectric (TE) material with high electrical conductivity. We discovered the synergistic effect of Bi2O3 on enhancing the average power factor (PF) and overall ZT value of the SnTe-based thermoelectric material. The introduction of Bi2O3 forms plenty of SnO2, Bi2O3, and Bi-rich nanoprecipitates. These interfaces between the SnTe matrix and the nanoprecipitates can enhance the average PF through the energy filtering effect. On the other hand, abundant and diverse nanoprecipitates can significantly diminish the lattice thermal conductivity (κlat) through enhanced phonon scattering. The synergistic effect of Bi2O3 resulted in a maximum ZT (ZTmax) value of 0.9 at SnTe-2% Bi2O3 and an average ZT (ZTave) value of 0.4 for SnTe-4% Bi2O3 from 300 K to 823 K. The work provides an excellent reference to develop non-toxic high-performance TE materials.}, author = {Hong, Tao and Guo, Changrong and Wang, Dongyang and Qin, Bingchao and Chang, Cheng and Gao, Xiang and Zhao, Li Dong}, issn = {2468-6069}, journal = {Materials Today Energy}, publisher = {Elsevier}, title = {{Enhanced thermoelectric performance in SnTe due to the energy filtering effect introduced by Bi2O3}}, doi = {10.1016/j.mtener.2022.100985}, volume = {25}, year = {2022}, } @article{11143, abstract = {Dravet syndrome is a neurodevelopmental disorder characterized by epilepsy, intellectual disability, and sudden death due to pathogenic variants in SCN1A with loss of function of the sodium channel subunit Nav1.1. Nav1.1-expressing parvalbumin GABAergic interneurons (PV-INs) from young Scn1a+/− mice show impaired action potential generation. An approach assessing PV-IN function in the same mice at two time points shows impaired spike generation in all Scn1a+/− mice at postnatal days (P) 16–21, whether deceased prior or surviving to P35, with normalization by P35 in surviving mice. However, PV-IN synaptic transmission is dysfunctional in young Scn1a+/− mice that did not survive and in Scn1a+/− mice ≥ P35. Modeling confirms that PV-IN axonal propagation is more sensitive to decreased sodium conductance than spike generation. These results demonstrate dynamic dysfunction in Dravet syndrome: combined abnormalities of PV-IN spike generation and propagation drives early disease severity, while ongoing dysfunction of synaptic transmission contributes to chronic pathology.}, author = {Kaneko, Keisuke and Currin, Christopher and Goff, Kevin M. and Wengert, Eric R. and Somarowthu, Ala and Vogels, Tim P and Goldberg, Ethan M.}, issn = {2211-1247}, journal = {Cell Reports}, number = {13}, publisher = {Elsevier}, title = {{Developmentally regulated impairment of parvalbumin interneuron synaptic transmission in an experimental model of Dravet syndrome}}, doi = {10.1016/j.celrep.2022.110580}, volume = {38}, year = {2022}, } @article{11144, abstract = {Thermoelectric materials allow for direct conversion between heat and electricity, offering the potential for power generation. The average dimensionless figure of merit ZTave determines device efficiency. N-type tin selenide crystals exhibit outstanding three-dimensional charge and two-dimensional phonon transport along the out-of-plane direction, contributing to a high maximum figure of merit Zmax of ~3.6 × 10−3 per kelvin but a moderate ZTave of ~1.1. We found an attractive high Zmax of ~4.1 × 10−3 per kelvin at 748 kelvin and a ZTave of ~1.7 at 300 to 773 kelvin in chlorine-doped and lead-alloyed tin selenide crystals by phonon-electron decoupling. The chlorine-induced low deformation potential improved the carrier mobility. The lead-induced mass and strain fluctuations reduced the lattice thermal conductivity. Phonon-electron decoupling plays a critical role to achieve high-performance thermoelectrics.}, author = {Su, Lizhong and Wang, Dongyang and Wang, Sining and Qin, Bingchao and Wang, Yuping and Qin, Yongxin and Jin, Yang and Chang, Cheng and Zhao, Li Dong}, issn = {1095-9203}, journal = {Science}, number = {6587}, pages = {1385--1389}, publisher = {American Association for the Advancement of Science}, title = {{High thermoelectric performance realized through manipulating layered phonon-electron decoupling}}, doi = {10.1126/science.abn8997}, volume = {375}, year = {2022}, } @inproceedings{11145, abstract = {List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.}, author = {Ferber, Asaf and Kwan, Matthew Alan and Sauermann, Lisa}, booktitle = {62nd Annual IEEE Symposium on Foundations of Computer Science}, isbn = {9781665420556}, issn = {0272-5428}, location = {Denver, CO, United States}, pages = {720--726}, publisher = {IEEE}, title = {{List-decodability with large radius for Reed-Solomon codes}}, doi = {10.1109/FOCS52979.2021.00075}, volume = {2022}, year = {2022}, } @article{11155, abstract = {The potential of energy filtering and direct electron detection for cryo-electron microscopy (cryo-EM) has been well documented. Here, we assess the performance of recently introduced hardware for cryo-electron tomography (cryo-ET) and subtomogram averaging (STA), an increasingly popular structural determination method for complex 3D specimens. We acquired cryo-ET datasets of EIAV virus-like particles (VLPs) on two contemporary cryo-EM systems equipped with different energy filters and direct electron detectors (DED), specifically a Krios G4, equipped with a cold field emission gun (CFEG), Thermo Fisher Scientific Selectris X energy filter, and a Falcon 4 DED; and a Krios G3i, with a Schottky field emission gun (XFEG), a Gatan Bioquantum energy filter, and a K3 DED. We performed constrained cross-correlation-based STA on equally sized datasets acquired on the respective systems. The resulting EIAV CA hexamer reconstructions show that both systems perform comparably in the 4–6 Å resolution range based on Fourier-Shell correlation (FSC). In addition, by employing a recently introduced multiparticle refinement approach, we obtained a reconstruction of the EIAV CA hexamer at 2.9 Å. Our results demonstrate the potential of the new generation of energy filters and DEDs for STA, and the effects of using different processing pipelines on their STA outcomes.}, author = {Obr, Martin and Hagen, Wim J.H. and Dick, Robert A. and Yu, Lingbo and Kotecha, Abhay and Schur, Florian KM}, issn = {1047-8477}, journal = {Journal of Structural Biology}, keywords = {Structural Biology}, number = {2}, publisher = {Elsevier}, title = {{Exploring high-resolution cryo-ET and subtomogram averaging capabilities of contemporary DEDs}}, doi = {10.1016/j.jsb.2022.107852}, volume = {214}, year = {2022}, } @article{11160, abstract = {Mutations in the chromodomain helicase DNA-binding 8 (CHD8) gene are a frequent cause of autism spectrum disorder (ASD). While its phenotypic spectrum often encompasses macrocephaly, implicating cortical abnormalities, how CHD8 haploinsufficiency affects neurodevelopmental is unclear. Here, employing human cerebral organoids, we find that CHD8 haploinsufficiency disrupted neurodevelopmental trajectories with an accelerated and delayed generation of, respectively, inhibitory and excitatory neurons that yields, at days 60 and 120, symmetrically opposite expansions in their proportions. This imbalance is consistent with an enlargement of cerebral organoids as an in vitro correlate of patients’ macrocephaly. Through an isogenic design of patient-specific mutations and mosaic organoids, we define genotype-phenotype relationships and uncover their cell-autonomous nature. Our results define cell-type-specific CHD8-dependent molecular defects related to an abnormal program of proliferation and alternative splicing. By identifying cell-type-specific effects of CHD8 mutations, our study uncovers reproducible developmental alterations that may be employed for neurodevelopmental disease modeling.}, author = {Villa, Carlo Emanuele and Cheroni, Cristina and Dotter, Christoph and López-Tóbon, Alejandro and Oliveira, Bárbara and Sacco, Roberto and Yahya, Aysan Çerağ and Morandell, Jasmin and Gabriele, Michele and Tavakoli, Mojtaba and Lyudchik, Julia and Sommer, Christoph M and Gabitto, Mariano and Danzl, Johann G and Testa, Giuseppe and Novarino, Gaia}, issn = {2211-1247}, journal = {Cell Reports}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {1}, publisher = {Elsevier}, title = {{CHD8 haploinsufficiency links autism to transient alterations in excitatory and inhibitory trajectories}}, doi = {10.1016/j.celrep.2022.110615}, volume = {39}, year = {2022}, } @article{11167, abstract = {Complex I is one of the major respiratory complexes, conserved from bacteria to mammals. It oxidises NADH, reduces quinone and pumps protons across the membrane, thus playing a central role in the oxidative energy metabolism. In this review we discuss our current state of understanding the structure of complex I from various species of mammals, plants, fungi, and bacteria, as well as of several complex I-related proteins. By comparing the structural evidence from these systems in different redox states and data from mutagenesis and molecular simulations, we formulate the mechanisms of electron transfer and proton pumping and explain how they are conformationally and electrostatically coupled. Finally, we discuss the structural basis of the deactivation phenomenon in mammalian complex I.}, author = {Kampjut, Domen and Sazanov, Leonid A}, issn = {0959-440X}, journal = {Current Opinion in Structural Biology}, keywords = {Molecular Biology, Structural Biology}, publisher = {Elsevier}, title = {{Structure of respiratory complex I – An emerging blueprint for the mechanism}}, doi = {10.1016/j.sbi.2022.102350}, volume = {74}, year = {2022}, } @article{11179, abstract = {Large oligomeric enzymes control a myriad of cellular processes, from protein synthesis and degradation to metabolism. The 0.5 MDa large TET2 aminopeptidase, a prototypical protease important for cellular homeostasis, degrades peptides within a ca. 60 Å wide tetrahedral chamber with four lateral openings. The mechanisms of substrate trafficking and processing remain debated. Here, we integrate magic-angle spinning (MAS) NMR, mutagenesis, co-evolution analysis and molecular dynamics simulations and reveal that a loop in the catalytic chamber is a key element for enzymatic function. The loop is able to stabilize ligands in the active site and may additionally have a direct role in activating the catalytic water molecule whereby a conserved histidine plays a key role. Our data provide a strong case for the functional importance of highly dynamic - and often overlooked - parts of an enzyme, and the potential of MAS NMR to investigate their dynamics at atomic resolution.}, author = {Gauto, Diego F. and Macek, Pavel and Malinverni, Duccio and Fraga, Hugo and Paloni, Matteo and Sučec, Iva and Hessel, Audrey and Bustamante, Juan Pablo and Barducci, Alessandro and Schanda, Paul}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Functional control of a 0.5 MDa TET aminopeptidase by a flexible loop revealed by MAS NMR}}, doi = {10.1038/s41467-022-29423-0}, volume = {13}, year = {2022}, } @inproceedings{11180, abstract = {Designing and implementing efficient parallel priority schedulers is an active research area. An intriguing proposed design is the Multi-Queue: given n threads and m ≥ n distinct priority queues, task insertions are performed uniformly at random, while, to delete, a thread picks two queues uniformly at random, and removes the observed task of higher priority. This approach scales well, and has probabilistic rank guarantees: roughly, the rank of each task removed, relative to remaining tasks in all other queues, is O (m) in expectation. Yet, the performance of this pattern is below that of well-engineered schedulers, which eschew theoretical guarantees for practical efficiency. We investigate whether it is possible to design and implement a Multi-Queue-based task scheduler that is both highly-efficient and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue (SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue affinity---each thread has a local queue, from which tasks are usually removed; but, with some probability, threads also attempt to steal higher-priority tasks from the other queues---and task batching, that is, the processing of several tasks in a single insert / remove step. These ideas are well-known for task scheduling without priorities; our theoretical contribution is showing that, despite relaxations, this design can still provide rank guarantees, which in turn implies bounds on total work performed. We provide a general SMQ implementation which can surpass state-of-the-art schedulers such as OBIM and PMOD in terms of performance on popular graph-processing benchmarks. Notably, the performance improvement comes mainly from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned approaches can still provide performance improvements for priority task scheduling.}, author = {Postnikova, Anastasiia and Koval, Nikita and Nadiradze, Giorgi and Alistarh, Dan-Adrian}, booktitle = {Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9781450392044}, location = {Seoul, Republic of Korea}, pages = {353--367}, publisher = {Association for Computing Machinery}, title = {{Multi-queues can be state-of-the-art priority schedulers}}, doi = {10.1145/3503221.3508432}, year = {2022}, } @inproceedings{11181, abstract = {To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained techniques, resulting in efficient and elegant algorithms, which can however be often difficult to understand and prove correct. While simpler techniques exist, such as transactional memory, they can have limited performance or portability relative to their fine-grained counterparts. Approaches at both ends of this complexity-performance spectrum have been extensively explored, but relatively less is known about the middle ground: approaches that are willing to sacrifice some performance for simplicity, while remaining competitive with state-of-the-art handcrafted designs. In this paper, we explore this middle ground, and present PathCAS, a primitive that combines ideas from multi-word CAS (KCAS) and transactional memory approaches, while carefully avoiding overhead. We show how PathCAS can be used to implement efficient search data structures relatively simply, using an internal binary search tree as an example, then extending this to an AVL tree. Our best implementations outperform many handcrafted search trees: in search-heavy workloads, it rivals the BCCO tree [5], the fastest known concurrent binary tree in terms of search performance [3]. Our results suggest that PathCAS can yield concurrent data structures that are relatively easy to build and prove correct, while offering surprisingly high performance.}, author = {Brown, Trevor A and Sigouin, William and Alistarh, Dan-Adrian}, booktitle = {Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9781450392044}, location = {Seoul, Republic of Korea}, pages = {385--399}, publisher = {Association for Computing Machinery}, title = {{PathCAS: An efficient middle ground for concurrent search data structures}}, doi = {10.1145/3503221.3508410}, year = {2022}, } @article{11182, abstract = {Immune cells are constantly on the move through multicellular organisms to explore and respond to pathogens and other harmful insults. While moving, immune cells efficiently traverse microenvironments composed of tissue cells and extracellular fibers, which together form complex environments of various porosity, stiffness, topography, and chemical composition. In this protocol we describe experimental procedures to investigate immune cell migration through microenvironments of heterogeneous porosity. In particular, we describe micro-channels, micro-pillars, and collagen networks as cell migration paths with alternative pore size choices. Employing micro-channels or micro-pillars that divide at junctions into alternative paths with initially differentially sized pores allows us to precisely (1) measure the cellular translocation time through these porous path junctions, (2) quantify the cellular preference for individual pore sizes, and (3) image cellular components like the nucleus and the cytoskeleton. This reductionistic experimental setup thus can elucidate how immune cells perform decisions in complex microenvironments of various porosity like the interstitium. The setup further allows investigation of the underlying forces of cellular squeezing and the consequences of cellular deformation on the integrity of the cell and its organelles. As a complementary approach that does not require any micro-engineering expertise, we describe the usage of three-dimensional collagen networks with different pore sizes. Whereas we here focus on dendritic cells as a model for motile immune cells, the described protocols are versatile as they are also applicable for other immune cell types like neutrophils and non-immune cell types such as mesenchymal and cancer cells. In summary, we here describe protocols to identify the mechanisms and principles of cellular probing, decision making, and squeezing during cellular movement through microenvironments of heterogeneous porosity.}, author = {Kroll, Janina and Ruiz-Fernandez, Mauricio J.A. and Braun, Malte B. and Merrin, Jack and Renkawitz, Jörg}, issn = {2691-1299}, journal = {Current Protocols}, number = {4}, publisher = {Wiley}, title = {{Quantifying the probing and selection of microenvironmental pores by motile immune cells}}, doi = {10.1002/cpz1.407}, volume = {2}, year = {2022}, } @inproceedings{11183, abstract = {Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph: - On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique. - On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard. - On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.}, author = {Nikabadi, Amir and Korhonen, Janne}, booktitle = {25th International Conference on Principles of Distributed Systems}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, isbn = {9783959772198}, issn = {1868-8969}, location = {Strasbourg, France}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters}}, doi = {10.4230/LIPIcs.OPODIS.2021.15}, volume = {217}, year = {2022}, } @inproceedings{11184, abstract = {Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary regular graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.}, author = {Alistarh, Dan-Adrian and Gelashvili, Rati and Rybicki, Joel}, booktitle = {25th International Conference on Principles of Distributed Systems}, editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, isbn = {9783959772198}, issn = {1868-8969}, location = {Strasbourg, France}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Fast graphical population protocols}}, doi = {10.4230/LIPIcs.OPODIS.2021.14}, volume = {217}, year = {2022}, } @inproceedings{11185, abstract = {Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider bundlings for families of pseudosegments, i.e., simple curves such that any two have share at most one point at which they cross. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of such instances (up to adding a term depending on the facial structure). This 8-approximation also holds for bundlings of good drawings of graphs. In the special case of circular drawings the approximation factor is 8 (no extra term), this improves upon the 10-approximation of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection graph of the pseudosegments is bipartite.}, author = {Arroyo Guevara, Alan M and Felsner, Stefan}, booktitle = {WALCOM 2022: Algorithms and Computation}, isbn = {9783030967307}, issn = {1611-3349}, location = {Jember, Indonesia}, pages = {383--395}, publisher = {Springer Nature}, title = {{Approximating the bundled crossing number}}, doi = {10.1007/978-3-030-96731-4_31}, volume = {13174}, year = {2022}, } @article{11186, abstract = {In this note, we study large deviations of the number 𝐍 of intercalates ( 2×2 combinatorial subsquares which are themselves Latin squares) in a random 𝑛×𝑛 Latin square. In particular, for constant 𝛿>0 we prove that exp(−𝑂(𝑛2log𝑛))⩽Pr(𝐍⩽(1−𝛿)𝑛2/4)⩽exp(−Ω(𝑛2)) and exp(−𝑂(𝑛4/3(log𝑛)))⩽Pr(𝐍⩾(1+𝛿)𝑛2/4)⩽exp(−Ω(𝑛4/3(log𝑛)2/3)) . As a consequence, we deduce that a typical order- 𝑛 Latin square has (1+𝑜(1))𝑛2/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless.}, author = {Kwan, Matthew Alan and Sah, Ashwin and Sawhney, Mehtaab}, issn = {1469-2120}, journal = {Bulletin of the London Mathematical Society}, number = {4}, pages = {1420--1438}, publisher = {Wiley}, title = {{Large deviations in random latin squares}}, doi = {10.1112/blms.12638}, volume = {54}, year = {2022}, }