A Framework for Ad-Hoc Type Inference (2007)
Extend Ed, Hosein Askari, Ole I. Hougaard, Michael I. Schwartzbach
) Hosein Askari, Ole I. Hougaard , Michael I. Schwartzbach fhosask,hougaard,misg@daimi.aau.dk BRICS y , Department of Computer Science University of Aarhus 8000 Aarhus C, Denmark Abstract Languages...
Efficient Group Signature Schemes for Large Groups (2007)
Extend Ed, Extended Abstract, Markus Stadler
) Jan Camenisch Department of Computer Science Haldeneggsteig 4 ETH Zurich 8092 Zurich, Switzerland camenisch@inf.ethz.ch Markus Stadler Ubilab Union Bank of Switzerland Bahnhofstr. 45 8021 Zurich,...
Optimal Parallel Approximation Algorithms for Prefix Sums and Integer Sorting (2007)
Extend Ed, Michael T. Goodrich, Yossi Matias
) Michael T. Goodrich Yossi Matias y Uzi Vishkin z Abstract Parallel prefix computation is perhaps the most frequently used subroutine in parallel algorithms today. Its time complexity on the...
Adapting to Asynchronous Dynamic Networks (2007)
Extend Ed, Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Michael Saks
Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation....
A Formal Treatment of Remotely Keyed Encryption (2007)
Extend Ed, Matt Blaze, Joan Feigenbaum, Moni Naor
) ? Matt Blaze, 1 Joan Feigenbaum, 1 Moni Naor 2 1 AT&T Labs -- Research 180 Park Avenue Florham Park, NJ 07932 USA fmab,jfg@research.att.com 2 Dept. Applied Math. and Computer Science Weizmann...
Abstractions for Parallel N-body Simulations (2007)
Extend Ed, Sandeep Bhatt, Marina Chen, Cheng-yee Lin, Pangfeng Liu
ions for Parallel N-body Simulations (Extended Abstract) Sandeep Bhatt Marina Chen Cheng-Yee Lin Pangfeng Liu Department of Computer Science Yale University New Haven, CT 06520 Abstract This paper...
Extend Ed, Extended Abstract, Amr Fahmy, Abdelsalam Heddaya
) Amr Fahmy amr@deas.harvard.edu Aiken Computation Lab Harvard University Abdelsalam Heddaya y heddaya@cs.bu.edu Computer Science Dept. Boston University 1 Introduction Communication and...
Extend Ed, F. Bueno, P. Deransart, W. Drabent, G. Ferrand, M. Hermenegildo
) F. Bueno P. Deransart y W. Drabent z G. Ferrand x M. Hermenegildo J. Ma/luszy'nski -- G. Puebla 1 Introduction This paper presents some on-going work in the ESPRIT project DiSCiPl. The project...
Extend Ed, Extended Abstract, R. N. Uma, Joel Wein
) R. N. Uma Joel Wein y December 2, 1997 Abstract Enumerative approaches, such as branch-and-bound, to solving optimization problems require a subroutine that produces a lower bound on the value of...
The Deterministic Complexity of Parallel Multisearch (2007)
Extend Ed, Armin Baumker, Wolfgang Dittrich, Andrea Pietracaprina
) Armin Baumker 1 Wolfgang Dittrich 1 Andrea Pietracaprina 2 1 Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, Paderborn, Germany 2 Dipartimento...
Layout of the Batcher Bitonic Sorter (2007)
Extend Ed, Shimon Even, S. Muthukrishnan, Michael S. Paterson, Suleyman Cenk S
) Shimon Even S. Muthukrishnan y Michael S. Paterson z Suleyman Cenk S . ahinalp x Abstract The grid-area required by a sorting net for input vectors of length N is shown to be at least (N \Gamma 1)...
The GARF Library of DSM Consistency Models (2007)
Extend Ed, Rachid Guerraoui, Benoit Garbinato, Karim R. Mazouni
Rachid Guerraoui, Benoit Garbinato, Karim R. Mazouni D'epartement d'Informatique Ecole Polytechnique F'ed'erale de Lausanne CH-1015, Suisse e-mail: guerraoui@di.epfl.ch GARF is an...
Gadgets, Approximation, and Linear Programming (2007)
Extend Ed, Luca Trevisan, Gregory B. Sorkin, David P. Williamson
] Luca Trevisan Gregory B. Sorkin y Madhu Sudan y David P. Williamson y From: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, October 1996. Please note final page,...
Synthesis from Knowledge-Based Specifications (2007)
) Ron van der Meyden 1 and Moshe Y. Vardi 2 1 Computing Sciences University of Technology, Sydney P.O. Box 123, Broadway, NSW 2007, Australia ron@socs.uts.edu.au http://www-staff.socs.uts.edu.au/ ¸...
Blindly-Competitive Algorithms: Pricing Bidding as a Case Study (2007)
Extend Ed, Baruch Awerbuch, Yossi Azar
) Baruch Awerbuch Yossi Azar y April 26, 1995 Abstract The standard setting for competitive analysis of online algorithms assumes that online algorithm knows the past (but not future) inputs, and can...
Monomial Bases and Polynomial System Solving (2007)
Extend Ed, Ioannis Z. Emiris, Ashutosh Rege
) Ioannis Z. Emiris Ashutosh Rege Abstract This paper addresses the problem of efficient construction of monomial bases for the coordinate rings of zerodimensional varieties. Existing approaches rely...
Breaking RSA May Be Easier Than Factoring (2007)
Extend Ed, Dan Boneh, Ramarathnam Venkatesan
) Dan Boneh Ramarathnam Venkatesan dabo@cs.stanford.edu venkie@microsoft.com Stanford University Microsoft Research Abstract We provide evidence that breaking low-exponent rsa cannot be equivalent to...
Pin Assignment for Multi-FPGA Systems (2007)
Extend Ed, Scott Hauck, Gaetano Borriello
) Scott Hauck, Gaetano Borriello Department of Computer Science and Engineering University of Washington Seattle, WA 98195 Abstract There is currently great interest in using systems of FPGAs for...
Optimizing Two-Phase, Level-Clocked Circuitry (2007)
Extend Ed, Extended Abstract, Alexander T. Ishii, Charles E. Leiserson, Marios C. Papaefthymiou, O(v E V
) Alexander T. Ishii NEC C&C Research Laboratories Princeton, New Jersey 08540 Charles E. Leiserson Marios C. Papaefthymiou MIT Laboratory for Computer Science Cambridge, Massachusetts 02139...
PSUN: A Profiling System for Usenet News (2007)
Extend Ed, H. Sorensen, M. Mc Elligott
) H. Sorensen, M. Mc Elligott, Computer Science Department, University College, Cork, Ireland. Email: {sorensen, mike@odyssey.ucc.ie} Abstract Information overload has become a well-worn term. Anyone...
S-Parameter Based Macro Model of Distributed-Lumped Networks Using Pade Approximation (2007)
1. Introduction Designing of large scale high performance circuits requires precise knowledge of circuit delays. The computation of delays associated with interconnects, in particular, poses a...
Optimal Time-Critical Scheduling Via Resource Augmentation (2007)
Extend Ed, Cynthia A. Phillips, Cliff Stein, Eric Torng, Joel Wein
) Cynthia A. Phillips Cliff Stein y Eric Torng z Joel Wein x Abstract We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting,...
Semantics and Expressiveness Issues in Active Databases (2007)
) Philippe Picouet E.N.S.T. - Paris picouet@inf.enst.fr Victor Vianu U.C. San Diego vianu@cs.ucsd.edu Abstract A formal framework is introduced for studying the semantics and expressiveness of active...
Classification of Lexical Items via Context Priming (2007)
Extend Ed, David J. Hutches, Walter J. Savitch
David J. Hutches Walter J. Savitch dhutches@ucsd.edu wsavitch@ucsd.edu Department of Computer Science and Engineering, Mail Code 0114 University of California, San Diego La Jolla, CA 92093-0114 I....
Node Weighted Network Upgrade Problems (2007)
Extend Ed, S. O. Krumke, H. Noltemeier, M. V. Marathe, S. S. Ravi
) S.O. Krumke 1 H. Noltemeier 1 M.V. Marathe 2 S.S. Ravi 3 January 22, 1997 Abstract Several problems arising in the areas of communication networks and VLSI design can be expressed in the following...
Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems (2007)
Extend Ed, Thomas H. Cormen, Leonard F. Wisniewski
) Thomas H. Cormen Leonard F. Wisniewski Department of Mathematics and Computer Science Dartmouth College Abstract We give asymptotically equal lower and upper bounds for the number of parallel I/O...
Illumination with Orthogonal Floodlights (2007)
Extend Ed, James Abello, Vladimir Estivill-castro, Thomas Shermer, Jorge Urrutia
) James Abello 1 , Vladimir Estivill-Castro 2 , Thomas Shermer 3 , Jorge Urrutia 4 1 Department of Computer Science, Texas A & M University, College Station, Texas MS 3112, US....
A Lossy Image Codec Based on Index Coding (2007)
Extend Ed, Jun Tian, Raymond O. Wells
) Jun Tian and Raymond O. Wells, Jr. Computational Mathematics Laboratory Rice University Houston, Texas 77251-1892 USA juntian@rice.edu, wells@rice.edu September 28, 1995 in Proc. IEEE DCC,...
) Leslie G. Valiant Division of Applied Sciences Harvard University Cambridge, MA 02138 Abstract Cognitive computation is discussed as a discipline that links together neurobiology, cognitive...
The Loading Time Scheduling Problem (2007)
Extend Ed, Randeep Bhatia, Samir Khuller, Joseph (seffi Naor
) Randeep Bhatia Samir Khuller y Joseph (Seffi) Naor z Computer Science Department Computer Science Department Computer Science Department Univ. of Maryland Univ. of Maryland Technion College Park,...
Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP (2007)
Extend Ed, F. Dehne, A. Ferreira, P. Flocchini, I. Rieping, A. Roncato, ...
E. C'aceres 1 , F. Dehne 2 , A. Ferreira 3 , P. Flocchini 4 , I. Rieping 5 , A. Roncato 6 , N. Santoro 7 , and S. W. Song 8 1 Univ. Federal de Mato Grosso do Sul, Campo Grande, Brasil,...
Deciding Containment for Queries with Complex Objects (2007)
Extend Ed, Alon Y. Levy, Dan Suciu
) Alon Y. Levy levy@research.att.com AT&T Labs Dan Suciu suciu@research.att.com AT&T Labs Abstract We address the problem of query containment and query equivalence for complex objects. We...
ShockAbsorber: A TCP Connection Router (2007)
) Germ'an Goldszmidt and Guerney Hunt IBM T. J. Watson Research Center ABSTRACT: ShockAbsorber is a software router of TCP connections that supports load sharing across multiple TCP servers that...
Long-Lived Renaming Made Adaptive (2007)
Extend Ed, Yehuda Afek, Hagit Attiya, Arie Fouren, Dan Touitou
) Yehuda Afek Hagit Attiya y Arie Fouren z Gideon Stupp x Dan Touitou -- Abstract Two implementations of an adaptive, wait-free, and long-lived renaming task in the read/write shared memory model are...
The Combinatorial Structure of Wait-free Solvable Tasks (2007)
Extend Ed, Extended Abstract, Hagit Attiya, Sergio Rajsbaum
) Hagit Attiya 1 and Sergio Rajsbaum 2 1 Department of Computer Science, The Technion, Haifa 32000, Israel. ??? 2 Instituto de Matem'aticas, UNAM, Ciudad Universitaria, D.F. 04510, M'exico....
Extend Ed, Marcus Schmid, Christian Blum
Marcus Schmid and Christian Blum Institut Eurécom 2229, route des Crêtes F-06904 Sophia Antipolis {mschmid,blum}@eurecom.fr 1 Multimedia Service Provision We present a multimedia platform that...
Fast, Long-Lived Renaming (2007)
Extend Ed, Mark Moir, James H. Anderson
) Mark Moir and James H. Anderson Department of Computer Science The University of North Carolina at Chapel Hill Chapel Hill, North Carolina 27599-3175, USA Abstract. We consider wait-free solutions...
The Combinatorial Structure of Wait-free Solvable Tasks (2007)
Extend Ed, Extended Abstract, Hagit Attiya, Sergio Rajsbaum
) Hagit Attiya 1 and Sergio Rajsbaum 2 1 Department of Computer Science, The Technion, Haifa 32000, Israel. ??? 2 Instituto de Matem'aticas, UNAM, Ciudad Universitaria, D.F. 04510, M'exico....
Compact Location Problems (2007)
Extend Ed, V. Radhakrishnan, S. O. Krumke, M. V. Marathe, D. J. Rosenkrantz, S. S. Ravi
) V. Radhakrishnan S.O. Krumke y M.V. Marathe D.J. Rosenkrantz S. S. Ravi Department of Computer Science University at Albany -- SUNY Albany, NY 12222 Abstract We consider the problem of placing a...
Extend Ed, F. Bueno, P. Deransart, W. Drabent, G. Ferrand, M. Hermenegildo
) F. Bueno P. Deransart y W. Drabent z G. Ferrand x M. Hermenegildo J. Ma/luszy'nski -- G. Puebla 1 Introduction This paper presents some on-going work in the ESPRIT project DiSCiPl. The project...
Extend Ed, Dan Boneh, Glenn Durfee, Nick Howgrave-graham
) Dan Boneh Glenn Durfee y Nick Howgrave-Graham dabo@cs.stanford.edu gdurf@cs.stanford.edu nahg@maths.bath.ac.uk Abstract We present an algorithm for factoring integers of the form N = p r q for...
Dependent Types in Practical Programming (1999)
Extend Ed, Hongwei Xi, Frank Pfenning
) Hongwei Xi Department of Computer Science and Engineering Oregon Graduate Institute of Science and Technology hongwei@cse.ogi.edu Frank Pfenning Department of Computer Science Carnegie Mellon...
A Theoretical and Empirical Study of a Noise-Tolerant Algorithm to Learn Geometric Patterns (1999)
Extend Ed, Sally A. Goldman, Stephen D. Scott
) Sally A. Goldman and Stephen D. Scott Department of Computer Science Washington University St. Louis, MO 63130 sg@cs.wustl.edu and sds@cs.wustl.edu Abstract Developing the ability to recognize a...
The Advantages of Forward Thinking in Generating Rooted and Free Trees (1999)
Extend Ed, Gang Li, Frank Ruskey
(SODA 99) Gang Li and Frank Ruskey Department of Computer Science University of Victoria Victoria, B.C. V8W 3P6, Canada Abstract We present a new approach to the exhaustive generation of rooted and...
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks (1999)
Extend Ed, Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg
) Shlomi Dolev Evangelos Kranakis y Danny Krizanc y David Peleg z Abstract This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles...
Survivable Consensus Objects (1998)
Extend Ed, Dahlia Malkhi, Michael K. Reiter
) Dahlia Malkhi Michael K. Reiter AT&T Labs-Research, Florham Park, NJ, USA fdalia,reiterg@research.att.com Abstract Reaching consensus among multiple processes in a distributed system is...
Optimistic Fair Exchange of Digital Signatures (1998)
Extend Ed, N. Asokan, Victor Shoup, Michael Waidner
) N. Asokan Victor Shoup Michael Waidner IBM Zurich Research Laboratory, Saumerstr. 4, 8803 Ruschlikon, Switzerland faso,sho,wmig@zurich.ibm.com Abstract. We present a new protocol that allows two...
TCP Dynamic Acknowledgment Delay: Theory and Practice (1998)
Extend Ed, Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott
) Daniel R. Dooly and Sally A. Goldman and Stephen D. Scott Dept. of Computer Science Washington University St. Louis, MO 63130 (drd1, sg, sds)@cs.wustl.edu Abstract We study an on-line problem that...
Synthesis of Fault-Tolerant Concurrent Programs (1998)
Extend Ed, Anish Arora, Paul C. Attie, E. Allen Emerson
) Anish ARORA 1 Department of Computer Science The Ohio State University anish@cis.ohio-state.edu Paul C. ATTIE 2 School of Computer Science Florida International University attie@fiu.edu E. Allen...
On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations (1998)
Extend Ed, Miki Hermann, Gernot Salzer
) Miki Hermann 1 and Gernot Salzer 2 1 LORIA (CNRS), BP 239, 54506 Vandoeuvre-l`es-Nancy, France. hermann@loria.fr 2 Technische Universitat Wien, Karlsplatz 13, 1040 Wien, Austria. salzer@logic.at...
Optimistic Fair Exchange of Digital Signatures (1998)
Extend Ed, N. Asokan, Victor Shoup, Michael Waidner
) N. Asokan Victor Shoup Michael Waidner IBM Zurich Research Laboratory, Saumerstr. 4, 8803 Ruschlikon, Switzerland faso,sho,wmig@zurich.ibm.com Abstract. We present a new protocol that allows two...
A Network Based Approach for Realtime Walkthrough of Massive Models (1998)
Extend Ed, Matthias Fischer, Martin Ziegler
) Matthias Fischer y , Tam'as Lukovszki, Martin Ziegler Heinz Nixdorf Institute and Department of Computer Science University of Paderborn, D-33095 Paderborn, Germany fmafi, talu,...
Extend Ed, Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter
) Lars Arge Octavian Procopiuc y Sridhar Ramaswamy z Torsten Suel x Jeffrey Scott Vitter -- Abstract We describe a powerful framework for designing efficient batch algorithms for certain large-scale...
The Performance of Work Stealing in Multiprogrammed Environments (1998)
Extend Ed, Robert D. Blumofe, Dionisios Papadopoulos
) Robert D. Blumofe Dionisios Papadopoulos Department of Computer Sciences, The University of Texas at Austin frdb,dionisisg@cs.utexas.edu As small-scale, shared-memory multiprocessors make their way...
Compact Routing Schemes With Low Stretch Factor (1998)
Extend Ed, Tamar Eilam, Cyril Gavoille, David Peleg
) Tamar Eilam Cyril Gavoille y David Peleg z January 8, 1998 Abstract This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows message routing on every weighted n-node...
TCP Dynamic Acknowledgment Delay: Theory and Practice (1998)
Extend Ed, Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott
) Daniel R. Dooly and Sally A. Goldman and Stephen D. Scott Dept. of Computer Science Washington University St. Louis, MO 63130 (drd1, sg, sds)@cs.wustl.edu Abstract In this paper we study an on-line...
Private Information Storage (1997)
Extend Ed, Rafail Ostrovsky, Victor Shoup
) Rafail Ostrovsky Victor Shoup y Bellcore Bellcore, IBM Abstract This paper deals with the problem of efficiently and privately storing and retrieving information that is distributively maintained...
Exploiting Dependencies to Enhance View Self-Maintainability (1997)
) Nam Huyn Stanford University huyn@cs.stanford.edu Abstract View self-maintenance is the process of incrementally refreshing a materialized view using the view instance and the update to some base...
Extend Ed, F. Bueno, P. Deransart, W. Drabent, G. Ferrand, M. Hermenegildo
) F. Bueno P. Deransart y W. Drabent z G. Ferrand x M. Hermenegildo J. Ma/luszy'nski -- G. Puebla 1 Introduction This paper presents some on-going work in the ESPRIT project DiSCiPl. The project...
Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP (1997)
Extend Ed, F. Dehne, A. Ferreira, P. Flocchini, I. Rieping, A. Roncato, ...
E. C'aceres 1 , F. Dehne 2 , A. Ferreira 3 , P. Flocchini 4 , I. Rieping 5 , A. Roncato 6 , N. Santoro 7 , and S. W. Song 8 1 Univ. Federal de Mato Grosso do Sul, Campo Grande, Brasil,...
The Deterministic Complexity of Parallel Multisearch (1996)
Extend Ed, Armin Baumker, Wolfgang Dittrich, Andrea Pietracaprina
) Appeared in: Proceedings of 5th SWAT '96, Springer LNCS 1097, 1996 Armin Baumker 1 Wolfgang Dittrich 1 Andrea Pietracaprina 2 1 Department of Mathematics and Computer Science and Heinz Nixdorf...
Integrating Information by Outerjoins and Full Disjunctions (1996)
Extend Ed, Anand Rajaraman, Jeffrey D. Ullman
) Anand Rajaraman Jeffrey D. Ullman Department of Computer Science Stanford University --anand, ullman@cs.stanford.edu Abstract Our motivation is the piecing together of tidbits of information found...
Answering Queries Using Limited External Query Processors (1996)
Extend Ed, Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman
) Alon Y. Levy AT&T Research levy@research.att.com Anand Rajaraman Stanford University anand@cs.stanford.edu Jeffrey D. Ullman Stanford University ullman@cs.stanford.edu Abstract When answering...
Hybrid cc, Hybrid Automata and Program Verification (1996)
Extend Ed, Vineet Gupta, Radha Jagadeesan, Vijay Saraswat
) Vineet Gupta ? Radha Jagadeesan ?? Vijay Saraswat ? 1 Introduction Synchronous programming. Discrete event driven systems [HP85,Ber89,Hal93] are systems that react with their environment at a rate...
Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach (1996)
Extend Ed, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter, Instytut Informatyki, Uniwersytet Warszawski
) Leszek G¸asieniec 1 ? Marek Karpinski 2 ?? Wojciech Plandowski 3 ??? Wojciech Rytter 3 y 1 Max-Planck Institut fur Informatik, Im Stadtwald, Saarbrucken D-66123, Germany. 2 Dept. of Computer...
Extend Ed, Claudio Bettini, X. Sean Wang, Sushil Jajodia
) Claudio Bettini Dept. of Computer Science (DSI) University of Milan via Comelico 39, 20135 Milan, Italy bettini@dsi.unimi.it X. Sean Wang, Sushil Jajodia Dept. of Info.& Software Systems Eng....
Improved Scheduling Algorithms for Minsum Criteria (1996)
Extend Ed, Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Cliff Stein, ...
) Soumen Chakrabarti ? Cynthia A. Phillips ?? Andreas S. Schulz ??? David B. Shmoys y Cliff Stein z Joel Wein x Abstract. We consider the problem of finding near-optimal solutions for a variety of...
A User Plane Security Protocol for ATM Networks (1996)
Extend Ed, Rao J. Cherukuri, Mohammad Peyravian, Venkata Surapaneni, Shyhtsun F. Wu
) Rao J. Cherukuri, Mohammad Peyravian Venkata Surapaneni IBM Corporation P.O.Box 12195 RTP, NC 27709 fraoc, peyravn, vsurapanenig@vnet.ibm.com Shyhtsun F. Wu Computer Science Department North...
Answering Queries Using Limited External Query Processors (1996)
Extend Ed, Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman
) Alon Y. Levy AT&T Research levy@research.att.com Anand Rajaraman Stanford University anand@cs.stanford.edu Jeffrey D. Ullman Stanford University ullman@cs.stanford.edu Abstract When answering...
Real-Time Object Sharing with Minimal System Support (1996)
Extend Ed, Srikanth Ramamurthy, Mark Moir, James H. Anderson
) Srikanth Ramamurthy, Mark Moir, and James H. Anderson Department of Computer Science, University of North Carolina at Chapel Hill Abstract We show that, for a large class of hard real-time systems,...
A Framework for Experimenting with QoS for Multimedia Services (1996)
Extend Ed, Deming Chen, Regis Colwell, Herschel Gelman, Panos K. Chrysanthis
) Deming Chen, Regis Colwell, Herschel Gelman, Panos K. Chrysanthis and Daniel Moss'e Department of Computer Science University of Pittsburgh Pittsburgh, PA 15260 fpanos,mosseg@cs.pitt.edu 1...
On Hamiltonian Triangulations in Simple Polygons (1995)
) Giri NARASIMHAN ? Department of Mathematical Sciences The University of Memphis Memphis TN 38152. e-mail: giri@next1.msci.memphis.edu Abstract. An n-vertex simple polygon P is said to have a...
Randomized Query Processing in Robot Path Planning (1995)
Extend Ed, Lydia E. Kavraki, Rajeev Motwani
) LYDIA E. KAVRAKI JEAN-CLAUDE LATOMBE RAJEEV MOTWANI y PRABHAKAR RAGHAVAN z Abstract The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query...
iKP -- A Family of Secure Electronic Payment Protocols (1995)
Extend Ed, Mihir Bellare, Juan A. Garay, Ralf Hauser, Amir Herzberg, Hugo Krawczyk, ...
Mihir Bellare y , Juan A. Garay y , Ralf Hauser z , Amir Herzberg y , Hugo Krawczyk y , Michael Steiner z , Gene Tsudik z , Michael Waidner z July 12, 1995 Abstract This paper proposes a family of...
Generalized Search Trees for Database Systems (1995)
Extend Ed, Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer
) Joseph M. Hellerstein University of Wisconsin, Madison jmh@cs.berkeley.edu Jeffrey F. Naughton University of Wisconsin, Madison naughton@cs.wisc.edu Avi Pfeffer University of California, Berkeley...
Language Learning from Texts: Mind Changes, Limited Memory and Monotonicity (1995)
Extend Ed, Efim Kinber, Frank Stephan
) Efim Kinber y University of Delaware Frank Stephan z Universit¨at Karlsruhe Abstract The paper explores language learning in the limit under various constraints on the number of mindchanges,...
A Game-Theoretic Classification of Interactive Complexity Classes (1995)
Extend Ed, Joan Feigenbaum, Daphne Koller, Peter Shor
) Joan Feigenbaum AT&T Bell Labs, 2C-473 600 Mountain Avenue Murray Hill, NJ 07974-0636 jf@research.att.com Daphne Koller UC Berkeley Computer Science Division Berkeley, CA 94720...
Computational Complexity of Simultaneous Elementary Matching Problems (1995)
) Miki Hermann 1; Phokion G. Kolaitis 2;y 1 CRIN (CNRS) and INRIA-Lorraine, BP 239, 54506 Vand#uvre-l#s-Nancy, France. (hermann@loria.fr) 2 Computer and Information Sciences, University of...
Scalable Atomic Primitives for Distributed Shared Memory Multiprocessors (1995)
Extend Ed, Maged M. Michael, Michael L. Scott
) Maged M. Michael Department of Computer Science University of Rochester Rochester, NY 14627-0226 USA Michael L. Scott Department of Computer Science University of Rochester Rochester, NY 14627-0226...
Answering Queries Using Views (1995)
Extend Ed, Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava
) Alon Y. Levy AT&T Bell Laboratories levy@research.att.com Alberto O. Mendelzon University of Toronto mendel@db.toronto.edu Yehoshua Sagiv y Hebrew University, Jerusalem sagiv@cs.huji.ac.il...
A Game-Theoretic Classification of Interactive Complexity Classes (1995)
Extend Ed, Joan Feigenbaum, Daphne Koller, Peter Shor
) Joan Feigenbaum AT&T Bell Labs, 2C-473 600 Mountain Avenue Murray Hill, NJ 07974-0636 jf@research.att.com Daphne Koller UC Berkeley Computer Science Division Berkeley, CA 94720...
High Performance Synchronization Algorithms for Multiprogrammed Multiprocessors (1995)
Extend Ed, Robert W. Wisniewski, Leonidas Kontothanassis, Michael L. Scott
) Robert W. Wisniewski, Leonidas Kontothanassis, and Michael L. Scott Department of Computer Science University of Rochester Rochester, NY 14627-0226 fbob,kthanasi,scottg@cs.rochester.edu June 1994...
Universal Constructions for Multi-Object Operations (1995)
Extend Ed, James H. Anderson, Mark Moir
) James H. Anderson and Mark Moir Department of Computer Science, University of North Carolina, Chapel Hill, NC 27599-3175 Abstract We present wait-free and lock-free universal constructions that...
k-Exclusion to Implement Resilient, Scalable Shared Objects (1994)
Extend Ed, James H. Anderson, Mark Moir
) James H. Anderson and Mark Moir Department of Computer Science The University of North Carolina at Chapel Hill Chapel Hill, North Carolina 27599-3175, USA Abstract We present a methodology for the...
Inheritance of Interface Specifications (1994)
Extend Ed, Gary T. Leavens, Gary T. Leavens
) Gary T. Leavens TR #93-23 September 1993 Keywords: specification, inheritance, subtype, subclass, modularity, objectoriented, abstract data type. 1992 CR Categories: D.2.1 [Software Engineering ]...
Inheritance of Interface Specifications (1994)
Extend Ed, Gary T. Leavens, Gary T. Leavens
) Gary T. Leavens TR #93-23 September 1993 Keywords: specification, inheritance, subtype, subclass, modularity, objectoriented, abstract data type. 1992 CR Categories: D.2.1 [Software Engineering ]...
Uniform Actions in Asynchronous Distributed Systems (1994)
Extend Ed, Dalia Malki, Ken Birman, Aleta Ricciardi
Dalia Malki Ken Birman y Aleta Ricciardi z Andr'e Schiper x Abstract We develop necessary conditions for the development of asynchronous distributed software that will perform uniform actions...
Uniform Actions in Asynchronous Distributed Systems (1994)
Extend Ed, Dalia Malki, Ken Birman, Aleta Ricciardi
Dalia Malki Ken Birman y Aleta Ricciardi z Andr'e Schiper x Abstract We develop necessary conditions for the development of asynchronous distributed software that will perform uniform actions...
Systematic Generation of Cryptographically Robust S-boxes (1993)
Extend Ed, Jennifer Seberry, Xian-mo Zhang, Yuliang Zheng
) Jennifer Seberry Xian-Mo Zhang Yuliang Zheng Department of Computer Science, the University of Wollongong Wollongong, NSW 2522, AUSTRALIA E-mail: fjennie,xianmo,yuliangg@cs.uow.edu.au May 27, 1996...
Towards a Necessary and Sufficient Condition for Wait-free Synchronization (1993)
Extend Ed, James H. Anderson, Mark Moir
) James H. Anderson and Mark Moir Department of Computer Science, The University of Maryland College Park, Maryland 20742-3255 U.S.A. Abstract. We define a class of shared objects called snapshot...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Extend Ed, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
) Yoav Freund AT&T Research Murray Hill, NJ 07974 Michael Kearns AT&T Research Murray Hill, NJ 07974 Dana Ron MIT Cambridge, MA 02138 Ronitt Rubinfeld Cornell University Ithaca, NY 14853...
Indexing for Data Models with Constraints and Classes (1993)
Extend Ed, Paris C. Kanellakis, Sridhar Ramaswamy, Darren E. Vengroff, Jeffrey S. Vitter
) Paris C. Kanellakis Sridhar Ramaswamy y Darren E. Vengroff z Jeffrey S. Vitter x Abstract We examine I/O-efficient data structures that provide indexing support for new data models. The database...
Maintaining Views Incrementally (1993)
Extend Ed, Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian
Ashish Gupta Stanford University agupta@cs.stanford.edu Inderpal Singh Mumick AT&T Bell Laboratories mumick@research.att.com V.S. Subrahmanian y University of Maryland vs@cs.umd.edu Abstract We...
Efficient Learning of Typical Finite Automata from Random Walks (1993)
Extend Ed, Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, ...
) Yoav Freund University of California Santa Cruz, CA 95064 Michael Kearns AT&T Bell Laboratories Murray Hill, NJ 07974 Dana Ron Hebrew University Jerusalem 91904, Israel Ronitt Rubinfeld Cornell...
Towards a Theory of Actor Computation (1992)
Extend Ed, Gul Agha, Ian A. Mason, Scott Smith, Carolyn Talcott
) Gul Agha University of Illinois agha@cs.uiuc.edu Ian A. Mason Stanford University iam@cs.stanford.edu Scott Smith Johns Hopkins University scott@cs.jhu.edu Carolyn Talcott Stanford University...
Wallet Databases with Observers (1992)
Extend Ed, David Chaum, Torben Pryds Pedersen
) David Chaum CWI The Netherlands Torben Pryds Pedersen Aarhus University Denmark Abstract Previously there have been essentially only two models for computers that people can use to handle ordinary...
Towards a Theory of Actor Computation (1992)
Extend Ed, Gul Agha, Ian A. Mason, Scott Smith, Carolyn Talcott
) Gul Agha University of Illinois agha@cs.uiuc.edu Ian A. Mason Stanford University iam@cs.stanford.edu Scott Smith Johns Hopkins University scott@cs.jhu.edu Carolyn Talcott Stanford University...
A Performance Driven Generator for Efficient Testable Conditional-Sum-Adders (1992)
Extend Ed, B. Becker, P. Molitor
) B. Becker P. Molitor Comp. Sc. Dept., J.W.G.-University Comp. Sc. Dept., University of Saarland W 6000 Frankfurt, Germany W 6600 Saarbrucken, Germany Abstract We present a performance driven...
A New Characterization of Mehlhorn's Polynomial Time Functionals (1991)
Extend Ed, Bruce Kapron, Stephen A. Cook
) Bruce Kapron School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 bmkapron@cs.cmu.edu Stephen A. Cook Department of Computer Science University of Toronto Toronto, Ontario,...
Hiding Instances in Zero-Knowledge Proof Systems (1990)
Extend Ed, Donald Beaver, Joan Feigenbaum, Victor Shoup
CRYPTO-1990 Proceedings) Donald Beaver Joan Feigenbaum y Victor Shoup z Abstract Informally speaking, an instance-hiding proof system for the function f is a protocol in which a polynomial-time...