waashk/acm huggingface dataset:
intensions and extensions in a reflective tower  this article presents a model of the reflective tower based on the formal semantics of its levels. they are related extensionally by their mutual interpretation and intensionally by reification and reflection.  the key points obtained here are: a formal relation between the semantic domains of each level; a formal identification of reification and reflection; the visualisation of intensional snapshots of a tower of interpreters; a formal justification and a generalization of brown's meta-continuation; a (structural) denotational semantics for a compositional subset of the model; the distinction between making continuations jumpy and pushy; the discovery of the tail-reflection property; and a scheme implementation of a properly tail- reflective and single-threaded reflective tower.  section 1 presents the new approach taken here: rather than implementing reification and reflection leading to a tower, we consider an infinite tower described by the semantics of each level and relate these by reification and reflection. meta- circularity then gives sufficient conditions for implementing it. section 2 investigates some aspects of the environments and control in a reflective tower. an analog of the funarg problem is pointed out, in relation with the correct environment at reification time. jumpy and pushy continuations are contrasted, and the notions of ephemeral level and proper tail-reflection are introduced. our approach is compared with related work and after a conclusion, some issues are proposed.  olivier danvy karoline malmkjaer
relativizing complexity classes with sparse oracles  baker, gill, and solovay constructed sparse sets a and b such that p(a) np(a) and np(b) co- np(b). in contrast to their results, we prove that p = np if and only if for every tally language t, p(t) = np( t), and that np = co-np if and only if for every tally language t, np(t) = co-np(t). we show that the polynomial hierarchy collapses if and only if there is a sparse set s such that the polynomial hierarchy relative to s collapses. similar results are obtained for several other complexity classes.  timothy j. long alan l. selman
implicit parameters  this paper introduces a language feature, called implicit parameters, that provides dynamically scoped variables within a statically-typed hindley-milner framework. implicit parameters are lexically distinct from regular identifiers, and are bound by a special with construct whose scope is dynamic, rather than static as with let. implicit parameters are treated by the type system as parameters that are not explicitly declared, but are inferred from their use.  we present implicit parameters within a small call-by-name λ-calculus. we give a type system, a type inference algorithm, and several semantics. we also explore implicit parameters in the wider settings of call-by-need languages with overloading, and call-by-value languages with effects. as a witness to the former, we have implemented implicit parameters as an extension of haskell within the hugs interpreter, which we use to present several motivating examples.  jeffrey r. lewis john launchbury erik meijer mark b. shields
exponential determinization for -automata with strong-fairness acceptance condition (extended abstract)  in [saf88] an exponential determination procedure for bu"chi automata was shown, yielding tight bounds for decision procedures of some logics ([ej88, saf88, sv89, kt89]). in [sv89] the complexity of determinization and complementation of ω-automata was further investigated, leaving as an open question the complexity of the determinization of a single class of ω-automata. for this class of ω-automata with strong fairness as acceptance condition (street automata), [sv89] managed to show an exponential complementation procedure, but showed that the blow-up of the translation of these automata to any of the classes known to admit exponential determinization is inherently exponential. this might suggest that the blow-up of the determinization of street automata is inherently doubly exponential.  surprisingly, we show an exponential determinization construction for any streett automaton. in fact, the complexity of our construction is roughly the same as the complexity achieved in [saf88] for bu"chi automata. moreover, a simple observation extends this upper bound to the complexity of the complementation problem. since any ω-automaton that admits exponential determinization can be easily converted into a streett automaton, we get one procedure that can be used for all of these conversions. this construction is optimal (up to a constant factor in the exponent) for all of these conversions.  our results imply that streett automata (with strong fairness as acceptance condition) can be used instead of bu"chi automata (with the weaker acceptance condition) without any loss of efficiency.  shmuel safra
two-prover one-round proof systems: their power and their problems (extended abstract)  we characterize the power of two-prover one-round (mip(2,1)) proof systems, showing that mip(2,1)=nexptime. however, the following intriguing question remains open: does parallel repetition decrease the error probability of mip(2,1) proof systems?.  we use techniques based on quadratic programming to study this problem, and prove the parallel repetition conjecture in some special cases. interestingly, our work leads to a general polynomial time heuristic for any np-problem. we prove the effectiveness of this heuristic for several problems, such as computing the chromatic number of perfect graphs.  uriel feige laszlo lovasz
the random access hierarchy  to be considered fast, algorithms for operations on large data structures should operate in polylog time, i.e., with the number of steps bounded by a polynomial in log(n) where n is the size of the data structure. example: an ordered list of reasonably short strings can be searched in log2 (n) time via binary search. to measure the time and space complexity of such operations, the usual turing machine with its serial-access input tape is replaced by a random access model. to compare such problems and define completeness, the appropriate relation is loglog reducibility: the relation generated by random- access transducers whose work tapes have length at most log(log(n)). the surprise is that instead of being a refinement of the standard log space, polynomial time, polynomial space, ... hierarchy, the complexity classes for these random-access turing machines form a distinct parallel hierarchy, namely, polylog time, polylog space, exppolylog time, ... . propositional truth evaluation, context-free language recognition and searching a linked list are complete for polylog space. searching ordered lists and searching unordered lists are complete for polylog time and nondeterministic polylog time respectively. in the serial-access hierarchy, log-space reducibility is not fine enough to classify polylog-time problems and there can be no complete problems for polylog space even with polynomial-time turing reducibility  dale myers
communication complexity of secure computation (extended abstract)  a secret-ballot vote for a single proposition is an example of a secure distributed computation. the goal is for m participants to jointly compute the output of some n-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior.  in this paper, we initiate the investigation of the communication complexity of unconditionally secure multi-party computation, and its relation with various fault-tolerance models. we present upper and lower bounds on communication, as well as tradeoffs among resources.  first, we consider the "direct sum problem" for communications complexity of perfectly secure protocols: can the communication complexity of securely computing a single function f : fn -&gt; f at k sets of inputs be smaller if all are computed simultaneously than if each is computed individually? we show that the answer depends on the failure model. a factor of o(n/log n) can be gained in the privacy model (where processors are curious but correct); specifically, when f is n-ary addition (mod 2), we show a lower bound of (n2 log n) for computing f o(n) times simultaneously. no gain is possible in a slightly stronger fault model (fail-stop mode); specifically, when f is n-ary addition over gf(q), we show an exact bound of (kn2 log q) for computing f at k sets of inputs simultaneously (for any k ≥ 1).  however, if one is willing to pay an additive cost in fault tolerance (from t to t-k+1), then a variety of known non-cryptographic protocols (including "provably unparallelizable" protocols from above!) can be systematically compiled to compute one function at k sets of inputs with no increase in communication complexity. our compilation technique is based on a new compression idea of polynomial-based multi-secret sharing.  lastly, we show how to compile private protocols into error-detecting protocols at a big savings of a factor of o (n3 matthew franklin moti yung
on tape versus core an application of space efficient perfect hash functions to the invariance of space  in complexity theory the use of informal estimates can be justified by appealing to the invariance thesis which states that all standard models of computing devices are sufficiently equivalent. this thesis would require, among others, that a ram can be simulated by a turingmachine with constant factor overhead in space. such a simulation is hard to obtain if the traditional spacemeasure for ram-space is used. the simulation uses a new method for condensing space, based on perfect hashing.  c. slot p. van emde boas
approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation  we present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. the distinguishing feature of our algorithms is their low running time: o(m logm) and o(m logm(l \\+ log (n))) respectively, where n and m are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. the main algorithmic ideas are a new extension of the primal-dual schema and the use of lagrangian relaxation to derive approximation algorithms.  kamal jain vijay v. vazirani
probabilistic analysis of bandwidth minimization algorithms  we study the probabilistic performance of heuristic algorithms for the np- complete bandwidth minimization problem. let (equation) be a graph with (equation). define the bandwidth of g by (equation) where τ ranges over all permutations on v. let a be a bandwidth minimization algorithm and let a (g) denote the bandwidth of the layout produced by a on the graph g. we say that a is a level algorithm if for all graphs (equation) the layout τ produced by a on g satisfies (equation) the level algorithms were first introduced by cuthill and mckee [1] and have proved quite successful in practice. however, it is easy to construct examples that cause the level algorithms to perform poorly. consequently worst-case analysis provides no insight to their practical success. in this paper we use probabilistic analysis in order to gain an understanding of these algorithms and to help us design better algorithms.  let (equation) be the graph defined by (equation) and let g be a random spanning subgraph of bn in which the vertices have been randomly re-labelled. we show that if a, is a level algorithm and (equation) then (equation) almost always holds, where ε is any positive constant. we also introduce a class of algorithms called the modified level algorithms and show that if a ' is a modified level algorithm and (equation) then (equation) almost always holds. a particular modified level algorithm mla1 is analyzed and we show that when (equation). we also study several other properties of random subgraphs of bn .  jonathan turner
a simple on-line bin-packing algorithm  the one-dimensional on-line bin-packing problem is considered, a simple o(1)-space and o(n)-time algorithm, called harmonicm, is presented. it is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the o(n)-space and o(n log n)-time algorithm first fit. also shown is that 1.691 … is a lower bound for all 0(1)-space on-line bin-packing algorithms. finally a revised version of harmonicm , an o(n)-space and o(n)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.  d c. c. lee d. t. lee
fast algorithms for n-dimensional restrictions of hard problems  let m be a parallel ram with p processors and arithmetic operations addition and subtraction recognizing l nn in t steps. (inputs for m are given integer by integer, not bit by bit.) then l can be recognized by a (sequential) linear search algorithm (lsa) in o(n_4(log(n ) + t \\+ log(p))) steps. thus many n-dimensional restrictions of np-complete problems (binary programming, traveling salesman problem, etc.) and even that of the uniquely optimum traveling salesman problem, which is &amp;am; p;#916;p2-complete, can be solved in polynomial time by an lsa. this result generalizes the construction of a polynomial lsa for the n-dimensional restriction of the knapsack problem previously shown by the author, and destroys the hope of proving nonpolynomial lower bounds on lsas for any problem that can be recognized by a pram as above with 2poly(n) processors in poly(n) time.  friedhelm meyer auf der heide
degrees of inferability  most theories of learning consider inferring a functionf from either (1) observations aboutf or, (2) questions aboutf. we consider a scenario whereby thelearner observes f and asks queriesto some set a.ex[a] is the set of concept classesex-learnable by an inductiveinference machine with oracle a.a andf areex- equivalent ifex[a] = ex[b]. the equivalenceclasses induced are the degrees ofinferability. we prove several results about thesedegrees: (1) there are an uncountable number of degrees. (2) fora r.e., rec ε bc[a] iff &0slash; ≤ta , and there is evidence thisholds for all sets a. (3) fora, b r.e.,a ≡t biffex[a] = ex[b]. (4) there existsa, b low2 r.e.,a|rb,ex[a] = ex[b]. (hence (3) isoptimal).  peter cholak efim kinber rod downey martin kummer lance fortnow stuart kurtz william gasarch theodore a. slaman
the 1-2-3 routing algorithm or the single channel 2-step router on 3 interconnection layers  in this paper an algorithm is presented for the single channel routing on 3 interconnection layers. first some general characteristics of routing on 3 interconnection layers are presented. then the specifications are introduced of the routing problem on 3 interconnection layers that will be considered. pins will be allowed to come out on both the diffusion/poly layer and the second metal layer with the routing done on both the first and second metal layer. if only the first metal layer was to be used horizontally then the routing problem could be solved by a simple left-edge channel algorithm. however the 1-2-3 algorithm presented here will solve identical problems with a smaller number of tracks and via's since it makes use of some specific characteristics of routing on 3 interconnection layers.
a note on probabilistically verifying integer and polynomial products  probabilistic algorithms are presented for testing the result of the product of two n-bit integers in o(n) bit operations and for testing the result of the product of two polynomials of degree n over any integral domain in 4n \\+ o(n) algebraic operations with the error probability o(l/n1-ε) for any ε > 0\\. the last algorithm does not depend on the constants of the underlying domain.  michael kaminski
improved bounds for routing and sorting on multi-dimensional meshes  we show improved bounds for 1--1 routing and sorting on multi- dimensional meshes and tori. in particular, we give a fairly simple deterministic algorithm for sorting on the d-dimensional mesh of side length n that achieves a running time of 3 dn/2+o(nd-dimensional mesh and torus, respectively, that make one copy of each element. we also show lower bounds for sorting with respect to a large class of indexing schemes, under a model of the mesh where each processor can hold an arbitrary number of packets. finally, we describe algorithms for permutation routing whose running times come very close to the diameter lower bound.  torsten suel
polygon triangulation in o(n log log n) time with simple data-structures  we give a new  (n log log n)-time deterministic linear-time algorithm for triangulating simple n-vertex polygons, which avoids the use of complicated data-structures. in addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run in  (n log* n) time. the major new techniques employed are the efficient location of horizontal visibility edges which partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. this latter technique has other interesting applications, including a linear-time algorithm to convert a steiner triangulation of a polygon into a true triangulation.  this research was partially supported by dimacs and the following grants: nserc 583584, nserc 580485, nsf-stc88-09648, onr-n00014-87-0467.  david g. kirkpatrick maria m. klawe robert e. tarjan
a method for deciding whether the galois group is abelian  we propose a polynomial time algorithm to decide whether the galois group of an irreducible polynomial ∈ q[x] is abelian, and, if so, determine all its elements along with their action on the set of roots of . this algorithm does not require factorization of polynomials over number fields. instead we shall use the quadratic newton---lifting and the truncated expressions of the roots of over a p\\---adic number field qp, for an appropriate prime p in z.  pilar fernandez-ferreiros maria de los angeles gomez-molleda
the prime factor non-binary discrete fourier transform and use of crystal_router as a general purpose communication routine  we have implemented one of the fast fourier transform algorithms, the prime factor algorithm (pfa), on the hypercube. on sequential computers, the pfa and other discrete fourier transforms (dft) such as the winograd algorithm (wfa) are known to be very efficient. however, both algorithms require full data shuffling and are thus challenging to any distributed memory parallel computers. we use a concurrent communication algorithm, called the crystal_router for communicating shuffled data. we will show that the speed gained in reduced arithmetic compared to binary fft is sufficient to overcome the extra communication requirement up to a certain number of processors. beyond this point the standard cooley-tukey fft algorithm has the best performance. we comment briefly on the application of the dft to signal processing in synthetic aperture radar (sar).  g. aloisio n. veneziani j. s. kim g. c. fox
computer vision for computer interaction figure 1 shows a vision of the future from the 1939 world's fair. the human-machine interface that was envisioned is wonderful. both machines are equipped with cameras; the woman interacts with the machine using an intuitive gesture. that degree of naturalness is a goal today for researchers designing human-machine interfaces. william t. freeman paul a. beardsley hiroshi kage ken-ichi tanaka kazuo kyuma craig d. weissman
dynamic scheduling of a fixed bandwidth communications channel for controlling multiple robots  we describe a distributed software system for controlling a group of miniature robots using a low capacity communication system. space and power limitations on the robots drastically limit the capacity of the communication system and require sharing bandwidth and other resources among the robots. we have developed a scheduling and resource allocation system that is capable of dynamically assigning resources to each robot.  paul e. rybski sascha a. stoeter maria gini dean f. hougen nikolaos papanikolopoulos
human vision, anti-aliasing, and the cheap 4000 line display  despite its other advantages, one of the major objections to raster graphics has been the poor image quality and aliasing effects caused by discrete sampling. these effects include "jaggies" or stair-stepping, crawling, line breakup, and scintillation. several solutions have been proposed in the literature, however, most suffer severe drawbacks and are only partially successful at eliminating aliasing effects. one solution, area anti-aliasing, is not only effective, it produces results comparable to higher resolution systems. using widely available data on human visual response, it is shown how this technique actually increases the perceived resolution of a display beyond the hardware resolution by factors of up to 16x. the requirements of such a system are discussed, as well as some of the problems encountered.  william j leler
the design of interactive simulations  we propose a methodology for developing simulations in the interactive mode. rather than use an iconic model for doing so, we show how the use of systems theory representation enhances the interaction. this not only facilitates debugging, but is of fundamental assistance in the model development itself. although recent advances in the realistic portrayal of systems has made great advances, the systems representation has been neglected in considering interaction. our hope is that our observations will lead to more research in this area.  alfred w. jones
qsplat: a multiresolution point rendering system for large meshes  advances in 3d scanning technologies have enabled the practical creation of meshes with hundreds of millions of polygons. traditional algorithms for display, simplification, and progressive transmission of meshes are impractical for data sets of this size. we describe a system for representing and progressively displaying these meshes that combines a multiresolution hierarchy based on bounding spheres with a rendering system based on points. a single data structure is used for view frustum culling, backface culling, level-of-detail selection, and rendering. the representation is compact and can be computed quickly, making it suitable for large data sets. our implementation, written for use in a large-scale 3d digitization project, launches quickly, maintains a user-settable interactive frame rate regardless of object complexity or camera position, yields reasonable image quality during motion, and refines progressively when idle to a high final image quality. we have demonstrated the system on scanned models containing hundreds of millions of samples.  szymon rusinkiewicz marc levoy
the display of characters using gray level sample arrays  character fonts on raster scanned display devices are usually represented by arrays of bits that are displayed as a matrix of black and white dots. this paper reviews a filtering and sampling method as applied to characters for building multiple bit per pixel arrays. these arrays can be used as alternative character representations for use on devices with gray scale capability. discussed in this paper are both the filtering algorithms that are used to generate gray scale fonts and some consequences of using gray levels for the representation of fonts including:  1\\. the apparent resolution of the display is increased when using gray scale fonts allowing smaller fonts to be used with higher apparent positional accuracy and readability. this is especially important when using low resolution displays.  2\\. fonts of any size and orientation can be generated automatically from suitable high precision representations. this automatic generation removes the tedious process of "bit tuning" fonts for a given display.  john e. warnock