@article{13268, abstract = {We give a simple argument to prove Nagai’s conjecture for type II degenerations of compact hyperkähler manifolds and cohomology classes of middle degree. Under an additional assumption, the techniques yield the conjecture in arbitrary degree. This would complete the proof of Nagai’s conjecture in general, as it was proved already for type I degenerations by Kollár, Laza, Saccà, and Voisin [10] and independently by Soldatenkov [18], while it is immediate for type III degenerations. Our arguments are close in spirit to a recent paper by Harder [8] proving similar results for the restrictive class of good degenerations.}, author = {Huybrechts, D. and Mauri, Mirko}, issn = {1945-001X}, journal = {Mathematical Research Letters}, number = {1}, pages = {125--141}, publisher = {International Press of Boston}, title = {{On type II degenerations of hyperkähler manifolds}}, doi = {10.4310/mrl.2023.v30.n1.a6}, volume = {30}, year = {2023}, } @inproceedings{14609, abstract = {Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol among n = 3t + 1 nodes that can tolerate up to t malicious nodes and support any reconstruction threshold ℓ ≥ t. Our protocol has an expected O(κn3) communication cost, where κ is the security parameter, and only assumes the hardness of the Discrete Logarithm. The core ingredient of our ADKG protocol is an asynchronous protocol to secret share a random polynomial of degree ℓ ≥ t, which has other applications, such as asynchronous proactive secret sharing and asynchronous multiparty computation. We implement our high-threshold ADKG protocol and evaluate it using a network of up to 128 geographically distributed nodes. Our evaluation shows that our high-threshold ADKG protocol reduces the running time by 90% and bandwidth usage by 80% over the state-of-the-art.}, author = {Das, Sourav and Xiang, Zhuolun and Kokoris Kogias, Eleftherios and Ren, Ling}, booktitle = {32nd USENIX Security Symposium}, isbn = {9781713879497}, location = {Anaheim, CA, United States}, pages = {5359--5376}, publisher = {Usenix Association}, title = {{Practical asynchronous high-threshold distributed key generation and distributed polynomial sampling}}, volume = {8}, year = {2023}, } @inproceedings{14718, abstract = {Binary decision diagrams (BDDs) are one of the fundamental data structures in formal methods and computer science in general. However, the performance of BDD-based algorithms greatly depends on memory latency due to the reliance on large hash tables and thus, by extension, on the speed of random memory access. This hinders the full utilisation of resources available on modern CPUs, since the absolute memory latency has not improved significantly for at least a decade. In this paper, we explore several implementation techniques that improve the performance of BDD manipulation either through enhanced memory locality or by partially eliminating random memory access. On a benchmark suite of 600+ BDDs derived from real-world applications, we demonstrate runtime that is comparable or better than parallelising the same operations on eight CPU cores. }, author = {Pastva, Samuel and Henzinger, Thomas A}, booktitle = {Proceedings of the 23rd Conference on Formal Methods in Computer-Aided Design}, isbn = {9783854480600}, location = {Ames, IA, United States}, pages = {122--131}, publisher = {TU Wien Academic Press}, title = {{Binary decision diagrams on modern hardware}}, doi = {10.34727/2023/isbn.978-3-85448-060-0_20}, year = {2023}, } @article{14799, abstract = {A round-robin study has been carried out to estimate the impact of the human element in small-angle scattering data analysis. Four corrected datasets were provided to participants ready for analysis. All datasets were measured on samples containing spherical scatterers, with two datasets in dilute dispersions and two from powders. Most of the 46 participants correctly identified the number of populations in the dilute dispersions, with half of the population mean entries within 1.5% and half of the population width entries within 40%. Due to the added complexity of the structure factor, far fewer people submitted answers on the powder datasets. For those that did, half of the entries for the means and widths were within 44 and 86%, respectively. This round-robin experiment highlights several causes for the discrepancies, for which solutions are proposed.}, author = {Pauw, Brian R. and Smales, Glen J. and Anker, Andy S. and Annadurai, Venkatasamy and Balazs, Daniel and Bienert, Ralf and Bouwman, Wim G. and Breßler, Ingo and Breternitz, Joachim and Brok, Erik S. and Bryant, Gary and Clulow, Andrew J. and Crater, Erin R. and De Geuser, Frédéric and Giudice, Alessandra Del and Deumer, Jérôme and Disch, Sabrina and Dutt, Shankar and Frank, Kilian and Fratini, Emiliano and Garcia, Paulo R.A.F. and Gilbert, Elliot P. and Hahn, Marc B. and Hallett, James and Hohenschutz, Max and Hollamby, Martin and Huband, Steven and Ilavsky, Jan and Jochum, Johanna K. and Juelsholt, Mikkel and Mansel, Bradley W. and Penttilä, Paavo and Pittkowski, Rebecca K. and Portale, Giuseppe and Pozzo, Lilo D. and Rochels, Leonhard and Rosalie, Julian M. and Saloga, Patrick E.J. and Seibt, Susanne and Smith, Andrew J. and Smith, Gregory N. and Spiering, Glenn A. and Stawski, Tomasz M. and Taché, Olivier and Thünemann, Andreas F. and Toth, Kristof and Whitten, Andrew E. and Wuttke, Joachim}, issn = {1600-5767}, journal = {Journal of Applied Crystallography}, number = {6}, pages = {1618--1629}, publisher = {International Union of Crystallography}, title = {{The human factor: Results of a small-angle scattering data analysis round robin}}, doi = {10.1107/S1600576723008324}, volume = {56}, year = {2023}, } @inproceedings{14243, abstract = {Two-player zero-sum "graph games" are central in logic, verification, and multi-agent systems. The game proceeds by placing a token on a vertex of a graph, and allowing the players to move it to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the players alternate turns in moving the token. In "bidding games", however, the players have budgets and in each turn, an auction (bidding) determines which player moves the token. So far, bidding games have only been studied as full-information games. In this work we initiate the study of partial-information bidding games: we study bidding games in which a player's initial budget is drawn from a known probability distribution. We show that while for some bidding mechanisms and objectives, it is straightforward to adapt the results from the full-information setting to the partial-information setting, for others, the analysis is significantly more challenging, requires new techniques, and gives rise to interesting results. Specifically, we study games with "mean-payoff" objectives in combination with "poorman" bidding. We construct optimal strategies for a partially-informed player who plays against a fully-informed adversary. We show that, somewhat surprisingly, the "value" under pure strategies does not necessarily exist in such games.}, author = {Avni, Guy and Jecker, Ismael R and Zikelic, Dorde}, booktitle = {Proceedings of the 37th AAAI Conference on Artificial Intelligence}, isbn = {9781577358800}, location = {Washington, DC, United States}, number = {5}, pages = {5464--5471}, publisher = {AAAI Press}, title = {{Bidding graph games with partially-observable budgets}}, doi = {10.1609/aaai.v37i5.25679}, volume = {37}, year = {2023}, } @inproceedings{15364, abstract = {Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and k-means++ can make Ω(ndk) time when clustering n points in a d-dimensional space (represented by an n×d matrix X) into k clusters. On massive datasets with moderate to large k, the multiplicative k factor can become very expensive. We introduce a simple randomized clustering algorithm that provably runs in expected time O(nnz(X)+nlogn) for arbitrary k. Here nnz(X) is the total number of non-zero entries in the input dataset X, which is upper bounded by nd and can be significantly smaller for sparse datasets. We prove that our algorithm achieves approximation ratio ˜O(k4) on any input dataset for the k-means objective, and our experiments show that the quality of the clusters found by our algorithm is usually much better than this worst-case bound. We use our algorithm for k-means clustering and for coreset construction; our experiments show that it gives a new tradeoff between running time and cluster quality compared to previous state-of-the-art methods for these tasks. Our theoretical analysis is based on novel results of independent interest. We show that the approximation ratio achieved after a random one-dimensional projection can be lifted to the original points and that k-means++ seeding can be implemented in expected time O(nlogn) in one dimension.}, author = {Charikar, Moses and Hu, Lunjia and Henzinger, Monika H and Vötsch, Maximilian and Waingarten, Erik}, booktitle = {37th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {New Orleans, LA, United States}, publisher = {Neural Information Processing Systems Foundation}, title = {{Simple, scalable and effective clustering via one-dimensional projections}}, volume = {36}, year = {2023}, } @inproceedings{15363, abstract = {Knowledge distillation is a popular approach for enhancing the performance of "student" models, with lower representational capacity, by taking advantage of more powerful "teacher" models. Despite its apparent simplicity, the underlying mechanics behind knowledge distillation (KD) are not yet fully understood. In this work, we shed new light on the inner workings of this method, by examining it from an optimization perspective. Specifically, we show that, in the context of linear and deep linear models, KD can be interpreted as a novel type of stochastic variance reduction mechanism. We provide a detailed convergence analysis of the resulting dynamics, which hold under standard assumptions for both strongly-convex and non-convex losses, showing that KD acts as a form of \emph{partial variance reduction}, which can reduce the stochastic gradient noise, but may not eliminate it completely, depending on the properties of the teacher'' model. Our analysis puts further emphasis on the need for careful parametrization of KD, in particular w.r.t. the weighting of the distillation loss, and is validated empirically on both linear models and deep neural networks.}, author = {Safaryan, Mher and Peste, Elena-Alexandra and Alistarh, Dan-Adrian}, booktitle = {36th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {New Orleans, LA, United States}, publisher = {Neural Information Processing Systems Foundation}, title = {{Knowledge distillation performs partial variance reduction}}, volume = {36}, year = {2023}, } @inproceedings{14921, abstract = {Neural collapse (NC) refers to the surprising structure of the last layer of deep neural networks in the terminal phase of gradient descent training. Recently, an increasing amount of experimental evidence has pointed to the propagation of NC to earlier layers of neural networks. However, while the NC in the last layer is well studied theoretically, much less is known about its multi-layered counterpart - deep neural collapse (DNC). In particular, existing work focuses either on linear layers or only on the last two layers at the price of an extra assumption. Our paper fills this gap by generalizing the established analytical framework for NC - the unconstrained features model - to multiple non-linear layers. Our key technical contribution is to show that, in a deep unconstrained features model, the unique global optimum for binary classification exhibits all the properties typical of DNC. This explains the existing experimental evidence of DNC. We also empirically show that (i) by optimizing deep unconstrained features models via gradient descent, the resulting solution agrees well with our theory, and (ii) trained networks recover the unconstrained features suitable for the occurrence of DNC, thus supporting the validity of this modeling principle.}, author = {Súkeník, Peter and Mondelli, Marco and Lampert, Christoph}, booktitle = {37th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {New Orleans, LA, United States}, publisher = {Neural Information Processing Systems Foundation}, title = {{Deep neural collapse is provably optimal for the deep unconstrained features model}}, year = {2023}, } @inproceedings{14260, abstract = {This paper presents Lincheck, a new practical and user-friendly framework for testing concurrent algorithms on the Java Virtual Machine (JVM). Lincheck provides a simple and declarative way to write concurrent tests: instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The framework automatically generates a set of concurrent scenarios, examines them using stress-testing or bounded model checking, and verifies that the results of each invocation are correct. Notably, if an error is detected via model checking, Lincheck provides an easy-to-follow trace to reproduce it, significantly simplifying the bug investigation. To the best of our knowledge, Lincheck is the first production-ready tool on the JVM that offers such a simple way of writing concurrent tests, without requiring special skills or expertise. We successfully integrated Lincheck in the development process of several large projects, such as Kotlin Coroutines, and identified new bugs in popular concurrency libraries, such as a race in Java’s standard ConcurrentLinkedDeque and a liveliness bug in Java’s AbstractQueuedSynchronizer framework, which is used in most of the synchronization primitives. We believe that Lincheck can significantly improve the quality and productivity of concurrent algorithms research and development and become the state-of-the-art tool for checking their correctness.}, author = {Koval, Nikita and Fedorov, Alexander and Sokolova, Maria and Tsitelov, Dmitry and Alistarh, Dan-Adrian}, booktitle = {35th International Conference on Computer Aided Verification}, isbn = {9783031377051}, issn = {1611-3349}, location = {Paris, France}, pages = {156--169}, publisher = {Springer Nature}, title = {{Lincheck: A practical framework for testing concurrent data structures on JVM}}, doi = {10.1007/978-3-031-37706-8_8}, volume = {13964}, year = {2023}, } @inproceedings{14259, abstract = {We provide a learning-based technique for guessing a winning strategy in a parity game originating from an LTL synthesis problem. A cheaply obtained guess can be useful in several applications. Not only can the guessed strategy be applied as best-effort in cases where the game’s huge size prohibits rigorous approaches, but it can also increase the scalability of rigorous LTL synthesis in several ways. Firstly, checking whether a guessed strategy is winning is easier than constructing one. Secondly, even if the guess is wrong in some places, it can be fixed by strategy iteration faster than constructing one from scratch. Thirdly, the guess can be used in on-the-fly approaches to prioritize exploration in the most fruitful directions. In contrast to previous works, we (i) reflect the highly structured logical information in game’s states, the so-called semantic labelling, coming from the recent LTL-to-automata translations, and (ii) learn to reflect it properly by learning from previously solved games, bringing the solving process closer to human-like reasoning.}, author = {Kretinsky, Jan and Meggendorfer, Tobias and Prokop, Maximilian and Rieder, Sabine}, booktitle = {35th International Conference on Computer Aided Verification}, isbn = {9783031377051}, issn = {1611-3349}, location = {Paris, France}, pages = {390--414}, publisher = {Springer Nature}, title = {{Guessing winning policies in LTL synthesis by semantic learning}}, doi = {10.1007/978-3-031-37706-8_20}, volume = {13964}, year = {2023}, } @misc{14995, abstract = {Lincheck is a new practical and user-friendly framework for testing concurrent data structures on the Java Virtual Machine (JVM). It provides a simple and declarative way to write concurrent tests. Instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The artifact presents a collection of Lincheck tests that discover new bugs in popular libraries and implementations from the concurrency literature -- they are listed in Table 1, Section 3. To evaluate the performance of Lincheck analysis, the collection of tests also includes those which check correct data structures and, thus, always succeed. Similarly to Table 2, Section 3, the experiments demonstrate the reasonable time to perform a test. Finally, Lincheck provides user-friendly output with an easy-to-follow trace to reproduce a detected error, significantly simplifying further investigation.}, author = {Koval, Nikita and Fedorov, Alexander and Sokolova, Maria and Tsitelov, Dmitry and Alistarh, Dan-Adrian}, publisher = {Zenodo}, title = {{Lincheck: A practical framework for testing concurrent data structures on JVM}}, doi = {10.5281/ZENODO.7877757}, year = {2023}, } @article{12960, abstract = {Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider its piecewise linear (PL) approximation M^ based on a triangulation T of the ambient space Rd. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ=1/D (and unavoidably exponential in n). Since it is known that for δ=Ω(d2.5), M^ is O(D2)-close and isotopic to M , our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M^ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. }, author = {Boissonnat, Jean Daniel and Kachanovich, Siargey and Wintraecken, Mathijs}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {2}, pages = {452--486}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations}}, doi = {10.1137/21M1412918}, volume = {52}, year = {2023}, } @article{14256, abstract = {Context. Space asteroseismology is revolutionizing our knowledge of the internal structure and dynamics of stars. A breakthrough is ongoing with the recent discoveries of signatures of strong magnetic fields in the core of red giant stars. The key signature for such a detection is the asymmetry these fields induce in the frequency splittings of observed dipolar mixed gravito-acoustic modes. Aims. We investigate the ability of the observed asymmetries of the frequency splittings of dipolar mixed modes to constrain the geometrical properties of deep magnetic fields. Methods. We used the powerful analytical Racah-Wigner algebra used in quantum mechanics to characterize the geometrical couplings of dipolar mixed oscillation modes with various realistically plausible topologies of fossil magnetic fields. We also computed the induced perturbation of their frequencies. Results. First, in the case of an oblique magnetic dipole, we provide the exact analytical expression of the asymmetry as a function of the angle between the rotation and magnetic axes. Its value provides a direct measure of this angle. Second, considering a combination of axisymmetric dipolar and quadrupolar fields, we show how the asymmetry is blind to the unraveling of the relative strength and sign of each component. Finally, in the case of a given multipole, we show that a negative asymmetry is a signature of non-axisymmetric topologies. Conclusions. Asymmetries of dipolar mixed modes provide a key bit of information on the geometrical topology of deep fossil magnetic fields, but this is insufficient on its own. Asteroseismic constraints should therefore be combined with spectropolarimetric observations and numerical simulations, which aim to predict the more probable stable large-scale geometries.}, author = {Mathis, S. and Bugnet, Lisa Annabelle}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, publisher = {EDP Sciences}, title = {{Asymmetries of frequency splittings of dipolar mixed modes: A window on the topology of deep magnetic fields}}, doi = {10.1051/0004-6361/202346832}, volume = {676}, year = {2023}, } @phdthesis{14547, abstract = {Superconductor-semiconductor heterostructures currently capture a significant amount of research interest and they serve as the physical platform in many proposals towards topological quantum computation. Despite being under extensive investigations, historically using transport techniques, the basic properties of the interface between the superconductor and the semiconductor remain to be understood. In this thesis, two separate studies on the Al-InAs heterostructures are reported with the first focusing on the physics of the material motivated by the emergence of a new phase, the Bogoliubov-Fermi surface. The second focuses on a technological application, a gate-tunable Josephson parametric amplifier. In the first study, we investigate the hypothesized unconventional nature of the induced superconductivity at the interface between the Al thin film and the InAs quantum well. We embed a two-dimensional Al-InAs hybrid system in a resonant microwave circuit allowing measurements of change in inductance. The behaviour of the resonance in a range of temperature and in-plane magnetic field has been studied and compared with the theory of conventional s-wave superconductor and a two-component theory that includes both contribution of the $s$-wave pairing in Al and the intraband $p \pm ip$ pairing in InAs. Measuring the temperature dependence of resonant frequency, no discrepancy is found between data and the conventional theory. We observe the breakdown of superconductivity due to an applied magnetic field which contradicts the conventional theory. In contrast, the data can be captured quantitatively by fitting to a two-component model. We find the evidence of the intraband $p \pm ip$ pairing in the InAs and the emergence of the Bogoliubov-Fermi surfaces due to magnetic field with the characteristic value $B^* = 0.33~\mathrm{T}$. From the fits, the sheet resistance of Al, the carrier density and mobility in InAs are determined. By systematically studying the anisotropy of the circuit response, we find weak anisotropy for $B < B^*$ and increasingly strong anisotropy for $B > B^*$ resulting in a pronounced two-lobe structure in polar plot of frequency versus field angle. Strong resemblance between the field dependence of dissipation and superfluid density hints at a hidden signature of the Bogoliubov-Fermi surface that is burried in the dissipation data. In the second study, we realize a parametric amplifier with a Josephson field effect transistor as the active element. The device's modest construction consists of a gated SNS weak link embedded at the center of a coplanar waveguide resonator. By applying a gate voltage, the resonant frequency is field-effect tunable over a range of 2 GHz. Modelling the JoFET minimally as a parallel RL circuit, the dissipation introduced by the JoFET can be quantitatively related to the gate voltage. We observed gate-tunable Kerr nonlinearity qualitatively in line with expectation. The JoFET amplifier has 20 dB of gain, 4 MHz of instantaneous bandwidth, and a 1dB compression point of -125.5 dBm when operated at a fixed resonant frequency. In general, the signal-to-noise ratio is improved by 5-7 dB when the JoFET amplifier is activated compared. The noise of the measurement chain and insertion loss of relevant circuit elements are calibrated to determine the expected and the real noise performance of the JoFET amplifier. As a quantification of the noise performance, the measured total input-referred noise of the JoFET amplifier is in good agreement with the estimated expectation which takes device loss into account. We found that the noise performance of the device reported in this document approaches one photon of total input-referred added noise which is the quantum limit imposed in nondegenerate parametric amplifier.}, author = {Phan, Duc T}, issn = {2663-337X}, keywords = {superconductor-semiconductor, superconductivity, Al, InAs, p-wave, superconductivity, JPA, microwave}, pages = {80}, publisher = {Institute of Science and Technology Austria}, title = {{Resonant microwave spectroscopy of Al-InAs}}, doi = {10.15479/14547}, year = {2023}, } @article{14749, abstract = {We unveil a powerful method for the stabilization of laser injection locking based on sensing variations in the output beam ellipticity of an optically seeded laser. The effect arises due to an interference between the seeding beam and the injected laser output. We demonstrate the method for a commercial semiconductor laser without the need for any internal changes to the readily operational injection locked laser system that was used. The method can also be used to increase the mode-hop free tuning range of lasers, and has the potential to fill a void in the low-noise laser industry.}, author = {Mishra, Umang and Li, Vyacheslav and Wald, Sebastian and Agafonova, Sofya and Diorico, Fritz R and Hosten, Onur}, issn = {1539-4794}, journal = {Optics Letters}, keywords = {Atomic and Molecular Physics, and Optics}, number = {15}, pages = {3973--3976}, publisher = {Optica Publishing Group}, title = {{Monitoring and active stabilization of laser injection locking using beam ellipticity}}, doi = {10.1364/ol.495553}, volume = {48}, year = {2023}, } @article{13233, abstract = {We study the impact of finite-range physics on the zero-range-model analysis of three-body recombination in ultracold atoms. We find that temperature dependence of the zero-range parameters can vary from one set of measurements to another as it may be driven by the distribution of error bars in the experiment, and not by the underlying three-body physics. To study finite-temperature effects in three-body recombination beyond the zero-range physics, we introduce and examine a finite-range model based upon a hyperspherical formalism. The systematic error discussed in this Letter may provide a significant contribution to the error bars of measured three-body parameters.}, author = {Agafonova, Sofya and Lemeshko, Mikhail and Volosniev, Artem}, issn = {2469-9934}, journal = {Physical Review A}, number = {6}, publisher = {American Physical Society}, title = {{Finite-range bias in fitting three-body loss to the zero-range model}}, doi = {10.1103/PhysRevA.107.L061304}, volume = {107}, year = {2023}, } @article{13264, abstract = {We build a parametric amplifier with a Josephson field-effect transistor (JoFET) as the active element. The resonant frequency of the device is field-effect tunable over a range of 2 GHz. The JoFET amplifier has 20 dB of gain, 4 MHz of instantaneous bandwidth, and a 1-dB compression point of -125.5 dBm when operated at a fixed resonance frequency. }, author = {Phan, Duc T and Falthansl-Scheinecker, Paul and Mishra, Umang and Strickland, W. M. and Langone, D. and Shabani, J. and Higginbotham, Andrew P}, issn = {2331-7019}, journal = {Physical Review Applied}, number = {6}, publisher = {American Physical Society}, title = {{Gate-tunable superconductor-semiconductor parametric amplifier}}, doi = {10.1103/PhysRevApplied.19.064032}, volume = {19}, year = {2023}, } @article{22162, abstract = {Given a bipartite graph G, the graphical matrix space SG consists of matrices whose non-zero entries can only be at those positions corresponding to edges in G. Tutte (J. London Math. Soc., 1947), Edmonds (J. Res. Nat. Bur. Standards Sect. B, 1967) and Lov´asz (FCT, 1979) observed connections between perfect matchings in G and full-rank matrices in SG. Dieudonn´e (Arch. Math., 1948) proved a tight upper bound on the dimensions of those matrix spaces containing only singular matrices. The starting point of this paper is a simultaneous generalization of these two classical results: we show that the largest dimension over subspaces of SG containing only singular matrices is equal to the maximum size over subgraphs of G without perfect matchings, based on Meshulam’s proof of Dieudonn´e’s result (Quart. J. Math., 1985). Starting from this result, we go on to establish more connections between properties of graphs and matrix spaces. For example, we establish connections between acyclicity and nilpotency, between strong connectivity and irreducibility, and between isomorphism and conjugacy/congruence. For each connection, we study three types of correspondences, namely the basic correspondence, the inherited correspondence (for subgraphs and subspaces), and the induced correspondence (for induced subgraphs and restrictions). Some correspondences lead to intriguing generalizations of classical results, such as Dieudonn´e’s result mentioned above, and a celebrated theorem of Gerstenhaber regarding the largest dimension of nil matrix spaces (Amer. J. Math., 1958). Finally, we show some implications of our results to quantum information and present open problems in computational complexity motivated by these results.}, author = {Li, Yinan and Qiao, Youming and Wigderson, Avi and Wigderson, Yuval and Zhang, Chuanqi}, issn = {1565-8511}, journal = {Israel Journal of Mathematics}, number = {2}, pages = {513--580}, publisher = {Springer Nature}, title = {{Connections between graphs and matrix spaces}}, doi = {10.1007/s11856-023-2515-7}, volume = {256}, year = {2023}, } @article{22159, abstract = {The size Ramsey number of a graph H is defined as the minimum number of edges in a graph G such that there is a monochromatic copy of H in every two-coloring of E(G). The size Ramsey number was introduced by Erdős, Faudree, Rousseau, and Schelp in 1978 and they ended their foundational paper by asking whether one can determine up to a constant factor the size Ramsey numbers of three families of graphs: complete bipartite graphs, book graphs (obtained by adding many common neighbors to the vertices of a clique), and starburst graphs (obtained by adding many pendant edges to each vertex of a clique). In this paper, we completely resolve the latter two questions and make substantial progress on the first by determining the size Ramsey number of Ks,t up to a constant factor for all t=Ω(s log s).}, author = {Conlon, David and Fox, Jacob and Wigderson, Yuval}, issn = {1439-6912}, journal = {Combinatorica}, number = {4}, pages = {743--768}, publisher = {Springer Nature}, title = {{Three early problems on size Ramsey numbers}}, doi = {10.1007/s00493-023-00034-7}, volume = {43}, year = {2023}, } @phdthesis{14641, abstract = {Mutation rates represent the net result of complex interactions among various cellular processes and can dramatically influence the evolutionary fate of microbial populations. However, many popular techniques used to study mutations are subject to the confounding effects of heredity and the subtleties of adaptation to selection, all of which make it difficult to observe any dynamic responses of mutation rates to fitness challenges. Furthermore, in spite of the ubiquity of quorum sensing systems across the bacterial domain and relevance for many physiological behaviors, the effects of such mechanisms on mutation rate and adaptation remain poorly understood. In the following work, I present the development of a microfluidic droplet-based method to measure single base-pair mutation rates in growing populations of the bacterium Escherichia coli. I use this method to observe a stress-induced increase in mutation rate that is mediated by luxS, a highly conserved bacterial quorum sensing component. I also show that the aforementioned increase in mutation rate, and its associated control by luxS, corresponds to a higher degree of adaptability under competitive environments.}, author = {Hennessey-Wesen, Mike}, issn = {2663-337X}, keywords = {microfluidics, miceobiology, mutations, quorum sensing}, pages = {104}, publisher = {Institute of Science and Technology Austria}, title = {{Adaptive mutation in E. coli modulated by luxS}}, doi = {10.15479/at:ista:14641}, year = {2023}, }