@article{11356, author = {Chang, Cheng and Qin, Bingchao and Su, Lizhong and Zhao, Li Dong}, issn = {2095-9281}, journal = {Science Bulletin}, number = {11}, pages = {1105--1107}, publisher = {Elsevier}, title = {{Distinct electron and hole transports in SnSe crystals}}, doi = {10.1016/j.scib.2022.04.007}, volume = {67}, year = {2022}, } @phdthesis{11362, abstract = {Deep learning has enabled breakthroughs in challenging computing problems and has emerged as the standard problem-solving tool for computer vision and natural language processing tasks. One exception to this trend is safety-critical tasks where robustness and resilience requirements contradict the black-box nature of neural networks. To deploy deep learning methods for these tasks, it is vital to provide guarantees on neural network agents' safety and robustness criteria. This can be achieved by developing formal verification methods to verify the safety and robustness properties of neural networks. Our goal is to design, develop and assess safety verification methods for neural networks to improve their reliability and trustworthiness in real-world applications. This thesis establishes techniques for the verification of compressed and adversarially trained models as well as the design of novel neural networks for verifiably safe decision-making. First, we establish the problem of verifying quantized neural networks. Quantization is a technique that trades numerical precision for the computational efficiency of running a neural network and is widely adopted in industry. We show that neglecting the reduced precision when verifying a neural network can lead to wrong conclusions about the robustness and safety of the network, highlighting that novel techniques for quantized network verification are necessary. We introduce several bit-exact verification methods explicitly designed for quantized neural networks and experimentally confirm on realistic networks that the network's robustness and other formal properties are affected by the quantization. Furthermore, we perform a case study providing evidence that adversarial training, a standard technique for making neural networks more robust, has detrimental effects on the network's performance. This robustness-accuracy tradeoff has been studied before regarding the accuracy obtained on classification datasets where each data point is independent of all other data points. On the other hand, we investigate the tradeoff empirically in robot learning settings where a both, a high accuracy and a high robustness, are desirable. Our results suggest that the negative side-effects of adversarial training outweigh its robustness benefits in practice. Finally, we consider the problem of verifying safety when running a Bayesian neural network policy in a feedback loop with systems over the infinite time horizon. Bayesian neural networks are probabilistic models for learning uncertainties in the data and are therefore often used on robotic and healthcare applications where data is inherently stochastic. We introduce a method for recalibrating Bayesian neural networks so that they yield probability distributions over safe decisions only. Our method learns a safety certificate that guarantees safety over the infinite time horizon to determine which decisions are safe in every possible state of the system. We demonstrate the effectiveness of our approach on a series of reinforcement learning benchmarks.}, author = {Lechner, Mathias}, isbn = {978-3-99078-017-6}, keywords = {neural networks, verification, machine learning}, pages = {124}, publisher = {Institute of Science and Technology Austria}, title = {{Learning verifiable representations}}, doi = {10.15479/at:ista:11362}, year = {2022}, } @unpublished{11366, abstract = {Adversarial training (i.e., training on adversarially perturbed input data) is a well-studied method for making neural networks robust to potential adversarial attacks during inference. However, the improved robustness does not come for free but rather is accompanied by a decrease in overall model accuracy and performance. Recent work has shown that, in practical robot learning applications, the effects of adversarial training do not pose a fair trade-off but inflict a net loss when measured in holistic robot performance. This work revisits the robustness-accuracy trade-off in robot learning by systematically analyzing if recent advances in robust training methods and theory in conjunction with adversarial robot learning can make adversarial training suitable for real-world robot applications. We evaluate a wide variety of robot learning tasks ranging from autonomous driving in a high-fidelity environment amenable to sim-to-real deployment, to mobile robot gesture recognition. Our results demonstrate that, while these techniques make incremental improvements on the trade-off on a relative scale, the negative side-effects caused by adversarial training still outweigh the improvements by an order of magnitude. We conclude that more substantial advances in robust learning methods are necessary before they can benefit robot learning tasks in practice.}, author = {Lechner, Mathias and Amini, Alexander and Rus, Daniela and Henzinger, Thomas A}, booktitle = {arXiv}, title = {{Revisiting the adversarial robustness-accuracy tradeoff in robot learning}}, doi = {10.48550/arXiv.2204.07373}, year = {2022}, } @article{11379, abstract = {Bernal-stacked multilayer graphene is a versatile platform to explore quantum transport phenomena and interaction physics due to its exceptional tunability via electrostatic gating. For instance, upon applying a perpendicular electric field, its band structure exhibits several off-center Dirac points (so-called Dirac gullies) in each valley. Here, the formation of Dirac gullies and the interaction-induced breakdown of gully coherence is explored via magnetotransport measurements in high-quality Bernal-stacked (ABA) trilayer graphene. At zero magnetic field, multiple Lifshitz transitions indicating the formation of Dirac gullies are identified. In the quantum Hall regime, the emergence of Dirac gullies is evident as an increase in Landau level degeneracy. When tuning both electric and magnetic fields, electron–electron interactions can be controllably enhanced until, beyond critical electric and magnetic fields, the gully degeneracy is eventually lifted. The arising correlated ground state is consistent with a previously predicted nematic phase that spontaneously breaks the rotational gully symmetry.}, author = {Winterer, Felix and Seiler, Anna M. and Ghazaryan, Areg and Geisenhof, Fabian R. and Watanabe, Kenji and Taniguchi, Takashi and Serbyn, Maksym and Weitz, R. Thomas}, issn = {1530-6992}, journal = {Nano Letters}, number = {8}, pages = {3317--3322}, publisher = {American Chemical Society}, title = {{Spontaneous gully-polarized quantum hall states in ABA trilayer graphene}}, doi = {10.1021/acs.nanolett.2c00435}, volume = {22}, year = {2022}, } @article{11400, abstract = {By varying the concentration of molecules in the cytoplasm or on the membrane, cells can induce the formation of condensates and liquid droplets, similar to phase separation. Their thermodynamics, much studied, depends on the mutual interactions between microscopic constituents. Here, we focus on the kinetics and size control of 2D clusters, forming on membranes. Using molecular dynamics of patchy colloids, we model a system of two species of proteins, giving origin to specific heterotypic bonds. We find that concentrations, together with valence and bond strength, control both the size and the growth time rate of the clusters. In particular, if one species is in large excess, it gradually saturates the binding sites of the other species; the system then becomes kinetically arrested and cluster coarsening slows down or stops, thus yielding effective size selection. This phenomenology is observed both in solid and fluid clusters, which feature additional generic homotypic interactions and are reminiscent of the ones observed on biological membranes.}, author = {Palaia, Ivan and Šarić, Anđela}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, keywords = {Physical and Theoretical Chemistry, General Physics and Astronomy}, number = {19}, publisher = {AIP Publishing}, title = {{Controlling cluster size in 2D phase-separating binary mixtures with specific interactions}}, doi = {10.1063/5.0087769}, volume = {156}, year = {2022}, } @article{11401, abstract = {Tin selenide (SnSe) is considered a robust candidate for thermoelectric applications due to its very high thermoelectric figure of merit, ZT, with values of 2.6 in p-type and 2.8 in n-type single crystals. Sn has been replaced with various lower group dopants to achieve successful p-type doping in SnSe with high ZT values. A known, facile, and powerful alternative way to introduce a hole carrier is to use a natural single Sn vacancy, VSn. Through transport and scanning tunneling microscopy studies, we discovered that VSn are dominant in high-quality (slow cooling rate) SnSe single crystals, while multiple vacancies, Vmulti, are dominant in low-quality (high cooling rate) single crystals. Surprisingly, both VSn and Vmulti help to increase the power factors of SnSe, whereas samples with dominant VSn have superior thermoelectric properties in SnSe single crystals. Additionally, the observation that Vmulti are good p-type sources observed in relatively low-quality single crystals is useful in thermoelectric applications because polycrystalline SnSe can be used due to its mechanical strength; this substance is usually fabricated at very high cooling speeds.}, author = {Nguyen, Van Quang and Trinh, Thi Ly and Chang, Cheng and Zhao, Li Dong and Nguyen, Thi Huong and Duong, Van Thiet and Duong, Anh Tuan and Park, Jong Ho and Park, Sudong and Kim, Jungdae and Cho, Sunglae}, issn = {1884-4057}, journal = {NPG Asia Materials}, publisher = {Springer Nature}, title = {{Unidentified major p-type source in SnSe: Multivacancies}}, doi = {10.1038/s41427-022-00393-5}, volume = {14}, year = {2022}, } @article{11402, abstract = {Fixed-horizon planning considers a weighted graph and asks to construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping-time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary as the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping-time distribution with expected stopping-time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping-time distribution can be achieved in polynomial time.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, issn = {1090-2724}, journal = {Journal of Computer and System Sciences}, pages = {1--21}, publisher = {Elsevier}, title = {{Graph planning with expected finite horizon}}, doi = {10.1016/j.jcss.2022.04.003}, volume = {129}, year = {2022}, } @article{11403, author = {Stöllner, Andrea}, issn = {2662-138X}, journal = {Nature Reviews Earth and Environment}, number = {6}, pages = {360}, publisher = {Springer Nature}, title = {{Measuring airborne nanoplastics using aerosol physics}}, doi = {10.1038/s43017-022-00302-y}, volume = {3}, year = {2022}, } @article{11411, abstract = {Many studies have quantified the distribution of heterozygosity and relatedness in natural populations, but few have examined the demographic processes driving these patterns. In this study, we take a novel approach by studying how population structure affects both pairwise identity and the distribution of heterozygosity in a natural population of the self-incompatible plant Antirrhinum majus. Excess variance in heterozygosity between individuals is due to identity disequilibrium, which reflects the variance in inbreeding between individuals; it is measured by the statistic g2. We calculated g2 together with FST and pairwise relatedness (Fij) using 91 SNPs in 22,353 individuals collected over 11 years. We find that pairwise Fij declines rapidly over short spatial scales, and the excess variance in heterozygosity between individuals reflects significant variation in inbreeding. Additionally, we detect an excess of individuals with around half the average heterozygosity, indicating either selfing or matings between close relatives. We use 2 types of simulation to ask whether variation in heterozygosity is consistent with fine-scale spatial population structure. First, by simulating offspring using parents drawn from a range of spatial scales, we show that the known pollen dispersal kernel explains g2. Second, we simulate a 1,000-generation pedigree using the known dispersal and spatial distribution and find that the resulting g2 is consistent with that observed from the field data. In contrast, a simulated population with uniform density underestimates g2, indicating that heterogeneous density promotes identity disequilibrium. Our study shows that heterogeneous density and leptokurtic dispersal can together explain the distribution of heterozygosity.}, author = {Surendranadh, Parvathy and Arathoon, Louise S and Baskett, Carina and Field, David and Pickup, Melinda and Barton, Nicholas H}, issn = {1943-2631}, journal = {Genetics}, number = {3}, publisher = {Oxford University Press}, title = {{Effects of fine-scale population structure on the distribution of heterozygosity in a long-term study of Antirrhinum majus}}, doi = {10.1093/genetics/iyac083}, volume = {221}, year = {2022}, } @article{11417, abstract = {Over the past few years, the field of quantum information science has seen tremendous progress toward realizing large-scale quantum computers. With demonstrations of quantum computers outperforming classical computers for a select range of problems,1–3 we have finally entered the noisy, intermediate-scale quantum (NISQ) computing era. While the quantum computers of today are technological marvels, they are not yet error corrected, and it is unclear whether any system will scale beyond a few hundred logical qubits without significant changes to architecture and control schemes. Today's quantum systems are analogous to the ENIAC (Electronic Numerical Integrator And Computer) and EDVAC (Electronic Discrete Variable Automatic Computer) systems of the 1940s, which ran on vacuum tubes. These machines were built on a solid, nominally scalable architecture and when they were developed, nobody could have predicted the development of the transistor and the impact of the resulting semiconductor industry. Simply put, the computers of today are nothing like the early computers of the 1940s. We believe that the qubits of future fault-tolerant quantum systems will look quite different from the qubits of the NISQ machines in operation today. This Special Topic issue is devoted to new and emerging quantum systems with a focus on enabling technologies that can eventually lead to the quantum analog to the transistor. We have solicited both research4–18 and perspective articles19–21 to discuss new and emerging qubit systems with a focus on novel materials, encodings, and architectures. We are proud to present a collection that touches on a wide range of technologies including superconductors,7–13,21 semiconductors,15–17,19 and individual atomic qubits.18 }, author = {Sigillito, Anthony J. and Covey, Jacob P. and Fink, Johannes M and Petersson, Karl and Preble, Stefan}, issn = {0003-6951}, journal = {Applied Physics Letters}, number = {19}, publisher = {American Institute of Physics}, title = {{Emerging qubit systems: Guest editorial}}, doi = {10.1063/5.0097339}, volume = {120}, year = {2022}, } @article{11418, abstract = {We consider the quadratic form of a general high-rank deterministic matrix on the eigenvectors of an N×N Wigner matrix and prove that it has Gaussian fluctuation for each bulk eigenvector in the large N limit. The proof is a combination of the energy method for the Dyson Brownian motion inspired by Marcinek and Yau (2021) and our recent multiresolvent local laws (Comm. Math. Phys. 388 (2021) 1005–1048).}, author = {Cipolloni, Giorgio and Erdös, László and Schröder, Dominik J}, issn = {2168-894X}, journal = {Annals of Probability}, number = {3}, pages = {984--1012}, publisher = {Institute of Mathematical Statistics}, title = {{Normal fluctuation in quantum ergodicity for Wigner matrices}}, doi = {10.1214/21-AOP1552}, volume = {50}, year = {2022}, } @article{11419, abstract = {Elevation of soluble wild-type (WT) tau occurs in synaptic compartments in Alzheimer’s disease. We addressed whether tau elevation affects synaptic transmission at the calyx of Held in slices from mice brainstem. Whole-cell loading of WT human tau (h-tau) in presynaptic terminals at 10–20 µM caused microtubule (MT) assembly and activity-dependent rundown of excitatory neurotransmission. Capacitance measurements revealed that the primary target of WT h-tau is vesicle endocytosis. Blocking MT assembly using nocodazole prevented tau-induced impairments of endocytosis and neurotransmission. Immunofluorescence imaging analyses revealed that MT assembly by WT h-tau loading was associated with an increased MT-bound fraction of the endocytic protein dynamin. A synthetic dodecapeptide corresponding to dynamin 1-pleckstrin-homology domain inhibited MT-dynamin interaction and rescued tau-induced impairments of endocytosis and neurotransmission. We conclude that elevation of presynaptic WT tau induces de novo assembly of MTs, thereby sequestering free dynamins. As a result, endocytosis and subsequent vesicle replenishment are impaired, causing activity-dependent rundown of neurotransmission.}, author = {Hori, Tetsuya and Eguchi, Kohgaku and Wang, Han Ying and Miyasaka, Tomohiro and Guillaud, Laurent and Taoufiq, Zacharie and Mahapatra, Satyajit and Yamada, Hiroshi and Takei, Kohji and Takahashi, Tomoyuki}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Microtubule assembly by tau impairs endocytosis and neurotransmission via dynamin sequestration in Alzheimer's disease synapse model}}, doi = {10.7554/eLife.73542}, volume = {11}, year = {2022}, } @inproceedings{11428, abstract = {The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.}, author = {Chambers, Erin and Fillmore, Christopher D and Stephenson, Elizabeth R and Wintraecken, Mathijs}, booktitle = {38th International Symposium on Computational Geometry}, editor = {Goaoc, Xavier and Kerber, Michael}, isbn = {978-3-95977-227-3}, issn = {1868-8969}, location = {Berlin, Germany}, pages = {66:1--66:9}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{A cautionary tale: Burning the medial axis is unstable}}, doi = {10.4230/LIPIcs.SoCG.2022.66}, volume = {224}, year = {2022}, } @book{11429, abstract = {This book constitutes the refereed proceedings of the 18th International Symposium on Web and Wireless Geographical Information Systems, W2GIS 2022, held in Konstanz, Germany, in April 2022. The 7 full papers presented together with 6 short papers in the volume were carefully reviewed and selected from 16 submissions. The papers cover topics that range from mobile GIS and Location-Based Services to Spatial Information Retrieval and Wireless Sensor Networks.}, editor = {Karimipour, Farid and Storandt, Sabine}, isbn = {9783031062445}, issn = {1611-3349}, pages = {153}, publisher = {Springer Nature}, title = {{Web and Wireless Geographical Information Systems}}, doi = {10.1007/978-3-031-06245-2}, volume = {13238}, year = {2022}, } @article{11432, abstract = {This paper proposes a method for simulating liquids in large bodies of water by coupling together a water surface wave simulator with a 3D Navier-Stokes simulator. The surface wave simulation uses the equivalent sources method (ESM) to efficiently animate large bodies of water with precisely controllable wave propagation behavior. The 3D liquid simulator animates complex non-linear fluid behaviors like splashes and breaking waves using off-the-shelf simulators using FLIP or the level set method with semi-Lagrangian advection. We combine the two approaches by using the 3D solver to animate localized non-linear behaviors, and the 2D wave solver to animate larger regions with linear surface physics. We use the surface motion from the 3D solver as boundary conditions for 2D surface wave simulator, and we use the velocity and surface heights from the 2D surface wave simulator as boundary conditions for the 3D fluid simulation. We also introduce a novel technique for removing visual artifacts caused by numerical errors in 3D fluid solvers: we use experimental data to estimate the artificial dispersion caused by the 3D solver and we then carefully tune the wave speeds of the 2D solver to match it, effectively eliminating any differences in wave behavior across the boundary. To the best of our knowledge, this is the first time such a empirically driven error compensation approach has been used to remove coupling errors from a physics simulator. Our coupled simulation approach leverages the strengths of each simulation technique, animating large environments with seamless transitions between 2D and 3D physics.}, author = {Schreck, Camille and Wojtan, Christopher J}, issn = {1467-8659}, journal = {Computer Graphics Forum}, number = {2}, pages = {343--353}, publisher = {Wiley}, title = {{Coupling 3D liquid simulation with 2D wave propagation for large scale water surface animation using the equivalent sources method}}, doi = {10.1111/cgf.14478}, volume = {41}, year = {2022}, } @article{11435, abstract = {We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection of a family of convex sets to the intersection of a subfamily of a fixed size. As an application, we establish the following quantitative Helly-type result for the diameter. If $K$ is the intersection of finitely many convex bodies in $\mathbb{R}^d$, then one can select $2d$ of these bodies whose intersection is of diameter at most $(2d)^3{diam}(K)$. The best previously known estimate, due to Brazitikos [Bull. Hellenic Math. Soc., 62 (2018), pp. 19--25], is $c d^{11/2}$. Moreover, we confirm that the multiplicative factor $c d^{1/2}$ conjectured by Bárány, Katchalski, and Pach [Proc. Amer. Math. Soc., 86 (1982), pp. 109--114] cannot be improved. The bounds above follow from our key result that concerns sparse approximation of a convex polytope by the convex hull of a well-chosen subset of its vertices: Assume that $Q \subset {\mathbb R}^d$ is a polytope whose centroid is the origin. Then there exist at most 2d vertices of $Q$ whose convex hull $Q^{\prime \prime}$ satisfies $Q \subset - 8d^3 Q^{\prime \prime}.$}, author = {Ivanov, Grigory and Naszodi, Marton}, issn = {0895-4801}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, pages = {951--957}, publisher = {Society for Industrial and Applied Mathematics}, title = {{A quantitative Helly-type theorem: Containment in a homothet}}, doi = {10.1137/21M1403308}, volume = {36}, year = {2022}, } @article{11438, abstract = {Lasers with well-controlled relative frequencies are indispensable for many applications in science and technology. We present a frequency-offset locking method for lasers based on beat-frequency discrimination utilizing hybrid electronic LC filters. The method is specifically designed for decoupling the tightness of the lock from the broadness of its capture range. The presented demonstration locks two free-running diode lasers at 780 nm with a 5.5-GHz offset. It displays an offset frequency instability below 55 Hz for time scales in excess of 1000 s and a minimum of 12 Hz at 10-s averaging. The performance is complemented with a 190-MHz lock-capture range, a tuning range of up to 1 GHz, and a frequency ramp agility of 200kHz/μs.}, author = {Li, Vyacheslav and Diorico, Fritz R and Hosten, Onur}, issn = {2331-7019}, journal = {Physical Review Applied}, keywords = {General Physics and Astronomy}, number = {5}, publisher = {American Physical Society}, title = {{Laser frequency-offset locking at 10-Hz-level instability using hybrid electronic filters}}, doi = {10.1103/physrevapplied.17.054031}, volume = {17}, year = {2022}, } @inbook{11440, abstract = {To compute the persistent homology of a grayscale digital image one needs to build a simplicial or cubical complex from it. For cubical complexes, the two commonly used constructions (corresponding to direct and indirect digital adjacencies) can give different results for the same image. The two constructions are almost dual to each other, and we use this relationship to extend and modify the cubical complexes to become dual filtered cell complexes. We derive a general relationship between the persistent homology of two dual filtered cell complexes, and also establish how various modifications to a filtered complex change the persistence diagram. Applying these results to images, we derive a method to transform the persistence diagram computed using one type of cubical complex into a persistence diagram for the other construction. This means software for computing persistent homology from images can now be easily adapted to produce results for either of the two cubical complex constructions without additional low-level code implementation.}, author = {Bleile, Bea and Garin, Adélie and Heiss, Teresa and Maggs, Kelly and Robins, Vanessa}, booktitle = {Research in Computational Topology 2}, editor = {Gasparovic, Ellen and Robins, Vanessa and Turner, Katharine}, isbn = {9783030955182}, pages = {1--26}, publisher = {Springer Nature}, title = {{The persistent homology of dual digital image constructions}}, doi = {10.1007/978-3-030-95519-9_1}, volume = {30}, year = {2022}, } @article{11442, abstract = {Enabling additive manufacturing to employ a wide range of novel, functional materials can be a major boost to this technology. However, making such materials printable requires painstaking trial-and-error by an expert operator, as they typically tend to exhibit peculiar rheological or hysteresis properties. Even in the case of successfully finding the process parameters, there is no guarantee of print-to-print consistency due to material differences between batches. These challenges make closed-loop feedback an attractive option where the process parameters are adjusted on-the-fly. There are several challenges for designing an efficient controller: the deposition parameters are complex and highly coupled, artifacts occur after long time horizons, simulating the deposition is computationally costly, and learning on hardware is intractable. In this work, we demonstrate the feasibility of learning a closed-loop control policy for additive manufacturing using reinforcement learning. We show that approximate, but efficient, numerical simulation is sufficient as long as it allows learning the behavioral patterns of deposition that translate to real-world experiences. In combination with reinforcement learning, our model can be used to discover control policies that outperform baseline controllers. Furthermore, the recovered policies have a minimal sim-to-real gap. We showcase this by applying our control policy in-vivo on a single-layer, direct ink writing printer. }, author = {Piovarci, Michael and Foshey, Michael and Xu, Jie and Erps, Timothy and Babaei, Vahid and Didyk, Piotr and Rusinkiewicz, Szymon and Matusik, Wojciech and Bickel, Bernd}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Closed-loop control of direct ink writing via reinforcement learning}}, doi = {10.1145/3528223.3530144}, volume = {41}, year = {2022}, } @article{11443, abstract = {Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes. First, we prove that for a fixed dimension d, the extension complexity of a random d-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie on a circle) has extension complexity at most 24√n. This bound is tight up to the constant factor 24. Finally, we show that there exists an no(1)-dimensional polytope with at most n vertices and extension complexity n1−o(1). Our theorems are proved with a range of different techniques, which we hope will be of further interest.}, author = {Kwan, Matthew Alan and Sauermann, Lisa and Zhao, Yufei}, issn = {1088-6850}, journal = {Transactions of the American Mathematical Society}, number = {6}, pages = {4209--4250}, publisher = {American Mathematical Society}, title = {{Extension complexity of low-dimensional polytopes}}, doi = {10.1090/tran/8614}, volume = {375}, year = {2022}, }