More Like this

1. Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond

   Balcan, M.-F.; Prasad, S.; Sandholm, T.; Vitercik, E. (January 2021, ArXivorg)

   null (Ed.)

   Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree-search algorithm used to find optimal solutions. In this paper we prove the first guarantees for learning high-performing cut-selection policies tailored to the instance distribution at hand using samples. We first bound the sample complexity of learning cutting planes from the canonical family of Chvátal-Gomory cuts. Our bounds handle any number of waves of any number of cuts and are fine tuned to the magnitudes of the constraint coefficients. Next, we prove sample complexity bounds for more sophisticated cut selection policies that use a combination of scoring rules to choose from a family of cuts. Finally, beyond the realm of cutting planes for integer programming, we develop a general abstraction of tree search that captures key components such as node selection and variable selection. For this abstraction, we bound the sample complexity of learning a good policy for building the search tree. 

   more » « less
2. Surface ionization waves propagating over non-planar substrates: wavy surfaces, cut-pores and droplets

   https://doi.org/10.1088/1361-6595/ac9a6c  

   Konina, Kseniia; Kruszelnicki, Juliusz; Meyer, Mackenzie E; Kushner, Mark J (November 2022, Plasma Sources Science and Technology)

   Abstract Atmospheric pressure plasmas intersecting with dielectric surfaces will often transition into surface ionization waves (SIWs). Several applications of these discharges are purposely configured to be SIWs. During propagation of an SIW over a dielectric surface, the plasma charges the surface while responding to changes in geometrical and electrical material properties. This is particularly important for non-planar surfaces where polarization of the dielectric results in local electric field enhancement. In this paper, we discuss results from computational investigations of negative and positive SIWs propagating over nonplanar dielectrics in three configurations—wavy surfaces, cuts through porous materials and water droplets on flat surfaces. We found that negative SIWs are particularly sensitive to the electric field enhancement that occurs at the crests of non-planar surfaces. The local increase in ionization rates by the electric field enhancement can result in the SIW detaching from the surface, which produces non-uniform plasma exposure of the surface. Positive SIWs tend to adhere to the surface to a greater degree. These trends indicate that treatment of pathogen containing droplets on surfaces may be best performed by positive SIWs. The same principles apply to the surfaces cut through pores. Buried pores with small openings to the SIW may be filled by plasma by either flow of plasma into the pore (large opening) or initiated by photoionization (small opening), depending on the size of the opening compared to the Debye length. 

   more » « less
3. Flows, growth rates, and the veering polynomial

   https://doi.org/10.1017/etds.2022.63  

   LANDRY, MICHAEL P.; MINSKY, YAIR N.; TAYLOR, SAMUEL J. (January 2022, Ergodic Theory and Dynamical Systems)

   Abstract For a pseudo-Anosov flow $$\varphi $$ without perfect fits on a closed $$3$$ -manifold, Agol–Guéritaud produce a veering triangulation $$\tau $$ on the manifold M obtained by deleting the singular orbits of $$\varphi $$ . We show that $$\tau $$ can be realized in M so that its 2-skeleton is positively transverse to $$\varphi $$ , and that the combinatorially defined flow graph $$\Phi $$ embedded in M uniformly codes the orbits of $$\varphi $$ in a precise sense. Together with these facts, we use a modified version of the veering polynomial, previously introduced by the authors, to compute the growth rates of the closed orbits of $$\varphi $$ after cutting M along certain transverse surfaces, thereby generalizing the work of McMullen in the fibered setting. These results are new even in the case where the transverse surface represents a class in the boundary of a fibered cone of M . Our work can be used to study the flow $$\varphi $$ on the original closed manifold. Applications include counting growth rates of closed orbits after cutting along closed transverse surfaces, defining a continuous, convex entropy function on the ‘positive’ cone in $H^1$ of the cut-open manifold, and answering a question of Leininger about the closure of the set of all stretch factors arising as monodromies within a single fibered cone of a $$3$$ -manifold. This last application connects to the study of endperiodic automorphisms of infinite-type surfaces and the growth rates of their periodic points. 

   more » « less
4. Programmable active kirigami metasheets with more freedom of actuation

   https://doi.org/10.1073/pnas.1906435116  

   Tang, Yichao; Li, Yanbin; Hong, Yaoye; Yang, Shu; Yin, Jie (December 2019, Proceedings of the National Academy of Sciences)

   Kirigami (cutting and/or folding) offers a promising strategy to reconfigure metamaterials. Conventionally, kirigami metamaterials are often composed of passive cut unit cells to be reconfigured under mechanical forces. The constituent stimuli-responsive materials in active kirigami metamaterials instead will enable potential mechanical properties and functionality, arising from the active control of cut unit cells. However, the planar features of hinges in conventional kirigami structures significantly constrain the degrees of freedom (DOFs) in both deformation and actuation of the cut units. To release both constraints, here, we demonstrate a universal design of implementing folds to reconstruct sole-cuts–based metamaterials. We show that the supplemented folds not only enrich the structural reconfiguration beyond sole cuts but also enable more DOFs in actuating the kirigami metasheets into 3 dimensions (3D) in response to environmental temperature. Utilizing the multi-DOF in deformation of unit cells, we demonstrate that planar metasheets with the same cut design can self-fold into programmable 3D kirigami metastructures with distinct mechanical properties. Last, we demonstrate potential applications of programmable kirigami machines and easy-turning soft robots. 

   more » « less
5. Winding Numbers on Discrete Surfaces

   https://doi.org/10.1145/3592401  

   Feng, Nicole; Gillespie, Mark; Crane, Keenan (July 2023, ACM Transactions on Graphics)

   In the plane, thewinding numberis the number of times a curve wraps around a given point. Winding numbers are a basic component of geometric algorithms such as point-in-polygon tests, and their generalization to data with noise or topological errors has proven valuable for geometry processing tasks ranging from surface reconstruction to mesh booleans. However, standard definitions do not immediately apply on surfaces, where not all curves bound regions. We develop a meaningful generalization, starting with the well-known relationship between winding numbers and harmonic functions. By processing the derivatives of such functions, we can robustly filter out components of the input that do not bound any region. Ultimately, our algorithm yields (i) a closed, completed version of the input curves, (ii) integer labels for regions that are meaningfully bounded by these curves, and (iii) the complementary curves that do not bound any region. The main computational cost is solving a standard Poisson equation, or for surfaces with nontrivial topology, a sparse linear program. We also introduce special basis functions to represent singularities that naturally occur at endpoints of open curves. 

   more » « less