More Like this

1. Rigid foldability is NP-hard

   Akitaya, Hugo A ; Demaine, Erik D ; Horiyama, Takashi ; Hull, Thomas C ; Ku, Jason S ; Tachi, Tomohiro ( January 2020 , Journal of computational geometry)

   null (Ed.)

   In this paper, we show that the rigid-foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from the partition problem, and that rigid-foldability with optional creases is NP-hard by a reduction from the 1-in-3 SAT problem. Unlike flat-foldabilty of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible self-intersection of the material, rigid foldabilltiy from a planar state is hard even though there is no potential self-intersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing folding-based systems such as self-folding matters and reconfigurable robots. 

   more » « less
2. Rigid folding equations of degree-6 origami vertices

   https://doi.org/10.1098/rspa.2022.0051  

   Farnham, Johnna ; Hull, Thomas C. ; Rumbolt, Aubrey ( April 2022 , Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences)

   Rigid origami, with applications ranging from nano-robots to unfolding solar sails in space, describes when a material is folded along straight crease line segments while keeping the regions between the creases planar. Prior work has found explicit equations for the folding angles of a flat-foldable degree-4 origami vertex and some cases of degree-6 vertices. We extend this work to generalized symmetries of the degree-6 vertex where all sector angles equal 60 ∘ . We enumerate the different viable rigid folding modes of these degree-6 crease patterns and then use second-order Taylor expansions and prior rigid folding techniques to find algebraic folding angle relationships between the creases. This allows us to explicitly compute the configuration space of these degree-6 vertices, and in the process we uncover new explanations for the effectiveness of Weierstrass substitutions in modelling rigid origami. These results expand the toolbox of rigid origami mechanisms that engineers and materials scientists may use in origami-inspired designs. 

   more » « less
3. The Power of Shared Randomness in Uncertain Communication

   Ghazi, B. ; Sudan, M. ( July 2017 , 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017))

   In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function f and an input string x, and Bob is given a function g and an input string y. The pair (x,y) comes from a known distribution mu and f and g are guaranteed to be close under this distribution. Alice and Bob wish to compute g(x,y) with high probability. The lack of agreement between Alice and Bob on the function that is being computed captures the uncertainty in the context. The previous work showed that any problem with one-way communication complexity k in the standard model (i.e., without uncertainty, in other words, under the promise that f=g) has public-coin communication at most O(k(1+I)) bits in the uncertain case, where I is the mutual information between x and y. Moreover, a lower bound of Omega(sqrt{I}) bits on the public-coin uncertain communication was also shown. However, an important question that was left open is related to the power that public randomness brings to uncertain communication. Can Alice and Bob achieve efficient communication amid uncertainty without using public randomness? And how powerful are public-coin protocols in overcoming uncertainty? Motivated by these two questions: - We prove the first separation between private-coin uncertain communication and public-coin uncertain communication. Namely, we exhibit a function class for which the communication in the standard model and the public-coin uncertain communication are O(1) while the private-coin uncertain communication is a growing function of n (the length of the inputs). This lower bound (proved with respect to the uniform distribution) is in sharp contrast with the case of public-coin uncertain communication which was shown by the previous work to be within a constant factor from the certain communication. This lower bound also implies the first separation between public-coin uncertain communication and deterministic uncertain communication. Interestingly, we also show that if Alice and Bob imperfectly share a sequence of random bits (a setup weaker than public randomness), then achieving a constant blow-up in communication is still possible. - We improve the lower-bound of the previous work on public-coin uncertain communication. Namely, we exhibit a function class and a distribution (with mutual information I approx n) for which the one-way certain communication is k bits but the one-way public-coin uncertain communication is at least Omega(sqrt{k}*sqrt{I}) bits. Our proofs introduce new problems in the standard communication complexity model and prove lower bounds for these problems. Both the problems and the lower bound techniques may be of general interest. 

   more » « less
4. Origami/Kirigami‐Guided Morphing of Composite Sheets

   https://doi.org/10.1002/adfm.201802768  

   Cui, Jianxun ; Poblete, Felipe R. ; Zhu, Yong ( August 2018 , Advanced Functional Materials)

   Several strategies are recently exploited to transform 2D sheets into desired 3D structures. For example, soft materials can be morphed into 3D continuously curved structures by inducing nonhomogeneous strain. On the other hand, rigid materials can be folded, often by origami/kirigami‐inspired approaches (i.e., flat sheets are folded along predesigned crease patterns). Here, for the first time, combining the two strategies, composite sheets are fabricated by embedding rigid origami/kirigami skeleton with creases into heat shrinkable polymer sheets to create novel 3D structures. Upon heating, shrinkage of the polymer sheets is constrained by the origami/kirigami patterns, giving rise to laterally nonuniform strain. As a result, Gaussian curvature of the composite sheets is changed, and flat sheets are transformed into 3D curved structures. A series of 3D structures are folded using this approach, including cones and truncated pyramids with different base shapes. Flat origami loops are folded into step structures. Tessellation of origami loops is transformed into 3D checkerboard pattern.

    

   more » « less
5. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow

   https://doi.org/10.1137/1.9781611977073.64  

   Chekuri, Chandra ; Quanrud, Kent ; Torres, Manuel ( January 2022 , Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms)

   The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a non-negative supermodular function $f: 2^V \rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$. For \dsg we describe a simple flow-based algorithm that outputs a $(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time where $m$ is the number of edges. Our algorithm is the first to have a near-linear dependence on $m$ and $1/\eps$ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed \dsg. Greedy peeling algorithms have been very popular for \dsg and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for \dssp and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al.\ \cite{bgpstww-20} developed an \emph{iterative} peeling algorithm for \dsg which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a $(1-\eps)$-approximation for \emph{any} supermodular function $f$; the key to our proof is to consider an LP formulation that is derived via the \Lovasz extension of a supermodular function. For \dsg the bound on the number of iterations we prove is $O(\frac{\Delta \ln |V|}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is the maximum degree and $\lambda^*$ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the $2$-approximation for densest-at-least-$k$ subgraph \cite{ks-09} extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of \dssp to maximize $f(S)/g(|S|)$ for a concave function $g$. 

   more » « less