Integration of Document Detection and Information Extraction

We have conducted a number of experiments to evaluate various modes of building an integrated detection/extraction system. The experiments were performed using SMART system as baseline. The goal was to determine if advanced information extraction methods can improve recall and precision of document detection. We identified the following two modes of integration:I. Extraction to Detection: broad-coverage extraction1. Extraction step: identify concepts for indexing2. Detection step 1: low recall, high initial precision3. Detection step 2: automatic relevance feedback using top N retrieved documents to regain recall.II. Detection to Extraction: query-specific extraction1. Detection step 1: high recall, low precision run2. Extraction step: learn concept(s) from query and retrieved subcollection3. Detection step 2: re-rank the subcollection to increase precisionOur integration effort concentrated on mode I, and the following issues:1. use of shallow but fast NLP for phrase extractions and disambiguation in place of a full syntactic parser2. use existing MUC-6 extraction capabilities to index a retrieval collection3. mixed Boolean/soft match retrieval model4. create a Universal Spotter algorithm for learning arbitrary concepts

1. Extraction step: identify concepts for indexing 2. Detection step 1: low recall, high initial precision 3. Detection step 2: automatic relevance feedback using top N retrieved documents to regain recall.
I1. Detection to Extraction: query-specific extraction 1.Detection step 1: high recall, low precision run 2.Extraction step: learn concept(s) from query and retrieved subcollection 3.Detection step 2: re-rank the subcollection to increase precision Our integration effort concentrated on mode I, and the following issues: 1.use of shallow but fast NLP for phrase extractions and disambiguation in place of a full syntactic parser 2.use existing MUC-6 extraction capabilities to index a retrieval collection 3.mixed Boolean/soft match retrieval model 4.create a Universal Spotter algorithm for learning arbitrary concepts

LEXlCO-SEMANTIC PATTERN MATCHING FOR SHALLOW NLP
The lexico-semantic pattern matching method allows for capturing of word sequences in text using a simple pattern language that can be compiled into a set of non-deterministic finite automata. Each automoton represents a single rule within the language, with several related rules forming a package. As a result of matching a rule against the input, a series of variables within the rule are bound to lexical elements in text. These bindings are subsequently used to generate single-word and/or multiple-word terms for indexing.
Long phrasal terms are decomposed into pairs in two phases as follows. In the first phase, only unambiguous pairs are collected, while all longer and potentially structurally ambiguous noun phrases are passed to the second phase. In the second phase, the distributional statistics gathered in the first phase are used to predict the strength of alternative two-word sub-components within long phrases. For example, we may have multiple unambiguous occurrences of "insider trading", while very few of "trading case". At the same time, there are numerous phrases such as =insider trading case", =insider trading legislation", etc., where the pair =insider trading" remains stable while the other elements get changed, and significantly fewer cases where, say, "trading case" is constant and the other words change.
The experiments performed on a subset of U.S. PTO's patent database show healthy 10%+ increase in average precision over baseline SMART system. The average precision (11-point) has increased from 49% SMART baseline on the test sample to 56%. Precision at 5 top retrieved documents jumped from 48% to 52%. We also noticed that phrase disambiguation step was critical for improved precision.

INDEXING WITH MUC-6 CONCEPTS
In these experiments we used actual MUC organization and people name spotter (from Lockheed Martin) to annotate and index a subset of TREC-4 collection. We selected 17 queries out of 250 TREC topics which explicitely mentioned some organizations by names. The following observations were made: 1.Different queries require different concepts to be spotted: concepts that are universal enough to be important in most domains are hard to find, or not discriminating enough. 2.These differences are frequently queryspecific, not just domain-specific, which makes MUC-style extraction impractical 3.The role that a concept plays in a query can affect its usefullness in retrieval: concepts found in focus appear to be radically more discriminating than those found in background roles.
Initial results show that targeted concept indexing can be extremely effective, however, random annotation may in fact cause loss of performance. Overall, the average precision improved by only 3%; however, some queries, namely those where the indexed concepts were in focus roles, benefited dramatically. For example, the query about Mitsubishi has gained about 25% in precision over SMART baseline (from 42% to 52%).
Typical results are summarized in the

MIXED BOOLEAN/SOFT RETRIEVAL MODEL
We allow strict-match terms to be included in the search queries in a specially designated field. The hard/soft query mechanism allows a user to specify either in interactive or batch mode a boolean type query which will restrict documents returned by a vector space model match. Documents not satisfying the query will be deemed to be nonrelevant for the query.
A two-pass retrieval has been implemented in SMART to allow proper interpretations of such queries. In interactive mode a normal vector query can be entered using 'run' command. When the first results are returned using 'boolean' will place you in editor mode (similar to run). Construct the query and terminate the query with a period on a line by itself. The documents returned by the latest 'run' command are filtered and only those satisfying the query are redisplayed. Using 'more' will always retrieve 'num_wanted' unless there are insufficient documents remaining that are relevant to the initial vector query.

RECOMMENDATIONS FOR AN INTEGRATED SYSTEM
The following were determined to be crucial in building an integrated extraction/detection system: 1. A large variety of extraction capabilities, best if could be generated rapidly on an ad-hoc basis.
2. Rapid discource analysis for role determination of semantically significant terms 3. The need for well-defined equivalence relation on annotations produced by an extraction system.

UNIVERSAL SPOTTER
Identifying concepts in natural language text is an important information extraction task. Depending upon the current information needs one may be interested in finding all references to people, locations, dates, organizations, companies, products, equipment, and so on. These concepts, along with their classification, can be used to index any given text for search or categorization purposes, to generate summaries, or to populate database records. However, automating the process of concept identification in unformatted text has not been an easy task. Various single-purpose spotters have been developed for specific types of concepts, including people names, company names, location names, dates, etc. but those were usually either hand crafted for particular applications or domains, or were heavily relying on apriori lexical clues, such as keywords (e.g., "Co.'), case (e.g., "John K. Big'), predicatable format (e.g., 123 Maple Street), or a combination of thereof. This makes creation and extension of such spotters an arduous manual job. Other, less salient entities, such as products, equipment, foodstuff, or generic references of any kind (e.g., "a Japanese automaker') could only be identified if a sufficiently detailed domain model was available.
We take a somewhat different approach to identify various types of text entities, both generic and specific, without a detailed understanding of the text domain, and relying instead on a combination of shallow linguistic processing (to identify candidate lexical entities), statistical knowledge acquisition, unsupervised learning techniques, and possibly broad (universal but often shallow) knowledge sources, such as on-line dictionaries (e.g., WordNet, Comlex, OALD, etc.). Our method moves beyond the traditional name spotters and towards a universal spotter where the requirements on what to spot can be specified as input parameters, and a specificpurpose spotter could be generated automatically. In this paper, we describe a method of creating spotters for entities of a specified category given only initial seed examples, and using an unsupervised learning process to discover rules for finding more instances of the concept. At this time we place no limit on what kind of things one may want to build a spotter for, although our experiments thus far concentrated on entities customarily referred to with noun phrases, e.g., equipment (e.g., =gas turbine assembly"), tools (e.g., =adjustable wrench"), products (e.g., "canned soup", "Arm Hammer baking soda"), organizations (e.g., American Medical Association), locations (e.g., Albany County Airport), people (e.g., Bill Clinton), and so on. We view the semantic categorization problem as a case of disambiguation, where for each lexical entity considered (words, phrases, N-grams), a binary decision has to be made whether or not it is an instance of the semantic type we are interested in. The problem of semantic tagging is thus reduced to the problem of partitioning the space of lexical entities into those that are used in the desired sense, and those that are not. We should note here that it is acceptable for homonym entities to have different classification depending upon the context in which they are used. Just as the word "'bank" can be assigned different senses in different contexts, so can" Boeing 777 jet" be once a product, and another time an equipment and not a product, depending upon the context. Other entities may be less context dependent (e.g., company names) if their definitions are based on internal context (e.g., "ends with Co.") as opposed to external context (e.g., "followed by manufactures"), or if they lack negative contexts.
The user provides the initial information (seed) about what kind of things he wishes to identify in text. This information should be in a form of a typical lexical context in which the entities to be spotted occur, e.g., "the name ends with Co.", or "to the right of produced or made", or "'to the right of maker of", and so forth, or simply by listing or highlighting a number of examples in text. In addition, negative examples can be given, if known, to eliminate certain "obvious' exceptions, e.g., "not to the right of made for ", "not toothbrushes". Given a sufficiently large training corpus, an unsupervised learning process is initiated in which the system will: (1) generate initial context rules from the seed examples; (2) find further instances of the sought-after concept using the initial context while maximizing recall and precision; (3) find additional contexts in which these entities occur; and (4) expand the current context rules based on selected new contexts to find even more entities.
We present and evaluate preliminary results of creating spotters for organizations and products.

What do you want to find: seed selection
If we want to identify some things in a stream of text, we first need to learn how to distinguish them from other items. For example, company names are usually capitalized and often end with "Co.', "Corp.', "Inc.' and so forth. Place names, such as cities, are normally capitalized, sometimes are followed by a state abbreviation (as in Albany, NY ), and may be preceded by locative prepositions (e.g., in, at, from, to ). Products may have no distinctive lexical appearance, but they tend to be associated with verbs such as "produce', "manufacture', "make', "sell', etc., which in turn may involve a company name. Other concepts, such as equipment or materials, have few if any obvious associations with the surrounding text, and one may prefer just to point them out directly to the learning program. There are texts, e.g., technical manuals, where such specialized entities occur more often than elsewhere, and it may be advantagous to use these texts to derive spotters.
The seed can be obtained either by hand tagging some text or using a naive spotter that has high precision but presumably low recall. A naive spotter may contain simple contextual rules such as those mentioned above, e.g., for organizations: a noun phrases ending with "Co." or "Inc."; for products: a noun phrase following "manufacturer of", "producer of", or "retailer of". When such naive spotter is difficult to come by, one may resort to hand tagging. From seeds to spotters The seed should identify the sought-after entities with a high precision (though not necessarily 100%), however its recall is assumed to be low, or else we would already have a good spotter. Our task is now to increase the recall while maintaining (or even increase if possible) the precision.
We proceed by examining the lexical context in which the seed entities occur. In the simplest instance of this process we consider a context to consist of N words to the left of the seed and N words to the right of the seed, as well as the words in the seed itself. Each piece of significant contextual evidence is then weighted against its distribution in the balance of the training corpus. This in turn leads to selection of some contexts to serve as indicators of relevant entities, in other words, they become the initial rules of the emerging spotter.
As an example, let's consider building a spotter for company names, starting with seeds as illustrated in the following fragments (with seed contexts highlighted): Having "Co.", "Inc." to pick out "'Henry Kaufman Co." and "Gabelli Funds Inc." as seeds, we proceed to find new evidence in the training corpus, using an unsupervised learning process, and discover that "'chairman of" and "'president of" are very likely to precede company names. We expand our initial set of rules, which allows us to spot more companies: This evidence discovery can be repeated in a bootstrapping process by replacing the initial set of seeds with the new set of entities obtained from the last iteration. In the above example, we now have "Skandinaviska Enskilda Banken" and "the stateowned electronics giant Thomson S.A." in addition to the initial two names. A further iteration may add "S.A." and "'Banken" to the set of contextual rules, and so forth. In general, entities can be both added and deleted from the evolving set of examples, depending on how exactly the evidence is weighted and combined. The details are explained in the following sections.

Text preparation
In most cases the text needs to be preprocessed to isolate basic lexical tokens (words, abbreviations, symbols, annotations, etc), and structural units (sections, paragraphs, sentences) whenever applicable. In addition, part-of-speech tagging is usually desirable, in which case the tagger may need to be re-trained on a text sample to optimize its performance. Finally, a limited amount of lexical normalization, or stemming, may be performed. The entities we are looking for may be expressed by certain types of phrases. For example, people names are usually sequences of proper nouns, while equipment names are contained within noun phrases, e.g., "forward looking infrared radar'. We use part of speech information to delineate those sequences of lexical tokens that are likely to contain "our' entities. From then on we restrict any further processing on these sequences, and their contexts.
These preparatory steps are desirable since they reduce the amount of noise through which the learning process needs to plow, but they are not, strictly speaking, necessary. Further experiments are required to determine the level of preprocessing required to optimize the performance of the Universal Spotter.

Evidence items
The semantic categorization problem described here displays some parallels to the word sense disambiguation problem where homonym words need to be assigned to one of several possible senses. There are two important differences, however. First, in the semantic categorization problem, there is at least one open-ended category serving as a grab bag for all things non-relevant. This category may be hard, if not impossible, to describe by any finite set of rules. Second, unlike the word sense disambiguation where the items to be classified are known apriori, we attempt to accomplish two things at the same time: discover the items to be considered for categorization; actually decide if an item belongs to a given category, or falls outside of it. The categorization of a lexical token as belonging to a given semantic class is based upon the information provided by the words occurring in the token itself, as well as the words that precede and follow it in text. In addition, positional relationships among these words may be of importance.

Experiments and Results
We used the Universal Spotter to find organizations and products in a 7 MBytes corpus consisting of articles from the Wall Street Journal. First, we pre-processed the text with a part-ofspeech tagger and identified all simple noun groups to be used as candidate phrases. 10 articles were set aside and hand tagged as key for evaluation. Subsequently, seeds were constructed manually in form of contextual rules. For organizations, these initial rules had a 98% precision and 49% recall; for products, the corresponding numbers were 97% and 42%. No lexicon verification has been used in order to show more clearly the behavior the learning method itself (the performance can be enhanced by lexicon verification). The seeds that we used in our experiments are quite simple, perhaps too simple. Better seeds may be needed (possibly developed through an interaction with the user) to obtain strong results for some categories of concepts.
For organization tagging, the recall and precision results obtained after the fourth bootstrapping cycle are 90% and 95%, respectively. Examples of extracted organizations include: "the State Statistical Institute Istat", "Wertheim Schroder Co", "Skandinaviska Enskilda Banken", "Statistics Canada".
The results for products tagging are at 80% recall at 85% precision, and 75% recall at 90% precision. Examples of extracted products include: "the Mercury Grand Marquis and Ford Crown Victoria cars", "Chevrolet Prizm", "Pump shoe", "AS/400".


extfieldsofstudy:
Computer Science
Mathematics
Physics

s2fieldsofstudy:
Computer Science
Mathematics

text:
Collision-Free Hashing from Lattice Problems

In 1995, Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same construction can also be used to obtain collision-free hashing. This paper contains a self-contained proof sketch of Ajtai's result.

Introduction
In 1995, Ajtai described a problem that is hard on the average if some well-known lattice problems are hard to approximate in the worst case, and demonstrated how this problem can be used to construct one-way functions [1]. We show that Ajtai's method can also be used to construct families of collision-free hash functions. Furthermore, a slight modification of this construction yields families of functions which are both universal and collision-free.

The Construction
The construction is very simple. For security parameter n, we pick a random n×m matrix M with entries from Z q , where m and q are chosen so that n log q < m < q 2n 4 and q = O(n c ) for some constant c > 0 (e.g., m = n 2 , q = n 7 ). See Section 3 for a discussion of the choice of parameters. The hash function h M : {0, 1} m → Z n q is then defined, for s = s 1 s 2 · · · s m ∈ {0, 1} m , as where M i is the i th column of M . Notice that h M 's input is m-bit long, whereas its output is n log q bits long. Since we chose the parameters such that m > n log q, there are collisions in h M . As we will argue below, however, it is infeasible to find any of these collisions unless some well known lattice problems have good approximation in the worst case. It follows that, although it is easy to find solutions for the equations M s ≡ 0 (mod q), it seems hard to find binary solutions (i.e., a vector s ∈ {0, 1} m in the solution space). Remark. Using our notation, the candidate one-way function introduced by Ajtai is f (M, s) def = (M, h M (s)). We note that this function is regular (cf., [3]); that is, the number of preimage of any image is about the same. (Furthermore, for most M 's the number of pre-images under h M of almost all images is about the same.) To the best of our knowledge, it is easier (and more efficient) to construct a pseudo-random generator based on a regular one-way function than based on an arbitrary one-way function (cf., [3] and [4]).

A Modification
A family of hash functions is called universal if a function uniformly selected in the family maps every two images uniformly on its range in a pairwise indepedent manner [2]. To obtain a family of functions that is both universal and collisionfree, we slightly modify the foregoing construction. First we set q to be a prime of the desired size. Then, in addition to picking a random matrix M ∈ Z n×m q , we also pick a random vector r ∈ Z n q . The function h M,r : {0, 1} m → Z n q is then defined, for s = s 1 · · · s m ∈ {0, 1} m , as The modified construction resembles the standard construction of universal hash functions [2], with calculations done over Z q instead of over Z 2 .

Formal Setting
In this section we give a brief description of some well known lattice problems, outline Ajtai's reduction, and our version of it.

Lattices
Definition 1: Given a set of n linearly independent vectors in R n , denoted V = v 1 , · · · , v n , we define the lattice spanned by V as the set of all possible linear combinations of the v i 's with integral coefficients; that is, We call V the basis of the lattice L(V ). We say that a set of vectors, L ⊂ R n , is a lattice if there is a basis V such that L = L(V ).
It is convenient to view a lattice L in R n as a "tiling" of the space R n using small parallelepipeds, with the lattice points being the vertices of these parallelepipeds. The parallelepipeds themselves are spanned by some basis of L. We call the parallelepiped that are spanned by the "shortest basis of L" (the one whose vectors have the shortest Euclidean norm) the basic cells of the lattice L. See Figure 1 for an illustration of these terms in a simple lattice in R 2 .

R 2
A lattice in Tiling using the "basic-cells" Tiling using some other basis Computational problems regarding lattices. Finding "short vectors" (i.e., vectors with small Euclidean norm) in lattices is considered a hard problem. There are no known efficient algorithms to find, given an arbitrary basis of a lattice, either the shortest non-zero vector in the lattice, or another basis for the same lattice whose longest vector is as short as possible. No efficient algorithms are known for approximation versions of these problems as well. The approximation versions being considered here are the following: (W1) Given an arbitrary basis B of a lattice L in R n , approximate (up to a polynomial factor in n) the length of the shortest vector in L. (W2) Given an arbitrary basis B of a lattice L in R n , find another basis of L whose length is at most polynomially (in n) larger than that of the smallest basis of L (where the length of a basis is the length of its longest vector).
We choose 'W' for the foregoing notation to indicate that we will be interested in the worst-case complexity of these problems. The best known algorithms for these problems are the L 3 algorithm and Schnorr algorithm. The L 3 algorithm, due to Lenstra, Lenstra and Lovász [5] approximates these problems to within a ratio of 2 n/2 in the worst case, and Schnorr's algorithm [6] improves this to (1 + ε) n for any fixed ε > 0. Another problem, which can be shown to be equivalent to the above approximation problems (cf. [1]), is the following: (W3) Given an arbitrary basis B of a lattice L, find a set of n linearly independent lattice vectors, whose length is at most polynomially (in n) larger than the length of the smallest set of n linearly independent lattice vectors.
(Again, the length of a set of vectors is the length of its longest vector.) A few remarks about (W3) are in order: 1. Note that not every linearly independent set of n lattice points is a basis for that lattice. For example, if V = {v 1 , v 2 } span some lattice in R 2 , then the set {2v 1 , v 2 } is a linearly independent set of 2 vectors that does not span L(V ), since we cannot represent v 1 as an integral linear combination of 2v 1 and v 2 . 2. In the sequel we reduce the security of our construction to the difficulty of solving Problem (W3). It will be convenient to use the following notation: For a given polynomial Q(·), denote by (W3) Q the problem of approximating the smallest independent set in an n-dimensional lattice up to a factor of Q(n).

Ajtai's Reduction
In his paper Ajtai described the following problem: Problem (A1): For parameters n, m, q ∈ N such that n log q < m ≤ q 2n 4 and q = O(n c ), for some constant c > 0.
Here, we used 'A' (in the notation) to indicate that we will be interested in the average-case complexity of this problem. Ajtai proved the following theorem, reducing the worst-case complexity of (W3) to the average-case complexity of (A1).
Ajtai's Theorem [1]: Suppose that it is possible to solve a uniformly selected instance of Problem (A1) in expected T (n, m, q)-time, where the expectation is taken over the choice of the instance as well as the coin-tosses of the solving algorithm. Then, it is possible to solve Problem (W3) in expected poly(|I|) · T (n, poly(n), poly(n)) time on every n-dimensional instance I, where the expectation is taken over the coin-tosses of the solving algorithm.
Remark. Ajtai [1] has noted that the theorem remain valid also when Problem (A1) is relaxed so that the desired output is allowed to have Euclidean norm of up to poly(n) (i.e., one requires x ≤ poly(n) rather than x < n).

Our Version
We observe that one can use essentially the same proof to show that the following problem is also hard on the average. Problem (A2): For parameters n, m, q ∈ N as in (A1).
Theorem 1: Suppose that it is possible to solve a uniformly selected instance of Problem (A2) in expected T (n, m, q)-time, where the expectation is taken over the choice of the instance as well as the coin-tosses of the solving algorithm. Then, it is possible to solve Problem (W3) in expected poly(|I|) · T (n, poly(n), poly(n)) time on every n-dimensional instance I, where the expectation is taken over the coin-tosses of the solving algorithm.
Proof: By the foregoing Remark, Ajtai's Theorem holds also when modifying Problem (A1) such that the output is (only) required to have Euclidean norm of up to m. Once so modified, Problem (A1) becomes more relaxed than Problem (A2) and so the current theorem follows.
For the sake of self-containment we sketch the main ideas of the proof of Ajtai's Theorem (equivalently, of Theorem 1) in Section 4. The reader is referred to [1] for further details.

Constructing Collision-Free Hash Functions
The security of our proposed collision-free hash functions follows directly from Theorem 1. Below, we spell out the argument and discuss the parameters.

The functions and their security
Recall our construction of a family of collision-free hash functions:

Picking a hash-function
To pick a hash-function with security-parameters n, m, q (where n log q < m ≤ q 2n 4 and q = O(n c )), we pick a random matrix M ∈ Z n×m q . The collision-free property is easy to establish assuming that Problem (A2) is hard on the average. That is:

Evaluating the hash function
Theorem 2: Suppose that given a uniformly chosen matrix, M ∈ Z n×m q , it is possible to find in (expected) T (n, m, q)-time two vectors x = y ∈ {0, 1} m such that M x ≡ M y (mod q). Then, it is possible to solve a uniformly selected instance of Problem (A2) in (expected) T (n, m, q)-time.
Proof: If we can find two binary strings which constitutes a solution to Problem (A2) for the instance M .

The Parameters
The proof of Theorem 1 imposes restrictions on the relationship between the parameters n, m and q. First of all, we should think of n as the security parameter of the system, since we derive the difficulty of solving Problem (A2) by assuming the difficulty of approximating some problems over n-dimensional lattices.
The condition m > n log q is necessary for two reasons. The first is simply because we want the output of the hash function to be shorter than its input. The second is that when m < n log q, a random instance of problem (A2) typically does not have a solution at all, and the reduction procedure in the proof of Theorem 1 falls apart.
The conditions q = O(n c ) and m < q/2n 4 also come from the proof of Theorem 1. Their implications for the security of the system are as follows: -The larger q is, the stronger the assumption that needs to be made regarding the complexity of problem (W3). Namely, the security proof shows that (A2) with parameters n, m, q is hard to solve on the average, if the problem (W3) (qn 6 ) is hard in the worst case, where (W3) (qn 6 ) is the problem of approximating the shortest independent set of a lattice up to a factor of qn 6 . Thus, for example, if we worry (for a given n) that an approximation ratio of n 15 is feasible, then we better choose q < n 9 . Also, since we know that approximation within exponential factor is possible, we must always choose q to be sub-exponential in n. -By the above, the ratio R def = q/n 4 m must be strictly bigger than 1 (above, for simplicy, we stated R > 2). The larger R is, the better the reduction becomes: In the reduction from (W3) to (A2) we need to solve several random (A2) problems to obtain a solution to one (W3) problem. The number of instances of (A2) problem which need to be solved depends on R. Specifically, this number behaves roughly like n 2 / log R. This means that when q/n 4 = 2m we need to solve about n 2 instances of (A2) per any instance of (W3), which yields a ratio of O(n 2 ) between the time it takes to break the hashing scheme and the time it takes to solve a worst-case (W3) problem. On the other hand, when R approaches 1 the number of iterations (in the reduction) grows rapidly (and tends to infinity).
Notice also that the inequalities n log q < m < q n 4 implies a lower bound on q, namely q log q > n 5 , which means that q = Ω(n 5 log n).

Self-contained Sketch of the Proof of Theorem 1
At the heart of the proof is the following procedure for solving (W3): It takes as inputs a basis B = b 1 , · · · , b n for a lattice and a set of n linearly independent lattice vectors V = v 1 , · · · , v n , with |v 1 | ≤ |v 2 | ≤ · · · ≤ |v n |. The procedure produces another lattice vector w, such that |w| ≤ |v n |/2 and w is linearly independent of v 1 , · · · , v n−1 . We can then replace the vector v n with w and repeat this process until we get a "very short independent set". When invoking this procedure, we denote by S the length of the vector v n (which is the longest vector in V ).
In the sequel we describe this procedure and show that as long as S is more than n c times the size of the basic lattice-cell (for some constant c > 0), the procedure succeeds with high probability. Therefore we can repeat the process until the procedure fails, and then conclude that (with high probability) the length of the longest vector in V is not more that n c times the size of the basic lattice-cell. For the rest of this section we will assume that S is larger than n c times the size of the basic lattice-cell.
The procedure consists of five steps: We first construct an "almost cubic" parallelepiped of lattice vectors, which we call a pseudo-cube. Next, we divide this pseudo-cube into q n small parallelepipeds (not necessarily of lattice vectors), which we call sub-pseudo-cubes. We then pick some random lattice points in the pseudo-cube (see Step 3) and consider the location of each point with respect to the partition of the pseudo-cube into sub-pseudo-cubes (see Step 4). Each such location is represented as a vector in Z n q and the collection of these vectors forms an instance of Problem (A2). A solution to this instance yields a lattice point that is pretty close to a "corner" of the pseudo-cube. Thus, our final step consists of using the solution to this (A2) instance to compute the "short vector" w. Below we describe each of these steps in more details.
1. Constructing a "pseudo-cube". The procedure first constructs a parallelepiped of lattice vectors that is "almost a cube". This can be done by taking a sufficiently large cube (say, a cube with side length of n 3 S), expressing each of the cubes' basis vectors as a linear combination of the v i 's, and then rounding the coefficients in this combination to the nearest integers. Denote the vectors thus obtained by f 1 , · · · , f n and the parallelepiped that is spanned by them by C. The f i 's are all lattice vectors, and their distance from the basis vectors of the "real cube" is very small compared to the size of the cube. 1 Hence the parallelepiped C is very "cube-like". We call this parallelepiped a pseudo-cube.
2. Dividing the pseudo-cube into "sub-pseudo-cubes". We then divide C into q n equal sub-pseudo-cubes, each of which can be represented by a vector in Z n q as follows: For each sub-pseudo-cube C T , we call the vector o T = i ti q f i the origin of C T (i.e., o T is the vector in C T that is closest to the origin). We note that any vector in v ∈ C T can be written as v = o T + δ where δ is the location of v inside the The "real cube" The pseudo-cube sub-pseudo-cube C T . See Figure 2 for an illustration of that construction (with n = 2, q = 3). The parameter q was chosen such that each C T is "much smaller" than S. That is, the side-length of each sub-pseudo-cube C T is Sn 3 /q ≤ S/2nm. On the other hand, with this choice, each C T is still much larger than the basic lattice cell (since S is much bigger than the size of the basic cell). This, together with the fact that the C T 's are close to being cubes, implies that each C T contains approximately the same number of lattice points.
3. Choosing random lattice points in C. We then choose m random lattice points u 1 , · · · u m ∈ C. To do that, we use the basis B = {b 1 , · · · , b n } of the lattice. To choose each point, we take a linear combination of the basis vectors b i with large enough integer coefficients (say, in the range [0, 2 n c · max(S, |B|)] for some constant c). This gives us some lattice point p.
We then "reduce p mod C". By this we mean that we look at a tiling of the space R n with the pseudo-cube C, and we compute the location vector of p in its surrounding pseudo-cube. Formally, this is done by representing p as a linear combination of the f i 's, and taking the fractional part of the coefficients in this combination. The resulting vector is a lattice point, since it is obtained by subtracting integer combination of the f i 's from p, whereas the f i 's are lattice vectors. Also, this vector must lie inside C, since it is a linear combination of the f i 's with coefficients in [0, 1). It can be shown that if we choose the coefficients from a large enough range, then the distribution induced over the lattice points in C is statistically close to the uniform distribution.

4.
Constructing an instance of Problem (A2). After we have chosen m lattice points u 1 , · · · , u m , we compute for each u i the vector T i ∈ Z n q that represent the sub-pseudo-cube in which u i falls. That is, for each i we have u i ∈ C Ti .
Since, as we said above, each sub-pseudo-cube contains approximately the same number of points, and since the u i 's are distributed almost uniformly in C, then the distribution induced on the C Ti 's is close to the uniform distribution, and so the distribution over the T i 's is close to the uniform distribution over Z n q . We now consider the matrix whose columns are the vectors T i , that is, M = (T 1 |T 2 | · · · |T m ). By the foregoing argument, it is an "almost uniform" random matrix in Z n×m q , and so, it is an "almost uniform" random instance of Problem (A2).

5.
Computing a "short lattice vector". We now have a random instance M of Problem (A2), and so we can use the algorithm whose existence we assume in Theorem 1 to solve this instance in expected T (n, m, q) time. The solution is a vector x = {x 1 , · · · , x m } ∈ {−1, 0, 1} m such that M x = i x i T i is congruent to 0 mod q.
Once we found x, we compute the lattice vector w ′ = m i=1 x i u i . Let us examine the vector w ′ : Recall that we can represent each u i as the sum of o i def = o T i (the origin vector of C Ti ) and δ i (the location of u i inside C Ti ). Thus, A key observation is that since i x i T i ≡0 (mod q), "reducing the vector ( i x i o i ) mod C" yields the all-zeros vector; that is, ( i x i o i ) mod C =0. To see why this is the case, recall that each where all c j 's are integers. Since "reducing the vector i x i o T i mod C" means subtracting from it an integer linear combination of f j 's, the resulting vector is 0. Thus, "reducing w ′ mod C" we get m i=1 x i δ i ; that is, Since each δ i is just the location of some point inside the sub-pseudo-cube C Ti , the size of each δ i is at most n · S/2mn = S/2m. Moreover as x i ∈ {−1, 0, 1} for all i we get This means that the lattice vector w ′ mod C is close up to S 2 to one of the "corners" of C. Thus, all we need to do is to find the difference vector between the lattice vector w ′ mod C and that corner (which is also a lattice vector). Doing that is very similar to reducing w ′ mod C: We express w ′ as a linear combination of the f i 's, but instead of taking the fractional part of the coefficients, we take the difference between these coefficients and the closest integers. This gives us the "promised vector" w, a lattice vector whose length is at most S/2.
The only thing left to verify is that with high probability, w can replace the largest vector in V (i.e., it is linearly independent of the other vectors in V ). To see that, notice that the vector x does not depend on the exact choice of the u i 's, but only on the choice of their sub-pseudo-cubes C Ti 's. Thus, we can think of the process of choosing the u i 's as first choosing the C Ti 's, next computing the x i 's and only then choosing the δ i 's.
Assume (w.l.o.g.) that we have x 1 = 0. Let us now fix all the δ i 's except δ 1 and then pick δ 1 so as to get a random lattice point in C T1 . Thus, the probability that w falls in some fixed subspace of R n (such as the one spanned by the n − 1 smallest vectors in V ), equals the probability that a random point in C T1 falls in such subspace. Since C T1 is a pseudo-cube that is much larger than the basic cell of L, this probability is very small.