In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms. This was accomplished on the basis of axiomatizations of these classes of algorithms. Here we extend the axiomatization and, in a companion paper, the proof, to cover interactive small-step algorithms that are not necessarily ordinary. This means that the algorithms (1) can complete a step without necessarily waiting for replies to all queries from that step and (2) can use not only the environment's replies but also the order in which the replies were received.
The of @cite_27 extends Bounded Exploration of @cite_12 to queries. As a consequence every well-founded answer function is finite. Furthermore, there is a uniform bound on the size of well-founded answer functions.
@cite_27 @cite_12
48624319 1840129892 2034079307 1484905448
Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes of set functions can be sketched. More formally, let f be a function mapping subsets of some ground set [n] to the non-negative real numbers. We say that f' is an α-sketch of f if for every set S, the value f'(S) lies between f(S) α and f(S), and f' can be specified by poly(n) bits. We show that for every subadditive function f there exists an α-sketch where α = n1 2. O(polylog(n)). Furthermore, we provide an algorithm that finds these sketches with a polynomial number of demand queries. This is essentially the best we can hope for since: 1. We show that there exist subadditive functions (in fact, XOS functions) that do not admit an o(n1 2) sketch. (Balcan and Harvey [3] previously showed that there exist functions belonging to the class of substitutes valuations that do not admit an O(n1 3) sketch.) 2. We prove that every deterministic algorithm that accesses the function via value queries only cannot guarantee a sketching ratio better than n1−e. We also show that coverage functions, an interesting subclass of submodular functions, admit arbitrarily good sketches. Finally, we show an interesting connection between sketching and learning. We show that for every class of valuations, if the class admits an α-sketch, then it can be α-approximately learned in the PMAC model of Balcan and Harvey. The bounds we prove are only information-theoretic and do not imply the existence of computationally efficient learning algorithms in general. Bounded increase is a termination technique where it is tried to find an argument x of a recursive function that is increased repeatedly until it reaches a bound b, which might be ensured by a condition x<b. Since the predicates like < may be arbitrary user-defined recursive functions, an induction calculus is utilized to prove conditional constraints. In this paper, we present a full formalization of bounded increase in the theorem prover Isabelle HOL. It fills one large gap in the pen-and-paper proof, and it includes generalized inference rules for the induction calculus as well as variants of the Babylonian algorithm to compute square roots. These algorithms were required to write executable functions which can certify untrusted termination proofs from termination tools that make use of bounded increase. And indeed, the resulting certifier was already useful: it detected an implementation error that remained undetected since 2007. Let ( A ) be finite relational structure of finite type, and let CSP ( ( A) ) denote the following decision problem: if ( I ) is a given structure of the same type as ( A ) , is there a homomorphism from ( I ) to ( A )? To each relational structure ( A ) is associated naturally an algebra ( A ) whose structure determines the complexity of the associated decision problem. We investigate those finite algebras arising from CSP’s of so-called bounded width, i.e., for which local consistency algorithms effectively decide the problem. We show that if a CSP has bounded width then the variety generated by the associated algebra omits the Hobby-McKenzie types 1 and 2. This provides a method to prove that certain CSP’s do not have bounded width. We give several applications, answering a question of Nesetřil and Zhu [26], by showing that various graph homomorphism problems do not have bounded width. Feder and Vardi [17] have shown that every CSP is polynomial-time equivalent to the retraction problem for a poset we call the Feder − Vardi poset of the structure. We show that, in the case where the structure has a single relation, if the retraction problem for the Feder-Vardi poset has bounded width then the CSP for the structure also has bounded width. This is used to exhibit a finite order-primal algebra whose variety admits type 2 but omits type 1 (provided P ≠ NP). We investigate the following problem: Given a list of n items and a function defined over lists of these items, generate a bounded amount of auxiliary information such that range queries asking for the value of the function on sub-lists can be answered within a certain time bound. For the function "mode" we improve the previously known time bound O(nƐ log n) to O(nƐ) with space O(n2-2Ɛ), where 0 ≤ Ɛ < 1 2. We improve the space bound O(n2 log log n log n) for an O(1) time bounded solution to O(n2 log n). For the function "median" the space bound O(n2 log log n log n) is improved to O(n2 log(k) n log n) for an O(1) time solution, where k is an arbitrary constant and log(k) is the iterated logarithm.