Arrow Research search

Author name cluster

Mark N. Wegman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
1 author row

Possible papers

8

FOCS Conference 1988 Conference Paper

Learning Probabilistic Prediction Functions (Extended Abstract)

  • Alfredo De Santis
  • George Markowsky
  • Mark N. Wegman

The question of how to learn rules, when those rules make probabilistic statements about the future, is considered. Issues are discussed that arise when attempting to determine what a good prediction function is, when those prediction functions make probabilistic assumptions. Learning has at least two purposes: to enable the learner to make predictions in the future and to satisfy intellectual curiosity as to the underlying cause of a process. Two results related to these distinct goals are given. In both cases, the inputs are a countable collection of functions which make probabilistic statements about a sequence of events. One of the results shows how to find one of the functions, which generated the sequence, the other result allows to do as well in terms of predicting events as the best of the collection. In both cases the results are obtained by evaluating a function based on a tradeoff between its simplicity and the accuracy of its predictions. >

Details

FOCS Conference 1980 Conference Paper

Parsing for Structural Editors (Extended Abstract)

  • Mark N. Wegman

We present techniques that enable the construction of an algorithm capable of re-parsing a string after another string has been inserted into it. Let M be the minimal, under certain restrictions, number of changes which must be made to the parse tree to reflect the insertions. Then the algorithm we present should work in no more time than M times a log factor of the height of the parse tree. The grammars we allow include all LR(1) grammars.

Details

FOCS Conference 1979 Conference Paper

New Classes and Applications of Hash Functions

  • Mark N. Wegman
  • Larry Carter

In this paper we exhibit several new classes of hash functions with certain desirable properties, and introduce two novel applications for hashing which make use of these functions. One class of functions is small, yet is almost universal2. If the functions hash n-bit long names into m-bit indices, then specifying a member of the class requires only O((m + log2log2(n)) log2(n)) bits as compared to O(n) bits for earlier techniques. For long names, this is about a factor of m larger than the lower bound of m+log2n-log2m bits. An application of this class is a provably secure authentication techniques for sending messages over insecure lines. A second class of functions satisfies a much stronger property than universal2. We present the application of testing sets for equality. The authentication technique allows the receiver to be certain that a message is genuine. An 'enemy' - even one with infinite computer resources - cannot forge or modify a message without detection. The set equality technique allows the the operations 'add member to set', 'delete member from set' and 'test two sets for equality' to be performed in expected constant time and with less than a specified probability of error.

Details

MFCS Conference 1978 Conference Paper

Analysis of a Universal Class of Hash Functions

  • George Markowsky
  • Larry Carter
  • Mark N. Wegman

Abstract In this paper we use linear algebraic methods to analyze the performance of several classes of hash functions, including the class H 2 presented by Carter and Wegman [2]. Suppose H is a suitable class, the hash functions in H map A to B, S is any subset of A whose size is equal to that of B, and x is any element of A. We show that the probability of choosing a function from H which maps x to the same value as more than t other elements of S is no greater than min ( 1 /t 2, 11 /t 4 ). Consider a database storage and retrieval system implemented using hashing and a linked list collision resolution strategy. A corollary of the main result is that the probability that the system would perform more than t times more slowly than expected is no greater than min( 1 /t 2, 11 /t 4 ). The "performance" being considered can be either the number of memory references required to process any individual request or the number required to process an arbitrary sequence of requests. Notice that these results do not assume that the requests to the database are random or uniformly distributed. Instead, the averaging is done over the possible choices of the actual hash function from H. Since the system designer can be sure that this choice is made randomly, the probabilities given hold for any input. It is also shown that the bound on poor performance when balanced trees are used in place of linked lists is approximately min (1/(4 t ), 11/(16 t )). The formulas are generalized to any size S.

Details