More Like this

1. Parametrized Motion Planning and Topological Complexity

   https://doi.org/10.1007/978-3-031-21090-7_1  

   Farber, M; Weinberger, S (October 2023, Algorithmic Foundations of Robotics XV)

   LaValle, S.; O'Kane, J.; Otte, M.; Sadigh, D.; Tokekar, P. (Ed.)

   In this paper we study paramertized motion planning algorithms which provide universal and flexible solutions to diverse motion planning problems. Such algorithms are intended to function under a variety of external conditions which are viewed as parameters and serve as part of the input of the algorithm. Continuing the recent paper [2], we study further the concept of parametrized topological complexity. We analyse in full detail the problem of controlling a swarm of robots in the presence of multiple obstacles in Euclidean space which served for us a natural motivating example. We present an explicit parametrized motion planning algorithm solving the motion planning problem for any number of robots and obstacles in Rd. This algorithm is optimal, it has minimal possible topological complexity for any d ≥ 3 odd. Besides, we describe a modification of this algorithm which is optimal for d ≥ 2 even. We also analyse the parametrized topological complexity of sphere bundles using the Stiefel - Whitney characteristic classes. 

   more » « less
2. Optimization-based Task and Motion Planning under Signal Temporal Logic Specifications using Logic Network Flow

   Lin, Xuan; Ren, Jiming; Coogan, Samuel; Zhao, Ye (May 2025, IEEE International Conference on Robotics and Automation)

   This paper proposes an optimization-based task and motion planning framework, named “Logic Network Flow”, to integrate signal temporal logic (STL) specifications into efficient mixed-binary linear programmings. In this framework, temporal predicates are encoded as polyhedron constraints on each edge of the network flow, instead of as constraints between the nodes as in the traditional Logic Tree formulation. Synthesized with Dynamic Network Flows, Logic Network Flows render a tighter convex relaxation compared to Logic Trees derived from these STL specifications. Our formulation is evaluated on several multi-robot motion planning case studies. Empirical results demonstrate that our formulation outperforms Logic Tree formulation in terms of computation time for several planning problems. As the problem size scales up, our method still discovers better lower and upper bounds by exploring fewer number of nodes during the branch-andbound process, although this comes at the cost of increased computational load for each node when exploring branches. 

   more » « less
3. Fragile Complexity of Comparison-Based Algorithms

   https://doi.org/10.4230/LIPIcs.ESA.2019.2  

   Afshani, P.; Fagerberg, R.; Hammer, D.; Jacob, R.; Kostitsyna, I.; Meyer, U.; Penschuck, M.; Sitchinava, N. (September 2019, Proceedings of the 27th European Symposium on Algorithms)

   We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We give a number of upper and lower bounds on the fragile complexity for fundamental problems, including Minimum, Selection, Sorting and Heap Construction. The results include both deterministic and randomized upper and lower bounds, and demonstrate a separation between the two settings for a number of problems. The depth of a comparator network is a straight-forward upper bound on the worst case fragile complexity of the corresponding fragile algorithm. We prove that fragile complexity is a different and strictly easier property than the depth of comparator networks, in the sense that for some problems a fragile complexity equal to the best network depth can be achieved with less total work and that with randomization, even a lower fragile complexity is possible. 

   more » « less
4. Differentially Private Testing of Identity and Closeness of Discrete Distributions

   Acharya, Jayadev; Sun, Ziteng; Zhang, Huanyu (January 2018, Advances in Neural Information Processing Systems 31 (NIPS 2018))

   We study the fundamental problems of identity testing (goodness of fit), and closeness testing (two sample test) of distributions over k elements, under differential privacy. While the problems have a long history in statistics, finite sample bounds for these problems have only been established recently. In this work, we derive upper and lower bounds on the sample complexity of both the problems under (epsilon, delta)-differential privacy. We provide sample optimal algorithms for identity testing problem for all parameter ranges, and the first results for closeness testing. Our closeness testing bounds are optimal in the sparse regime where the number of samples is at most k. Our upper bounds are obtained by privatizing non-private estimators for these problems. The non-private estimators are chosen to have small sensitivity. We propose a general framework to establish lower bounds on the sample complexity of statistical tasks under differential privacy. We show a bound on di erentially private algorithms in terms of a coupling between the two hypothesis classes we aim to test. By carefully constructing chosen priors over the hypothesis classes, and using Le Cam’s two point theorem we provide a general mechanism for proving lower bounds. We believe that the framework can be used to obtain strong lower bounds for other statistical tasks under privacy. 

   more » « less
5. Streaming and Query Once Space Complexity of Longest Increasing Subsequence

   https://doi.org/10.1007/978-3-031-49190-0_3  

   Li, Xin; Zheng, Yu (December 2023, Lecture notes in computer science)

   Longest Increasing Subsequence (LIS) is a fundamental problem in combinatorics and computer science. Previously, there have been numerous works on both upper bounds and lower bounds of the time complexity of computing and approximating , yet only a few on the equally important space complexity. In this paper, we further study the space complexity of computing and approximating LIS in various models. Specifically, we prove non-trivial space lower bounds in the following two models: (1) the adaptive query-once model or read-once branching programs, and (2) the streaming model where the order of streaming is different from the natural order. As far as we know, there are no previous works on the space complexity of LIS in these models. Besides the bounds, our work also leaves many intriguing open problems. 

   more » « less