Proof Pearl: a Formal Proof of Higman��s Lemma in ACL2

Higman??s lemma is an important result in infinitary combinatorics, which has been formalized in several theorem provers. In this paper we present a formalization and proof of Higman??s Lemma in the ACL2 theorem prover. Our formalization is based on a proof by Murthy and Russell, where the key termination argument is justified by the multiset relation induced by a well-founded relation. To our knowledge, this is the first mechanization of this proof.     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.     

Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization

Many theorems about Kolmogorov complexity rely on existence of combinatorial objects with specific properties. Usually the probabilistic method gives such objects with better parameters than explicit constructions do. But the probabilistic method does not give “effective” variants of such theorems, i.e. variants for resource-bounded Kolmogorov complexity. We show that a “naive derandomization” approach of replacing these objects by the output of Nisan-Wigderson pseudo-random generator can give polynomial-space variants of such theorems. Specifically, we improve the preceding polynomial-space analogue of Muchnik’s conditional complexity theorem. I.e., for all a and b there exists a program p of least possible length that transforms a to b and is simple conditional on b. Here all programs work in polynomial space and all complexities are measured with logarithmic accuracy instead of polylogarithmic one in the previous work.     

Algorithms of increasing the calculation accuracy for an aircraft’s orientation angle

Algorithms for calculating an aircraft’s orientation angles based on the results of the numerical integration of Poisson’s and quaternion equations are proposed. The algorithms in the presence of random errors of the matrix elements of direction cosines and quaternions are characterized by a significantly higher accuracy in comparison to the formulas for solving the formulated problem. The results of testing the mathematical modeling data under random errors, which confirm the increased accuracy of the calculation of the orientation angles, are given.     

Lower Bound on Average-Case Complexity of Inversion of Goldreich’s Function by Drunken Backtracking Algorithms

We prove an exponential lower bound on the average time of inverting Goldreich’s function by drunken backtracking algorithms; this resolves the open question stated in Cook et al. (Proceedings of TCC, pp. 521–538, 2009). The Goldreich’s function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by the fixed predicate of arity d. Our Goldreich’s function is based on an expander graph and on the nonlinear predicates that are linear in Ω(d) variables. Drunken algorithm is a backtracking algorithm that somehow chooses a variable for splitting and randomly chooses the value for the variable to be investigated at first. After the submission to the journal we found out that the same result was independently obtained by Rachel Miller.     

Optimal navigation in planar time-varying flow: Zermelo��s problem revisited

This paper is concerned with time-optimal navigation for flight vehicles in a planar, time-varying flow-field, where the objective is to find the fastest trajectory between initial and final points. The primary contribution of the paper is the observation that in a point-symmetric flow, such as inside vortices or regions of eddie-driven upwelling/downwelling, the rate of the steering angle has to be equal to one-half of the instantaneous vertical vorticity. Consequently, if the vorticity is zero, then the steering angle is constant. The result can be applied to find the time-optimal trajectories in practical control problems, by reducing the infinite-dimensional continuous problem to numerical optimization involving at most two unknown scalar parameters.     

Discrete Optimization Problems with Interval Data: Pareto Set of Solutions or Set of Weak Solutions?

For optimization problems with interval uncertainty, traditionally researchers have considered definitions based on element-wise optimality: a feasible solution is a strong solution if it optimizes the objective function f(x, c) for all possible values of the parameters c within the given intervals c, and it is a weak solution if it optimizes the objective function f(x, c) for some values cc. In our previous papers, we introduced the alternative approach based on the idea of Pareto optimality.In this paper, we analyze the relation between these two concepts of optimality, and provide arguments in favor of the Pareto approach.     

Practical protocol for Yao’s millionaires problem enables secure multi-party computation of metrics and efficient privacy-preserving k-NN for large data sets

Finding the nearest k objects to a query object is a fundamental operation for many data mining algorithms. With the recent interest in privacy, it is not surprising that there is strong interest in k-NN queries to enable clustering, classification and outlier-detection tasks. However, previous approaches to privacy-preserving k-NN have been costly and can only be realistically applied to small data sets. In this paper, we provide efficient solutions for k-NN queries for vertically partitioned data. We provide the first solution for the L _∞ (or Chessboard) metric as well as detailed privacy-preserving computation of all other Minkowski metrics. We enable privacy-preserving L _∞ by providing a practical approach to the Yao’s millionaires problem with more than two parties. This is based on a pragmatic and implementable solution to Yao’s millionaires problem with shares. We also provide privacy-preserving algorithms for combinations of local metrics into a global metric that handles the large dimensionality and diversity of attributes common in vertically partitioned data. To manage very large data sets, we provide a privacy-preserving SASH (a very successful data structure for associative queries in high dimensions). Besides providing a theoretical analysis, we illustrate the efficiency of our approach with an empirical evaluation.     

A New Methodology for the Design of Passive Biped Robots: Determining Conditions on the Robot��s Parameters for the Existence of Stable Walking Cycles

Currently, passive robots are designed following a trial and error process in which the existence of a stable walking cycle for a given passive robot??s model is analyzed using Poincaré maps. The standard stability analysis procedure suffers from discretization aliasing, and it is not able to deal with complex passive models. In this paper a methodology that allows finding conditions on the robot??s parameters of a given passive model in order to obtain a stable walking cycle is proposed. The proposed methodology overcomes the aliasing problem that arises when Poincaré sections are discretized. Basically, it implements a search process that allows finding stable subspaces in the parameters?? space (i.e., regions with parameters?? combinations that produce stable walking cycles), by simulating the robot dynamics for different parameters?? combinations. After initial conditions are randomly selected, the robot??s dynamics is modeled step by step, and in the Poincaré section the existence of a walking cycle is verified. The methodology includes the definition of a search algorithm for exploring the parameters?? space, a method for the partition of the space in hypercubes and their efficient management using proper data structures, and the use of so-called design value functions that quantify the feasibility of the resulting parameters. Among the main characteristics of the proposed methodology are being robot independent (it can be used with any passive robot model, regardless of its complexity), and robust (stable subspaces incorporate a stability margin value that deals with differences between the robot??s model and its physical realization). The methodology is validated in the design process of a complex semi-passive robot that includes trunk, knees, and non-punctual feet. The robot also considers the use of actuators, controllers and batteries for its actuation.     

A historical compilation of software metrics with applicability to NASA��s Orion spacecraft flight software sizing

Estimating the size of a large and complex software system is a challenging task. Early in a project’s life cycle, when requirements for the system may be immature and functionality defined only at a high level, resource profiles are necessary for appropriate funding, staffing, and development of a viable project plan. Similar project historical software size data and trends provide a tool to predict software size, creating a feasible estimation approach. To confidently estimate the flight software required for the Orion Spacecraft, NASA conducted an analysis of similar space and aircraft software systems. This paper presents the results of a study that compiled data from over 400 spacecraft, aircraft, and submarine software projects, which were functionally similar in nature to the Orion spacecraft flight software. The study includes the analysis and summary of overall trends in software size, development strategies, and processes. The results indicate a well-correlated upward trend in software size over time for both crewed and uncrewed space and aircraft. This trend was used to predict the estimated completed size of the Orion flight software at approximately 2.3 million Source Lines of Code (SLOC).     

The problem of electronic argument: a humanist’s perspective

This article attempts to explain the absence of a new rhetoric, as repurposed for electronic media. Such a rhetoric would provide, among other things, a blueprint for electronic arguments conducted in hypermedia form. Without an electronic rhetoric, the artifacts generated in new media inevitably fall into a narrow range: e-commerce and edutainment. One role of the humanist in this technological age, whose mother tongue is the conceptual language of the technologist, is to speak in an alternative language out of which an electronic rhetoric could emerge. The hallmark of the humanist’s alternative language or vocabulary is that it does not find technological innovation synonymous with rhetorical invention.     

In the Palm of Leonardo’s Hand: Modeling Polyhedra

George W. Hart presents three examples of new computer-based “3D printing” techniques for recreating the historically important polyhedral models of Leonardo da Vinci and Luca Pacioli. It is hoped that such models will inspire students and the public to appreciate the history and beauty of polyhedra for architectural and other applications.