We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and probabilistically checkable proofs of proximity. Namely, we show that the structure of ...
详细信息
We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and probabilistically checkable proofs of proximity. Namely, we show that the structure of every algorithm that makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with n(1-1/O(q2 log 2 q)) sample complexity, following the definition of Goldreich and Ron [ACM Trans. Comput. Theory, 8 (2016), 7]. We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacypreserving local algorithms. Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following. We strengthen the stateof-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity;this resolves an open problem raised by Gur and Lachish [SIAM J. Comput., 50 (2021), pp. 788-813]. We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity;this resolves a problem left open in a work of Fischer, Lachish, and Vasudev [Proceedings of the 56th Annual Symposium on Foundations of Computer Science, IEEE, 2015, pp. 1163-1182], bypassing an exponential blowup caused by previous techniques in the case of adaptive testers. We prove that the known separation between proofs of proximity and testers is essentially maximal;this resolves a problem left open by Gur and Rothblum [Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017, pp. 39:1-39:43;Comput. Complexity, 27 (2018), pp. 99-207] regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal-Szemeredi theorem.
In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as reward. We evaluate a stopping ...
详细信息
ISBN:
(纸本)9798400703836
In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. In the classic setting, the order is fixed, and the optimal ratio is known to be 1/2. Three variants of this problem have been extensively studied: the prophet-secretary model, where variables arrive in uniformly random order;the free-order model, where the gambler chooses the arrival order;and the i.i.d. model, where the distributions are all the same, rendering the arrival order irrelevant. Most of the literature assumes that distributions are known to the gambler. Recent work has considered the question of what is achievable when the gambler has access only to a few samples per distribution. Surprisingly, in the fixed-order case, a single sample from each distribution is enough to approximate the optimal ratio, but this is not the case in any of the three variants. We provide a unified proof that for all three variants of the problem, a constant number of samples (independent of n) for each distribution is good enough to approximate the optimal ratios. Prior to our work, this was known to be the case only in the i.i.d. variant. Previous works relied on explicitly constructing sample-based algorithms that match the best possible ratio. Remarkably, the optimal ratios for the prophet-secretary and the free-order variants with full information are still unknown. Consequently, our result requires a significantly different approach than for the classic problem and the i.i.d. variant, where the optimal ratios and the algorithms that achieve them are known. We complement our result showing that our algorithms can be implemented in polynomial time. A key ingredient in our proof is an existential result based on a minimax argument, which states that there must
Finding a path in a narrow passage is a bottleneck for randomised sampling-based motion planning methods. This paper introduces a technique that solves this problem. The main inspiration was the method of exit areas f...
详细信息
ISBN:
(纸本)9783031087516;9783031087509
Finding a path in a narrow passage is a bottleneck for randomised sampling-based motion planning methods. This paper introduces a technique that solves this problem. The main inspiration was the method of exit areas for cavities in protein models, but the proposed solution can also be used in another context. For data with narrow passages, the proposed method finds passageways for which sampling-based methods are not sufficient, or provides information that a collision-free path does not exist. With such information, it is possible to quit the motion planning computation if no solution exists and its further search would be a loss of time. Otherwise, the method continues to sample the space with sampling-based method (a RRT algorithm) until a solution is found or the maximum number of iterations is reached. The method was tested on real biomolecular data - dcp protein - and on artificial data (to show the superiority of the proposed solution on better-imagined data) with positive results.
Rapidly exploring random trees (RRTs) have proven effective in quickly finding feasible solutions to complex motion planning problems. RRT* is an extension of the RRT algorithm that provides probabilistic asymptotic o...
详细信息
Rapidly exploring random trees (RRTs) have proven effective in quickly finding feasible solutions to complex motion planning problems. RRT* is an extension of the RRT algorithm that provides probabilistic asymptotic optimality guarantees when using straight-line motion primitives. This work provides extensions to RRT and RRT* that employ fillets as motion primitives, allowing path curvature constraints to be considered when planning. Two fillets are developed, an arc-based fillet that uses circular arcs to generate paths that respect maximum curvature constraints and a spline-based fillet that uses Bezier curves to additionally respect curvature continuity requirements. Planning with these fillets is shown to far exceed the performance of RRT* using Dubin's path motion primitives, approaching the performance of planning with straight-line path primitives. Path sampling heuristics are also introduced to accelerate convergence for nonholonomic motion planning. Comparisons to established RRT* approaches are made using the Open Motion Planning Library (OMPL).
暂无评论