We offer a short tour into the interactive interpretation of sequential programs. We emphasize streamlike computation — that is, computation of successive bits of information upon request. The core of the approach surveyed here dates back to the work of Berry and the author on sequential algorithms on concrete data structures in the late seventies, culminating in the design of the programming language CDS, in which the semantics of programs of any type can be explored interactively. Around one decade later, two major insights of Cartwright and Felleisen on one hand, and of Lamarche on the other hand gave new, decisive impulses to the study of sequentiality. Cartwright and Felleisen observed that sequential algorithms give a direct semantics to control operators like call-cc and proposed to include explicit errors both in the syntax and in the semantics of the language PCF. Lamarche (unpublished) connected sequential algorithms to linear logic and games. The successful program of games semantics has spanned over the nineties until now, starting with syntax-independent characterizations of the term model of PCF by Abramsky, Jagadeesan, and Malacaria on one hand, and by Hyland and Ong on the other hand.
Two important models of functions that have been constructed since turned out to be the extensional collapse (i.e. the hereditary quotient equating sequential algorithms computing the same function, i.e. (in the affine case) two algorithms @math and @math such that @math ): Bucciarelli and Ehrhard's model of strongly stable functions @cite_3 @cite_16 , and Longley's model of sequentially realizable functionals @cite_10 . The first model arose from an algebraic characterization of sequential (first-order) functions, that carries over to all types. The second one is a realizability model over a combinatory algebra in which the interaction at work in sequential algorithms is encoded.
@cite_16 @cite_10 @cite_3
2038883640 1985955425 1963626918
In the previous chapter, we saw how the model PC offers a ‘maximal’ class of partial computable functionals strictly extending SF (in the sense of the poset ( J ( N _ ) ) of Subsection 3.6.4). In the present chapter, we show that SF can also be extended in a very different direction to yield another class SR of ‘computable’ functionals which is in some sense incompatible with PC. This class was first identified by Bucciarelli and Ehrhard [45] as the class of strongly stable functionals; later work by Ehrhard [69], van Oosten [294] and Longley [176] established the computational significance of these functionals, investigated their theory in some detail, and provided a range of alternative characterizations. We prove that, in the hierarchy of simple types based on the type of natural numbers, any finite strongly stable function is equal to the application of the semantics of a PCF-definable functional to some strongly stable (generally not PCF-definable) functionals of type two. Applying a logical relation technique, we derive from this result that the strongly stable model of PCF is the extensional collapse of its sequential algorithms model. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of @math -colorings or the number of independent sets of a graph and also the partition functions of certain “spin glass” models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill [Random Structures Algorithms, 17 (2000), pp. 260-289] and Bulatov and Grohe [Theoret. Comput. Sci., 348 (2005), pp. 148-186], we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by Hadamard matrices (these turn out to be central in our proofs) we obtain a simple algebraic tractability criterion, which says that the tractable cases are those “representable” by a quadratic polynomial over the field @math . Accurate reconstruction of piecewise-smooth functions from a finite number of Fourier coefficients is an important problem in various applications. The inherent inaccuracy, in particular the Gibbs phenomenon, is being intensively investigated during the last decades. Several nonlinear reconstruction methods have been proposed, and it is by now well-established that the "classical" convergence order can be completely restored up to the discontinuities. Still, the maximal accuracy of determining the positions of these discontinuities remains an open question. In this paper we prove that the locations of the jumps (and subsequently the pointwise values of the function) can be reconstructed with at least "half the classical accuracy". In particular, we develop a constructive approximation procedure which, given the first @math Fourier coefficients of a piecewise- @math function, recovers the locations of the jumps with accuracy @math , and the values of the function between the jumps with accuracy @math (similar estimates are obtained for the associated jump magnitudes). A key ingredient of the algorithm is to start with the case of a single discontinuity, where a modified version of one of the existing algebraic methods (due to K.Eckhoff) may be applied. It turns out that the additional orders of smoothness produce a highly correlated error terms in the Fourier coefficients, which eventually cancel out in the corresponding algebraic equations. To handle more than one jump, we propose to apply a localization procedure via a convolution in the Fourier domain. We present a cartesian closed category of dI-domains with coherence and strongly stable functions which provides a new model of PCF, where terms are interpreted by functions and where, at first order, all functions are sequential. We show how this model can be refined in such a way that the theory it induces on the terms of PCF be strictly finer than the theory induced by the Scott model of continuous functions. Abstract Irregular sampling and “stable sampling” of band-limited functions have been studied by H.J. Landau [H.J. Landau, Necessary density conditions for sampling and interpolation of certain entire functions, Acta Math. 117 (1967) 37–52]. We prove that quasicrystals are sets of stable sampling. To cite this article: B. Matei, Y. Meyer, C. R. Acad. Sci. Paris, Ser. I 346 (2008). An algorithm for solving the problem: minimize @math (a convex function) subject to @math , @math , each @math a concave function, is presented. Specifically, the function [ P [ x,t,r_k ] f( x ) + r_k^ - 1 [ g_i ( x ) - t_i ] ^2 ] is minimized over all x, nonnegative t, for a strictly decreasing null sequence @math . This extends the work of T. Pietrzykowski [5]. It is proved that for every @math , there exists a finite point @math which minimizes P, and which solves the convex programming problem as @math . This algorithm is similar to the Sequential Unconstrained Minimization Technique (SUMT) [1] in that it solves the (Wolfe) dual programming problem [6]. It differs from SUMT in that (1) it approaches the optimum from the region of infeasibility (i.e., it is a relaxation technique), (2) it does not require a nonempty interior to the nonlinearly constrained region, (3) no separate feasibilit... This paper addresses the problem of minimizing a convex, Lipschitz function @math over a convex, compact set @math under a stochastic bandit (i.e., noisy zeroth-order) feedback model. In this model, the algorithm is allowed to observe noisy realizations of the function value @math at any query point @math . The quantity of interest is the regret of the algorithm, which is the sum of the function values at algorithm's query points minus the optimal function value. We demonstrate a generalization of the ellipsoid algorithm that incurs @math regret. Since any algorithm has regret at least @math on this problem, our algorithm is optimal in terms of the scaling with @math . A central theme in distributed network algorithms concerns understanding and coping with the issue of locality . Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for . In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard @math model of computation and define @math (for local decision ) as the class of decision problems that can be solved in @math communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class @math , containing all languages for which there exists a randomized algorithm that runs in @math rounds, accepts correct instances with probability at least @math and rejects incorrect ones with probability at least @math . We show that @math is a threshold for the containment of @math in @math . More precisely, we show that there exists a language that does not belong to @math for any @math but does belong to @math for any @math such that @math . On the other hand, we show that, restricted to hereditary languages, @math , for any function @math and any @math such that @math . In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide languages . Finally, we introduce the notion of local reduction, and establish some completeness results. The amoeba of a holomorphic function @math is, by definition, the image in @math of the zero locus of @math under the simple mapping that takes each coordinate to the logarithm of its modulus. The terminology was introduced in the 1990s by the famous (biologist and) mathematician Israel Gelfand and his coauthors Kapranov and Zelevinsky (GKZ). In this paper we study a natural convex potential function @math with the property that its Monge-Ampere mass is concentrated to the amoeba of @math We obtain results of two kinds; by approximating @math with a piecewise linear function, we get striking combinatorial information regarding the amoeba and the Newton polytope of @math ; by computing the Monge-Ampere measure, we find sharp bounds for the area of amoebas in @math . We also consider systems of functions @math and prove a local version of the classical Bernstein theorem on the number of roots of systems of algebraic equations. As computational challenges in optimization and statistical inference grow ever harder, algorithms that utilize derivatives are becoming increasingly more important. The implementation of the derivatives that make these algorithms so powerful, however, is a substantial user burden and the practicality of these algorithms depends critically on tools like automatic differentiation that remove the implementation burden entirely. The Stan Math Library is a C++, reverse-mode automatic differentiation library designed to be usable, extensive and extensible, efficient, scalable, stable, portable, and redistributable in order to facilitate the construction and utilization of such algorithms. Usability is achieved through a simple direct interface and a cleanly abstracted functional interface. The extensive built-in library includes functions for matrix operations, linear algebra, differential equation solving, and most common probability functions. Extensibility derives from a straightforward object-oriented framework for expressions, allowing users to easily create custom functions. Efficiency is achieved through a combination of custom memory management, subexpression caching, traits-based metaprogramming, and expression templates. Partial derivatives for compound functions are evaluated lazily for improved scalability. Stability is achieved by taking care with arithmetic precision in algebraic expressions and providing stable, compound functions where possible. For portability, the library is standards-compliant C++ (03) and has been tested for all major compilers for Windows, Mac OS X, and Linux. This paper presents an analysis of spinal codes, a class of rateless codes proposed recently. We prove that spinal codes achieve Shannon capacity for the binary symmetric channel (BSC) and the additive white Gaussian noise (AWGN) channel with an efficient polynomial-time encoder and decoder. They are the first rateless codes with proofs of these properties for BSC and AWGN. The key idea in the spinal code is the sequential application of a hash function over the message bits. The sequential structure of the code turns out to be crucial for efficient decoding. Moreover, counter to the wisdom of having an expander structure in good codes, we show that the spinal code, despite its sequential structure, achieves capacity. The pseudo-randomness provided by a hash function suffices for this purpose. Our proof introduces a variant of Gallager's result characterizing the error exponent of random codes for any memoryless channel. We present a novel application of these error-exponent results within the framework of an efficient sequential code. The application of a hash function over the message bits provides a methodical and effective way to de-randomize Shannon's random codebook construction. Prediction markets are economic mechanisms for aggregating information about future events through sequential interactions with traders. The pricing mechanisms in these markets are known to be related to optimization algorithms in machine learning and through these connections we have some understanding of how equilibrium market prices relate to the beliefs of the traders in a market. However, little is known about rates and guarantees for the convergence of these sequential mechanisms, and two recent papers cite this as an important open question. In this paper we show how some previously studied prediction market trading models can be understood as a natural generalization of randomized coordinate descent which we call randomized subspace descent (RSD). We establish convergence rates for RSD and leverage them to prove rates for the two prediction market models above, answering the open questions. Our results extend beyond standard centralized markets to arbitrary trade networks. We describe a new class of list decodable codes based on Galois extensions of function fields and present a list decoding algorithm. These codes are obtained as a result of folding the set of rational places of a function field using certain elements (automorphisms) from the Galois group of the extension. This work is an extension of Folded Reed Solomon codes to the setting of Algebraic Geometric codes. We describe two constructions based on this framework depending on if the order of the automorphism used to fold the code is large or small compared to the block length. When the automorphism is of large order, the codes have polynomially bounded list size in the worst case. This construction gives codes of rate @math over an alphabet of size independent of block length that can correct a fraction of @math errors subject to the existence of asymptotically good towers of function fields with large automorphisms. The second construction addresses the case when the order of the element used to fold is small compared to the block length. In this case a heuristic analysis shows that for a random received word, the expected list size and the running time of the decoding algorithm are bounded by a polynomial in the block length. When applied to the Garcia-Stichtenoth tower, this yields codes of rate @math over an alphabet of size @math , that can correct a fraction of @math errors. Let @math be a cyclic @math -algebra of dimension @math with finite dimensional cohomology only in dimension one and two. By transfer theorem there exists a cyclic @math -algebra structure on the cohomology @math . The inner product plus the higher products of the cyclic @math -algebra defines a superpotential function @math on @math . We associate with an analytic Milnor fiber for the formal function @math and define the Euler characteristic of @math is to be the Euler characteristic of the 'et ale cohomology of the analytic Milnor fiber. In this paper we prove a Thom-Sebastiani type formula for the Euler characteristic of cyclic @math -algebras. As applications we prove the Joyce-Song formulas about the Behrend function identities for semi-Schur objects in the derived category of coherent sheaves over Calabi-Yau threefolds. A motivic Thom-Sebastiani type formula and a conjectural motivic Joyce-Song formulas for the motivic Milnor fiber of cyclic @math -algebras are also discussed. Let @math be a smooth scheme over an algebraically closed field @math of characteristic zero and @math a regular function, and write @math Crit @math , as a closed subscheme of @math . The motivic vanishing cycle @math is an element of the @math -equivariant motivic Grothendieck ring @math defined by Denef and Loeser math.AG 0006050 and Looijenga math.AG 0006220, and used in Kontsevich and Soibelman's theory of motivic Donaldson-Thomas invariants, arXiv:0811.2435. We prove three main results: (a) @math depends only on the third-order thickenings @math of @math . (b) If @math is another smooth scheme, @math is regular, @math Crit @math , and @math is an embedding with @math and @math an isomorphism, then @math equals @math "twisted" by a motive associated to a principal @math -bundle defined using @math , where now we work in a quotient ring @math of @math . (c) If @math is an "oriented algebraic d-critical locus" in the sense of Joyce arXiv:1304.4508, there is a natural motive @math , such that if @math is locally modelled on Crit @math , then @math is locally modelled on @math . Using results from arXiv:1305.6302, these imply the existence of natural motives on moduli schemes of coherent sheaves on a Calabi-Yau 3-fold equipped with "orientation data", as required in Kontsevich and Soibelman's motivic Donaldson-Thomas theory arXiv:0811.2435, and on intersections of oriented Lagrangians in an algebraic symplectic manifold. This paper is an analogue for motives of results on perverse sheaves of vanishing cycles proved in arXiv:1211.3259. We extend this paper to Artin stacks in arXiv:1312.0090. Preface 1. Introduction Part I. Preliminaries: 2. Basic Concepts 3. Basic Analysis and Optimality Conditions 4. Basic Linear Algebra 5. Krylov Subspace Methods Part II. Trust-Region Methods for Unconstrained Optimization: 6. Global Convergence of the Basic Algorithm 7.The Trust-Region Subproblem 8. Further Convergence Theory Issues 9. Conditional Models 10. Algorithmic Extensions 11. Nonsmooth Problems Part III. Trust-Region Methods for Constrained Optimization with Convex Constraints: 12. Projection Methods for Convex Constraints 13. Barrier Methods for Inequality Constraints Part IV. Trust-Region Mewthods for General Constained Optimization and Systems of Nonlinear Equations: 14. Penalty-Function Methods 15. Sequential Quadratic Programming Methods 16. Nonlinear Equations and Nonlinear Fitting Part V. Final Considerations: Practicalities Afterword Appendix: A Summary of Assumptions Annotated Bibliography Subject and Notation Index Author Index. We present a linear realizability technique for building Partial Equivalence Relations (PER) categories over Linear Combinatory Algebras. These PER categories turn out to be linear categories and to form an adjoint model with their co-Kleisli categories. We show that a special linear combinatory algebra of partial involutions, arising from Geometry of Interaction constructions, gives rise to a fully and faithfully complete modelfor ML polymorphic types of system F. Any sequential machine M represents a function f M from input sequences to output symbols. A function f is representable if some finite-state sequential machine represents it. The function f M is called an n-th order approximation to a given function f if f M is equal to f for all input sequences of length less than or equal to n . It is proved that, for an arbitrary nonrepresentable function f , there are infinitely many n such that any sequential machine representing an n th order approximation to f has more than n 2 + 1 states. An analogous result is obtained for two-way sequential machines and, using these and related results, lower bounds are obtained for two-way sequential machines and, using these and related results, lower bounds are obtained on the amount of work tape required online and offline Turing machines that compute nonrepresentable functions.