We describe an error in earlier probabilistic analyses of the pure literal heuristic as a procedure for solving the satisfiability problem for sets of k-clauses (k-SAT). All probabilistic analyses are in the constant ...
详细信息
We describe an error in earlier probabilistic analyses of the pure literal heuristic as a procedure for solving the satisfiability problem for sets of k-clauses (k-SAT). All probabilistic analyses are in the constant degree model in which a random instance C of k-SAT consists of m clauses selected independently and uniformly (with replacement) from the set of all k-clauses over n variables. We provide a new analysis for k = 2. Specifically, we show with probability approaching 1 as m goes to ∞ one can apply the pure literal rule repeatedly to a random instance of 2-SAT until the number of clauses is `small' provided n/m≥λ>1. But if n/m&leλΕ clauses will remain.
In this paper; we show how to extend the argument due to Bonet, Pitassi and Raz to show that bounded-depth Frege proofs do not have feasible interpolation, assuming that factoring of Blum integers or computing the Dif...
详细信息
In this paper; we show how to extend the argument due to Bonet, Pitassi and Raz to show that bounded-depth Frege proofs do not have feasible interpolation, assuming that factoring of Blum integers or computing the Diffie-Hellman function is sufficiently hard. It follows as a corollary that bounded-depth Frege is not automatizable; in other words, there is no deterministic polynomial-time algorithm that will output a short proof if one exists. A notable feature of our argument is its simplicity.
In this article, we discuss the application, of a Green's function approach to contact maps. We apply the contact map algorithm to the case of an elastic bar impacting on a massive foundation. It is demonstrated t...
详细信息
In this article, we discuss the application, of a Green's function approach to contact maps. We apply the contact map algorithm to the case of an elastic bar impacting on a massive foundation. It is demonstrated that the energy lost to elastic waves is an important factor in post-contact states.
Self-recovery micro-rollback synthesis (SMS) has currently become an important issue in high level synthesis. The problem of SMS combines the problem of functional unit scheduling and assignment with the problem of ch...
详细信息
Self-recovery micro-rollback synthesis (SMS) has currently become an important issue in high level synthesis. The problem of SMS combines the problem of functional unit scheduling and assignment with the problem of checkpoint insertion and microprogram optimization. It has been shown that these problems are NP-complete. The most studied problem is functional unit scheduling and assignment. Several heuristic techniques, including as soon as possible (ASAP), as last as possible (ALAP), integer programming, spring elasticity model, graph based mobility model, and genetic algorithm, are proposed. However, there are few studies on self-recovery micro-rollback synthesis and the technique of solution space searching by genetic algorithm has not been attempted. We study the feasibility of the genetic algorithm for the problem of SMS constrained on: the number of functional units, control steps, number of checkpoints, and the functional unit areas.
The paper presents a new approach for shape recovery based on integrating geometric and photometric information. We consider 3D objects which are symmetric with respect to a plane (e.g., faces) and their reconstructio...
详细信息
The paper presents a new approach for shape recovery based on integrating geometric and photometric information. We consider 3D objects which are symmetric with respect to a plane (e.g., faces) and their reconstruction from a single image. Both the viewpoint and the illumination are not necessarily frontal. In principle, no correspondence between symmetric points is required, but knowledge about a few corresponding pairs accelerates the process. The basic idea is that an image taken from a general, non-frontal viewpoint, under non-frontal illumination can be regarded as a pair of images of half of the object, taken from two different viewing positions and two different lighting directions. We show that integrating the photometric and geometric information yields the unknown lighting and viewing parameters, as well as dense correspondence between pairs of symmetric points. As a result, a dense shape recovery of the object is computed. The method has been implemented and tested experimentally on simulated and real data.
We provide rigorous time/space trade-offs for inverting any function. Given a function f, we give a time/space trade-off of TS2 = N3q(f), where q(f) is the probability that two random elements (taken with replacement)...
详细信息
We provide rigorous time/space trade-offs for inverting any function. Given a function f, we give a time/space trade-off of TS2 = N3q(f), where q(f) is the probability that two random elements (taken with replacement) are mapped to the same image under f. We also give a more general trade-off, T S3 = N3, that can invert any function at any point.
In a previous paper (1998) we presented a method for image-based navigation by which a robot can navigate to desired positions and orientations in 3D space specified by single images taken from these positions. In thi...
详细信息
In a previous paper (1998) we presented a method for image-based navigation by which a robot can navigate to desired positions and orientations in 3D space specified by single images taken from these positions. In this paper we further investigate the method and develop robust algorithms for navigation assuming the perspective projection model. In particular, we develop a tracking algorithm that exploits our knowledge of the motion performed by the robot at every step. This algorithm allows us to maintain correspondences between frames and eliminate false correspondences. We combine this tracking algorithm with an iterative optimization procedure to accurately recover the displacement of the robot from the target. Our method for navigation is attractive since it does not require a 3D model of the environment. We demonstrate the robustness of our method by applying it to a six degree of freedom robot arm.
We present a framework integrating specification and scheduler generation for real time systems. In a first step, the system, which can include arbitrarily designed tasks (cyclic or sporadic, with or without precedenc...
详细信息
We present a framework integrating specification and scheduler generation for real time systems. In a first step, the system, which can include arbitrarily designed tasks (cyclic or sporadic, with or without precedence constraints, any number of resources and CPUs) is specified as a timed Petri net. In a second step, our tool generates the most general non preemptive online scheduler for the specification, using a controller synthesis technique.
暂无评论