Rectangle-of-Influence Drawings of Four-Connected Plane Graphs (2008)
Exte Nd Ed, Kazuyuki Miura, Takao Nishizeki
Kazuyuki Miura Takao Nishizeki Graduate School of Information Sciences Tohoku University, Aoba-yama 05, Sendai 980-8579, Japan E-mail: miura@nishizeki.ecei.tohoku.ac.jp nishi@ecei.tohoku.ac.jp...
Towards Flexible Teamwork in Behavior-Based Robots: (2008)
Gal A. Kaminka # Computer Science Department galk@cs.biu.ac.il Inna Frenkel Computer Science Department frenkei1@cs.biu.ac.il Categories and Subject Descriptors I.2.11 [Distributed Artificial...
A Hierarchy of Conditions for Consensus Solvability (2008)
Exte Nd Ed, Achour Mostefaoui Y, Sergio Rajsbaum Z
Achour Mostefaoui 35042 Rennes Cedex Sergio Rajsbaum Compaq CRL One Cambridge Center 02142 Cambridge, MA Michel Raynal 35042 Rennes Cedex Matthieu Roy 35042 Rennes Cedex France ABSTRACT In a previous...
A Hierarchy of Conditions for Consensus Solvability (2008)
Exte Nd Ed, Achour Mostefaouiysergio, Rennes Cedex
Achour Mostefaoui 35042 Rennes Cedex Sergio Rajsbaum Compaq CRL One Cambridge Center 02142 Cambridge, MA Michel Raynal 35042 Rennes Cedex Matthieu Roy 35042 Rennes Cedex France ABSTRACT In a previous...
Retrenchment and the Mondex Electronic Purse (2008)
Exte Nd Ed, Richard Banach, Czeslaw Jeske, Susan Stepney, Southampton So Bj
Richard Banach , Michael Poppleton Czeslaw Jeske and Susan Stepney Department of Computer Science, University of Manchester, Manchester M13 9PL, UK, fbanach,cjg@cs.man.ac.uk Department of Electronics...
Incremental Triangulation for Trimmed Spline Surfaces (2008)
Exte Nd Ed, Subodh Kumar, Dinesh Manocha
Subodh Kumar Dinesh Manocha Department of Computer Science University of North Carolina Chapel Hill, NC, 27599-3175 fkumar,manochag@cs.unc.edu 1
Pricing Price Information in E-Commerce (2008)
Exte Nd Ed, Panos M. Markopoulos, Lyle H. Ungar
Panos M. Markopoulos Computer and Information Science Dept.
Specification and Refinement of Secure IT-Systems (2008)
Exte Nd Ed, Thomas Santen, Andreas Pfitzmann, Maritta Heisel
Thomas Santen Institut fur Softwaretechnik und Theoretische Informatik Technische Universitat Berlin 10587 Berlin, Germany santen@acm.org Andreas Pfitzmann Fakultat fur Informatik Technische...
A Simple Procedure for Finding Guessing Attacks (2008)
Exte Nd Ed, Ricardo Corin, Ro Etalle
Ricardo Corin and Sandro Etalle 1,2 Dept. of Computer Science, University of Twente, The Netherlands CWI, Center for Mathematics and Computer Science Amsterdam {corin,etalle}@cs.utwente.nl Abstract A...
Delivering Popular Web Pages Using Cyclic Multicast (2007)
Exte Nd Ed, Kevin C. Almeroth, Mostafa H. Ammar
) Kevin. C. Almeroth a and Mostafa. H. Ammar b a Department of Computer Science University of California, Santa Barbara Santa Barbara, CA 93106-5110 b College of Computing Georgia Institute of...
On the Relative Complexities of Some Geometric Problems (2007)
) Jeff Erickson y 1 Introduction We consider a number of problems whose best known algorithms run in roughly O(n 4=3 ) time. While it is generally believed that these algorithms are optimal, at least...
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms (2007)
Exte Nd Ed, Frank Dehne, Wolfgang Dittrich, David Hutchinson, Anil Maheshwari
Frank Dehne 2 Wolfgang Dittrich 3 David Hutchinson 2;4 Anil Maheshwari 2;4 July 30, 1998 Abstract Block-wise access to data is a central theme in the design of efficient external memory (EM)...
Long-Lived Renaming Made Adaptive (2007)
Exte Nd 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...
Strengthening Lagrangian Bounds for the MAX-SAT Problem (2007)
Exte Nd Ed, Paolo Nobili, Antonio Sassano
) Paolo Nobili 1 , Antonio Sassano 2 1 Istituto di Analisi dei Sistemi ed Informatica, CNR-Roma, ITALY. Email: nobili@iasi.rm.cnr.it 2 Dipartimento di Informatica e Sistemistica, Universit`a di Roma...
Mendler-Style Inductive Types, Categorically (2007)
Exte Nd Ed, Tarmo Uustalu, Varmo Vene
Tarmo Uustalu 1 and Varmo Vene 2 1 Dept. of Teleinformatics, Royal Institute of Technology Electrum 204, SE-164 40 Kista, Sweden; tarmo@it.kth.se 2 Inst. of Computer Science, University of Tartu J....
A Formal Treatment of Remotely Keyed Encryption (2007)
Exte Nd 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...
Tutoring Strategies in Game-Tree Search (2007)
) HIROYUKI IIDA, YOSHIYUKI KOTANI, AND JOS W. H. M. UITERWIJK Introduction. According to the analysis of grandmaster-like strategies in Shogi [Iida and Uiterwijk 1993], it is important for a teacher,...
Querying Very Large Multi-dimensional Datasets in ADR - (2007)
Exte Nd Ed, Tahsin Kurc Y, Chialin Chang Y, Renato Ferreira Y, Alan Sussman Y, Joel Saltz Y
# Tahsin Kurc y , Chialin Chang y , Renato Ferreira y , Alan Sussman y , Joel Saltz y+ y Institute for Advanced Computer Studies and Dept. of Computer Science University of Maryland College Park, MD...
Quantitative Computation by Hilbert Machines (2007)
) Herbert Wiklicky herbert@cs.city.ac.uk City University London Northampton Square London EC1V OHB Abstract. In order to extend classical models of computing with symbols we introduce a model for...
A Discrete Strategy Improvement Algorithm for Solving Parity Games (2007)
) Jens Voge 1;? and Marcin Jurdzinski 2;?? 1 Lehrstuhl fur Informatik VII RWTH Aachen, D-52056 Aachen, Germany voege@informatik.rwth-aachen.de 2 BRICS ? ? ? Department of Computer Science,...
Completeness Results for Linear Logic on Petri Nets (2007)
Exte Nd Ed, Uffe Engberg, Glynn Winskel, Ny Munkegade
) Uffe Engberg Glynn Winskel Computer Science Department Aarhus University Ny Munkegade DK-8000 Aarhus C, Denmark Abstract Completeness is shown for several versions of Girard's linear logic...
Distributed control for PARIS (2007)
Exte Nd Ed, Baruch Awerbuch, Israel Cidon, Inder Gopal, Marc Kaplan, Shay Kutten
Baruch Awerbuch Israel Cidon y Inder Gopal yz Marc Kaplan yx Shay Kutten y Abstract We describe the control protocols of the PARIS experimental network. This high bandwidth network for integrated...
Exte Nd 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...
Strong Normalization for all-style (2007)
Exte Nd Ed, Jean-baptiste Joinet, Harold Schellinx, Mathematisch Instituut
Jean-Baptiste Joinet ? , Harold Schellinx ?? , Lorenzo Tortora de Falco ??? ' Equipe de Logique Math'ematique, Universit'e Paris VII Mathematisch Instituut, Universiteit Utrecht...
Exte Nd Ed, Pankaj K. Agarwal, Lars Arge, Je Erickson Z
) Pankaj K. Agarwal Lars Arge y Jeff Erickson z Submitted to 19th ACM Symposium on Principles of Database Systems. November 8, 1999 Abstract We propose three indexing schemes for storing a set S of N...
Optimal Resiliency against Mobile Faults (2007)
Exte Nd Ed, Harry Buhrman, Juan A. Garay, Jaap-henk Hoepman
) Harry Buhrman Juan A. Garay y Jaap-Henk Hoepman CWI IBM T.J. Watson Research Center CWI P.O. Box 94070 P.O. Box 704 P.O. Box 94070 1090 GB Amsterdam Yorktown Heights, NY 10598 1090 GB Amsterdam The...
An Approach to Flexible Forms of Proof Control for a First-Order Inductive Theorem Prover (2007)
) Ulrich Kuhler FB Informatik, Universitat Kaiserslautern, D-67653 Kaiserslautern, Germany kuehler@informatik.uni-kl.de Abstract. We propose an approach to the problem of proof control for our new...
Exte Nd Ed, John Kelsey, Bruce Schneier, David Wagner
) Chris Hall 1 , John Kelsey 1 , Bruce Schneier 1 , and David Wagner 2 1 Counterpane Systems 101 E. Minnehaha Pkwy Minneapolis, MN 55419 (612) 823-1098 fhall,kelsey,schneierg@counterpane.com 2 U.C....
Transient Fault Detectors (2007)
Exte Nd Ed, Joffroy Beauquier, Shlomi Dolev
) Joffroy Beauquier 1 Sylvie Delaet 1 Shlomi Dolev 2? S'ebastien Tixeuil 1 1 Laboratoire de Recherche en Informatique, Batiment 490, Universit'e de Paris Sud, F91405 Orsay Cedex, France....
Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (2007)
Exte Nd Ed, Jeff Edmonds, Donald D. Chinn, Tim Brecht, Xiaotie Deng
Jeff Edmonds y Donald D. Chinn y Tim Brecht y Xiaotie Deng y Department of Computer Science York University North York, ONT M3J 1P3 Abstract A multiprocessor system is unlikely to have access to...
A Typed Lambda Calculus of Objects (2007)
) Luigi Liquori 1 and Giuseppe Castagna 2 1 Dipartimento d'Informatica, Universit a di Torino C.so Svizzera 185, 10149 Torino, Italy 2 CNRS, LIENS-DMI, Ecole Normale Sup erieure, 45 rue...
Fast, Long-Lived Renaming (2007)
Exte Nd 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 April 1994 Abstract We consider wait-free...
A Generic Algorithm for CLP Analysis (2007)
Exte Nd Ed, Extended Abstract, Nevin Heintze, Joxan Jaffar
) Nevin Heintze y and Joxan Jaffar z June 13, 1995 Logic program analyzers typically employ abstract interpretation and consist of two main components: an abstract domain and a generic iterative...
SPEC - A Unified Approach to Modularity, Parametrisation and Views in Attributations (2007)
) Burkhart Wolff 1. Introduction This paper is an extended abstract of [Wolff 94a], whose purpose is twofold: Firstly, it attempts to generalise the notion of "attribute grammar" to the...
Experience with Architectures for Supporting IP Multicast over ATM (2007)
) Rajesh R. Talpade (Georgia Tech) Grenville J. Armitage (Bellcore) Mostafa H. Ammar (Georgia Tech) ftaddy, ammarg@cc.gatech.edu gja@thumper.bellcore.com April 15, 1996 Abstract Two basic techniques...
The Magic Words Are Squeamish Ossifrage (2007)
Exte Nd Ed, Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul C. Leyl
Derek Atkins 1 , Michael Graff 2 , Arjen K. Lenstra 3 , Paul C. Leyland 4 1 12 Rindge Avenue, Cambridge, MA 02140, U. S. A. E-mail: warlord@mit.edu 2 Iowa State University, 215 Durham Center, Ames,...
: A Butterfly-topology Parallel GA as A Function Optimizer (2007)
Exte Nd Ed, Fattaneh Taghiyareh, Hiroshi Nagahashi
Fattaneh Taghiyareh and Hiroshi Nagahashi Interdisciplinary Graduate School of Science and Engineering Tokyo Institute of Technology Genetic algorithms (GAs) are receiving increased attention in...
Smallest Enclosing Cylinders (2007)
Exte Nd Ed, Elmar Schomer, Jurgen Sellen, Marek Teichmann, Chee Yap
Elmar Schomer Jurgen Sellen y Marek Teichmann z Chee Yap x August 2, 1995 Abstract This paper addresses the complexity of computing the smallest-radius infinite cylinder that encloses an input set of...
Unifying Verification Paradigms (2007)
) ? Appears in the Proceedings of FTRTFT'96, LNCS 1135 Natarajan Shankar Computer Science Laboratory SRI International Menlo Park CA 94025 USA shankar@csl.sri.com URL:...
Experience with Architectures for Supporting IP Multicast over ATM (2007)
) Rajesh R. Talpade (Georgia Tech) Grenville J. Armitage (Bellcore) Mostafa H. Ammar (Georgia Tech) ftaddy, ammarg@cc.gatech.edu gja@thumper.bellcore.com August 13, 1996 Abstract Two basic techniques...
Perfectly-Secure Dynamic-Conference Key Distribution (2007)
Abstract. A conference key (key) distribution scheme is a method to distribute some pieces of information among a set of users is such a way each group (pair) of users can compute a common key to use...
A Theory of Recursive Domains with Applications to Concurrency (2007)
Exte Nd Ed, Gian Luca Cattani, Marcelo Fiore, Glynn Winskel
) Gian Luca Cattani 1 , Marcelo Fiore 2; , Glynn Winskel 1 1 BRICS y , University of Aarhus, Denmark 2 COGS, University of Sussex, UK Abstract We develop a 2-categorical theory for recursively...
Extending PROMELA and Spin for Real--Time (2007)
Exte Nd Ed, Stavros Tripakis, Costas Courcoubetis
Stavros Tripakis 1 and Costas Courcoubetis 1 ? Department of Computer Science, University of Crete, Heraklion, Greece, and Institute of Computer Science, FORTH Abstract. The efficient representation...
Towards Highly Available Three-Tier Monitoring Applications (2007)
Exte Nd Ed, David Breitg, Gleb Shaviner, Danny Dolev
David Breitgand, Gleb Shaviner, and Danny Dolev School of Computer Science and Engineering, The Hebrew University of Jerusalem, Givat-Ram 91904, Jerusalem E-Mail: {davb, gleb, dolev}@cs.huji.ac.il...
Deterministic Resource Discovery in Distributed Networks (2007)
Exte Nd Ed, Shay Kutten, David Peleg
Shay Kutten Technion David Peleg Weizmann Institute Uzi Vishkin Univ. of Maryland & Technion ABSTRACT Leighton and Lewin. They developed a number of algorithms for the problem in the weakly...
Faster Algorithms for k-Medians in Trees (2007)
Exte Nd Ed, Robert Benkoczi, Binay Bhattacharya, Marek Chrobak, Wojciech Rytter
Robert Benkoczi , Binay Bhattacharya , Marek Chrobak , Lawrence L.
Cache Cookies for Browser Authentication (2006)
Exte Nd Ed, Ari Juels, Markus Jakobsson, Tom N. Jagatic
Ari Juels Markus Jakobsson Tom N. Jagatic RSA Laboratories and Indiana University and Indiana University RavenWhite Inc. RavenWhite Inc.
Towards a Theory of Data Entanglement (2004)
Exte Nd Ed, James Aspnes, Joan Feigenbaum, R Yampolskiy, Sheng Zhong
We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-or-nothing integrity (AONI) that binds the users' data in a way that...
The Complexity of Games on Highly Regular Graphs (2004)
Exte Nd Ed, Konstantinos Daskalakis, Christos H. Papadimitriou
Konstantinos Daskalakis # Christos H. Papadimitriou + November 18, 2004 Abstract We study from the complexity point of view the problem of finding equilibria in games defined by highly regular graphs...
A Static Analyzer for Large Safety-Critical Software (2003)
Exte Nd Ed, Bruno Blanchet, Patrick Cousot, Radhia Cousot, J Feret, Laurent Mauborgne, ...
Bruno Blanchet # Patrick Cousot Radhia Cousot # J er ome Feret Laurent Mauborgne Antoine Min e David Monniaux # Xavier Rival ABSTRACT We show that abstract interpretation-based static program...
A Static Analyzer for Large Safety-Critical Software (2003)
Exte Nd Ed, Bruno Blanchet, Patrick Cousot, Radhia Cousot, Jérôme Feret, Laurent Mauborgne, ...
Bruno Blanchet # Patrick Cousot Radhia Cousot # J er ome Feret Laurent Mauborgne Antoine Min e David Monniaux # Xavier Rival ABSTRACT We show that abstract interpretation-based static program...
A Logic for Reasoning about Digital Rights (2002)
Exte Nd Ed, Riccardo Pucella, Vicky Weissman
Riccardo Pucella Department of Computer Science Cornell University Ithaca, NY 14853 riccardo@cs.cornell.edu Vicky Weissman Department of Computer Science Cornell University Ithaca, NY 14853...
Computing in Totally Anonymous Asynchronous Shared Memory Systems (2002)
Exte Nd Ed, Hagit Attiya, Alla Gorbach, Shlomo Moran
) Hagit Attiya ? Alla Gorbach ?? and Shlomo Moran ??? Department of Computer Science, The Technion Abstract. In the totally anonymous shared memory model of asynchronous distributed computing,...
Protecting People Location Information (2002)
Urs Hengartner and Peter Steenkiste ### # Department of Computer Science Department of Electrical and Computer Engineering Carnegie Mellon University uhengart,prs # @cs.cmu.edu 1
Games on Graphs and Sequentially Realizable Functionals (2002)
Exte Nd Ed, Martin Hyland, Andrea Schalk
Martin Hyland DPMMS Centre for Mathematical Sciences Wilberforce Road, Cambridge, CB3 0WB, UK M.Hyland@dpmms.cam.ac.uk Andrea Schalk Department of Computer Science University of Manchester Oxford...
Using Aspect-GAMMA in the Design of Embedded Systems (2002)
Exte Nd Ed, Mohammadreza Mousavi, Giovanni Russello, Michel Chaudron, Michel Reniers, Twan Basten, ...
MohammadReza Mousavi, Giovanni Russello, Michel Chaudron, Michel Reniers, Twan Basten Technische Universiteit Eindhoven (TU/e) P.O. Box 513, 5600 MB Eindhoven, The Netherlands Angelo Corsaro, Sandeep...
Compact Labeling Schemes for Ancestor Queries (2001)
Exte Nd Ed, Serge Abiteboul, Haim Kaplan, Tova Milo
Serge Abiteboul Haim Kaplan Tova Milo Abstract We consider the following problem. Give a rooted tree T , label the nodes of T in the most compact way such that given the labels of two nodes one can...
Coding Recursion a la Mendler (2000)
Exte Nd Ed, Tarmo Uustalu, Varmo Vene
Tarmo Uustalu 1? and Varmo Vene 2 1 Inst. of Cybernetics, Tallinn Technical University Akadeemia tee 21, EE-126 18 Tallinn, Estonia; tarmo@cs.ioc.ee 2 Inst. of Computer Science, University of Tartu...
The Impact of Write Back on Cache Performance (2000)
Exte Nd Ed, Daniel Kroening, Silvia M. Mueller
Daniel Kroening # and Silvia M. Mueller Computer Science Department Universitaet des Saarlandes, 66123 Saarbruecken, Germany email: kroening@handshake.de, smueller@cs.uni-sb.de, Tel.: (+49)...
Distributed Models and Algorithms for Survivability in Network Routing (2000)
Exte Nd Ed, Fred S. Annexstein, Kennth A. Berman
Fred S. Annexstein and Kennth A. Berman Department of ECE & Computer Science University of Cincinnati Cincinnati, OH 45221 ffred.annexstein, ken.bermang@uc.edu Abstract We introduce a natural...
Improved Algorithms for Theory Revision with Queries (2000)
Exte Nd Ed, Judy Goldsmith, Robert H. Sloan
Judy Goldsmith University of Kentucky 763 Anderson Hall Lexington, KY 40506 goldsmit@cs.uky.edu Robert H. Sloan Dept. of EE & Comp. Sci. U. Illinois at Chicago 851 S. Morgan St. Rm 1120 Chicago,...
CAS-DSM: A Compiler Assisted Software DSM (1999)
Manoj N.P. y and R. Govindarajany z yDepartment of Computer Science and Automation zSupercomputer Education and Research Centre Indian Institute of Science Bangalore 560 012, INDIA....
Recursive Types in Games: Axiomatics and Process Representation (1998)
) Marcelo Fiore COGS, University of Sussex Kohei Honda LFCS, University of Edinburgh Abstract This paper presents two basic results on game-based semantics of FPC, a metalanguage with sums, products,...
Asynchronous Group Mutual Exclusion (1998)
) Yuh-Jzer Joung joung@ccms.ntu.edu.tw Department of Information Management National Taiwan University Taipei, Taiwan Abstract Mutual exclusion and concurrency are two fundamental and essentially...
A Wait-Free Classification of Loop Agreement Tasks (1998)
Exte Nd Ed, Maurice Herlihy, Sergio Rajsbaum
) ? Maurice Herlihy 1 and Sergio Rajsbaum 2 1 Computer Science Department, Brown University, Providence RI 02912, USA, herlihy@cs.brown.edu 2 Instituto de Matem'aticas, U.N.A.M., Ciudad...
Spatial Codes and the Hardness of String Folding Problems (1998)
Exte Nd Ed, Ashwin Nayak, Alistair Sinclair, Uri Zwick
) Ashwin Nayak Alistair Sinclair y Uri Zwick z Abstract We present the first proof of NP-hardness (under randomized polynomial time reductions) for string folding problems over a finite alphabet. All...
Communication-Optimal Parallel Minimum Spanning Tree Algorithms (1998)
Exte Nd Ed, Micah Adler, Wolfgang Dittrich, Ben Juurlink, Ingo Rieping
Micah Adler 1 Wolfgang Dittrich 2 Ben Juurlink 3 Miros/law Kuty/lowski 4 Ingo Rieping 3 Abstract Lower and upper bounds for finding a minimum spanning tree (MST) in a weighted undirected graph on the...
Security of Blind Digital Signatures (1997)
Exte Nd Ed, Ari Juels, Michael Luby, Rafail Ostrovsky
) Ari Juels 1? Michael Luby 2 Rafail Ostrovsky 3 1 RSA Laboratories. Email: ari@rsa.com. 2 Digital Equipment Corporation, 130 Lytton Avenue, Palo Alto, CA 94301-1044. Email: luby@pa.dec.com. 3 Bell...
A Simple Algorithmically Reasoned Characterization of Wait-free Computations (1997)
Exte Nd Ed, Elizabeth Borowsky, Eli Gafni
) Elizabeth Borowsky (borowsky@hpl.hp.com) Eli Gafni (eli@cs.ucla.edu) Computer Science Department University of California, Los Angeles Los Angeles, CA 90024 U.S.A. Abstract This paper introduces...
Undecidability Results for low complexity degree structures (1997)
Rod Downey , Victoria University of Wellington New Zealand Andr'e Nies y The University of Chicago Chicago Illinois 60637 USA Abstract We prove that the theory of EXPTIME degrees with respect to...
Local Model Checking for Value-passing Processes (1997)
Exte Nd Ed, J. Rathke, M. Hennessy
) 1 J. Rathke and M. Hennessy Dept. of Cognitive and Computing Science, University of Sussex, Brighton BN1 9QH, United Kingdom. Telephone: (+44) 1273 606755 Fax: (+44) 1273 671320 Email: fjulianr,...
A Signature Technique for Similarity-Based Queries (1997)
Exte Nd Ed, C. Faloutsos, H. V. Jagadish, A. O. Mendelzon, T. Milo
) C. Faloutsos Univ. of Maryland christos@cs.umd.edu H. V. Jagadish AT&T Labs jag@research.att.com A. O. Mendelzon Univ. of Toronto mendel@db.toronto.edu T. Milo Tel Aviv Univ....
Limitations On Inductive Learning (1997)
Exte Nd Ed, Thomas G. Dietterich
) Thomas G. Dietterich Department of Computer Science Oregon State University Corvallis, OR 97331 tgd@cs.orst.edu ABSTRACT This paper explores the proposition that inductive learning from examples is...
Exte Nd Ed, Bobby Krupczak, Mostafa Ammar, Ken Calvert
) Bobby Krupczak, Mostafa Ammar, Ken Calvert College Of Computing, Georgia Institute of Technology Atlanta, GA 30332-0280 1 Introduction Protocol software can be difficult, cumbersome, and expensive...
On Extracting Randomness From Weak Random Sources (1996)
Amnon Ta-Shma y Abstract We deal with the problem of extracting as much randomness as possible from a defective random source. We devise a new tool, a "merger", which is a function that...
Efficient Algorithms for Lempel-Ziv Encoding (1996)
Exte Nd Ed, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter
) 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...
Improved Scheduling Algorithms for Minsum Criteria (1996)
Exte Nd 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...
Linear vs. Order Constraint Queries Over Rational Databases (1996)
Exte Nd Ed, Alexei P. Stolboushkin, Michael A. Taitslin
) Alexei P. Stolboushkin Department of Mathematics UCLA Los Angeles, CA 90024-1555 aps@math.ucla.edu Michael A. Taitslin y Department of Computer Science Tver State University Tver, Russia 170000...
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence (1996)
Exte Nd Ed, Miklos Ajtai, Cynthia Dwork
) Miklos Ajtai Cynthia Dwork May 2, 1997 Abstract We present a probabilistic public key cryptosystem which is secure unless the worst case of the following lattice problem can be solved in polynomial...
A Stable Model Semantics for Behavioral Inheritance in Deductive Object Oriented Languages (1995)
Exte Nd Ed, Michele Bugliesi, Hasan M. Jamil
) Michele Bugliesi 1 Hasan M. Jamil 2 Dip. di Matematica Pura ed Applicata Dept. of Computer Science Universit`a di Padova, Italy Concordia University, Canada michele@goedel.math.unipd.it...
Efficient Stopping Rules for Markov Chains (1995)
) L' aszl' o Lov' asz Dept. of Computer Science, Yale University, New Haven CT 06510; lovasz@cs.yale.edu Peter Winkler AT&T Bell Laboratories 2D-147, Murray Hill NJ 07974;...
Time Bounds for Mutual Exclusion and Related Problems (1994)
Exte Nd Ed, Jae-heon Yang, James H. Anderson
) Jae-Heon Yang Department of Computer Science The University of Maryland College Park, Maryland 20742-3255 James H. Anderson Department of Computer Science The University of North Carolina Chapel...
A Logic for Encapsulation in Object Oriented Languages (1994)
Exte Nd Ed, Michele Bugliesi, Hasan M. Jamil
) Michele Bugliesi 1 Dip. di Matematica Pura ed Applicata, Univ. di Padova Via Belzoni 7, I-35131 Padova, Italy e-mail: michele@goedel.math.unipd.it Hasan M. Jamil 2 Department of Computer Science,...
Optimal Nearly-Similar Polygon Stabbers of Convex Polygons (1994)
Exte Nd Ed, Paul Colley, Henk Meijer
Paul Colley colley@qucis.queensu.ca Henk Meijer henk@qucis.queensu.ca David Rappaport daver@qucis.queensu.ca Department of Computer and Information Science Queen's University Kingston, Ontario,...
Set Based Analysis of ML Programs (1993)
Exte Nd Ed, Nevin Heintze, Um Cmu-cs-fox
) NEVIN HEINTZE July 1993 CMU-CS-93-193 (Also appears as Fox Memorandum CMU-CS-FOX-93-03.) School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 Abstract Reasoning about a...
One-Way Functions are Essential for Non-Trivial Zero-Knowledge (1993)
Exte Nd Ed, Rafail Ostrovsky, Avi Wigderson
) Rafail Ostrovsky y Avi Wigderson z TR-93-073 Novemeber, 1993 Abstract It was known that if one-way functions exist, then there are zero-knowledge proofs for every language in PSPACE. We prove that...
Matching Nuts and Bolts (1993)
Exte Nd Ed, Noga Alon, Manuel Blum, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky TR-93-075 Novemeber, 1993 Abstract We describe a procedure which may be helpful to any disorganized carpenter...
A Fast Parallel Conservative Garbage Collector for Concurrent Object-Oriented Systems (1991)
Exte Nd Ed, Satoshi Matsuoka, Akinori Yonezawa
Satoshi Matsuoka, Shin'ichi Furuso, and Akinori Yonezawa Department of Information Science The University of Tokyo fmatsu,furuso,yonezawag@is.s.u-tokyo.ac.jp Abstract In future OO-OS, multiple...
Resource-bounded Continuity and Sequentiality for Type-two Functionals (1991)
Exte Nd Ed, Samuel R. Buss, Bruce M. Kapron
Samuel R. Buss Department of Mathematics University of California, San Diego La Jolla, CA 92093-0112 sbuss@ucsd.edu Bruce M. Kapron Computer Science Department University of Victoria Victoria BC...
How To Withstand Mobile Virus Attacks (1991)
Exte Nd Ed, Rafail Ostrovsky, Moti Yung
Rafail Ostrovsky Moti Yung y Abstract We initiate a study of distributed adversarial model of computation in which faults are non-stationary and can move through the network, analogous to a spread of...
PERs Generalise Projections for Strictness Analysis (1990)
) Sebastian Hunt Department Of Computing Imperial College London SW7 2BZ Abstract We show how Wadler and Hughes's use of Scott projections to describe properties of functions ("Projections...
Robust Learning with Infinite Additional Information
Exte Nd Ed, Susanne Kaufmann, Frank Stephan
) Appeared In: EuroCOLT'97, LNCS 1208, 316--330, Springer-Verlag, 1997. Susanne Kaufmann 1 and Frank Stephan 2 ?? 1 Interactive Systems Laboratories, Am Fasanengarten 5, Universitat Karlsruhe,...