Arrow Research search

Author name cluster

Miklós Ajtai

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.

35 papers
1 author row

Possible papers

35

STOC Conference 2013 Conference Paper

Lower bounds for RAMs and quantifier elimination

  • Miklós Ajtai

For each natural number d we consider a finite structure M d whose universe is the set of all 0,1-sequence of length n=2 d , each representing a natural number in the set {0,1,...,2 n -1} in binary form. The operations included in the structure are the four constants 0,1,2 n -1,n, multiplication and addition modulo 2 n , the unary function min{2 x , 2 n -1}, the binary functions ⌊ x/y⌋ (with ⌊ x/0 ⌋ =0), max(x,y), min(x,y), and the boolean vector operations, vee,- defined on 0,1 sequences of length n, by performing the operations on all components simultaneously. These are essentially the arithmetic operations that can be performed on a RAM, with wordlength n, by a single instruction. We show that there exists an ε>0 and a term (that is, an algebraic expression) F(x,y) built up from the mentioned operations, with the only free variables x,y, such that if G d (y), d=0,1,2,..., is a sequence of terms, and for all d=0,1,2,..., M d models ∀ x, [G d (x)-> ∃ y, F(x,y)=0], then for infinitely many integers d, the depth of the term G d , that is, the maximal number of nestings of the operations in it, is at least ε (log d) 1/2 = ε (log log n) 1/2 . The following is a consequence. We are considering RAMs N n , with wordlength n=2 d , whose arithmetic instructions are the arithmetic operations listed above, and also have the usual other RAM instructions. The size of the memory is restricted only by the address space, that is, it is 2 n words. The RAMs has a finite instruction set, each instruction is encoded by a fixed natural number independently of n. Therefore a program P can run on each machine N n , if n=2 d is sufficiently large. We show that there exists an ε>0 and a program P, such that it satisfies the following two conditions. (i) For all sufficiently large n=2 d , if P running on N n gets an input consisting of two words a and b, then, in constant time, it gives a 0,1 output P n (a,b). (ii) Suppose that Q is a program such that for each sufficiently large n=2 d , if Q, running on N n , gets a word a of length n as an input, then it decides whether there exists a word b of length n such that P n (a,b)=0. Then, for infinitely many positive integers d, there exists a word a of length n=2 d , such that the running time of Q on N n at input a is at least ε (log d) 1/2 (log log d) -1 ≥ (log d) 1/2-ε = (log log n) 1/2-ε .

Details

STOC Conference 2012 Conference Paper

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

  • Miklós Ajtai

For each natural number d we consider a finite structure m d whose universe is the set of all 0,1-sequence of length n=2 d , each representing a natural number in the set [0,1,...,2 n -1] in binary form. The operations included in the structure are the four constants 0,1,2 n -1,n, multiplication and addition modulo 2 n , the unary function min[2 x , 2 n -1], the binary functions ⌊ x/y⌋ (with ⌊ x/0 ⌋ =0), max(x,y), min(x,y), and the boolean vector operations ∧,∨,- defined on 0,1 sequences of length n by performing the operations on all components simultaneously. These are essentially the arithmetic operations that can be performed on a RAM, with wordlength n, by a single instruction. We show that there exists a term (that is, an algebraic expression) F(x,y) built up from the mentioned operations, with the only free variables x,y, such that for all terms G(y), which is also built up from the mentioned operations, the following holds. For infinitely many positive integers d, there exists an a ∈ m d such that the following two statements are not equivalent: (i) m d |= ∃ x, F(x,a), (ii) m d models G(a)=0. In other words, the question whether an existential statement, depending on the parameter a ∈ m d is true or not, cannot be decided by evaluating an algebraic expression at a. Another way of formulating the theorem, in a slightly stronger form, is, that over the structures m d , quantifier elimination is not possible in the following sense. Let calm be a first-order language with equality, containing function symbols for all of the mentioned arithmetic operations. Then there exists an existential first-order formula φ(y) of calm, containing a single existential quantifier and the only free variable y, such that for each propositional formula P(y) of calm, we have that for infinitely many positive integers d, φ(y) and P(y) are not equivalent on m d , that is, m d |= - ∀ y, φ(y) >-> P(y). We also show that the theorem, in both forms, remains true if the binary operation min [x y , 2 n -1] is added to the structure m d . A general theorem is proved as well, which describes sufficient conditions for a set of operations on a sequence of structures k d , d=1,2,... which guarantees that the analogues of the mentioned theorems holds for the structures k d too.

Details

STOC Conference 2010 Conference Paper

Oblivious RAMs without cryptogrpahic assumptions

  • Miklós Ajtai

ithmic increase in the time and space requirements is possible on a probabilistic (coin flipping) RAM without using any cryptographic assumptions. The simulation will fail with a negligible probability. If n memory locations are used, then the probability of failure is at most n -log n . Pippenger and Fischer has shown in 1979, see [7], that a Turing machine with one-dimensional tapes, performing a computation of length n can be simulated on-line by an oblivious Turing machine with two dimensional tapes, in time O(n log n), where a Turing machine is oblivious if the movements of it heads as a function of time are independent of its input. For RAMs the notion of obliviousness was defined by Goldreich in 1987 in [2], and he proved a simulation theorem about it. A RAM is oblivious if the distribution of its memory access pattern, which memory cells are accessed at which time, is independent of the program running on the RAM, provided that the time used by the program is fixed. That is, an adversary watching the memory access will not know anything about the program running on the machine apart from its total time. Ostrovsky, improving Goldreich's theorem, has shown in 1990, see [4], [5], [3], that a RAM using n memory cells can a be simulated by an oblivious RAM with a random oracle (where the random bits can be accessed repeatedly) so that the increase of the space and time requirement is only about a factor of ln (Goldreich's factor was about exp[(log n) 1/2 ]). In both cases the oblivious RAM with a random oracle, can be replaced, by an oblivious probabilistic (coin-flipping) RAM, provided that we accept some unproven cryptographic assumptions, e.g., the existence of a one-way function. In this paper we show that simulation with an oblivious, coin-flipping RAM, with only a factor of ln increase in time and space requirements, is possible, even without any cryptographic assumptions.

Details

STOC Conference 2005 Conference Paper

Representing hard lattices with O(n log n) bits

  • Miklós Ajtai

We present a variant of the Ajtai-Dwork public-key cryptosystem where the size of the public-key is only O ( n log n ) bits and the encrypted text/clear text ratio is also O ( n log n ). This is true with the assumption that all of the participants in the cryptosystem share O ( n 2 log n ) random bits which has to be picked only once and the users of the cryptosystem get them e.g. together with the software implementing the protocol. The public key is a random lattice with an n c -unique nonzero shortest vector, where the constant c >1‾2 can be picked arbitrarily close to 1‾2, and we pick the lattice according to a distribution described in the paper. We do not prove a worst-case average-case equivalence but the security of the system follows from the hardness of a randomized diophantine approximation problem related to a well-known theorem of Dirichlet.

Details

STOC Conference 2004 Conference Paper

A conjecture about polynomial time computable lattice-lattice functions

  • Miklós Ajtai

We formulate a conjecture which describes all of the polynomial time computable (p. t. c. ) functions f with domain( f )=lattice n , range( f ) ⊆ lattice m , m ≤ n c , where lattice n is the set of lattices in R n with determinant 1. A former conjecture, the 0-1-conjecture, of the author states that all 0,1-valued functions defined on lattice n are constant almost everywhere. Since the n -dimensional lattices as Abelian groups are pairwise isomorphic we can say that, according to this conjecture, the value of a p. t. c. 0,1-function may depend only on the algebraic structure of the lattice and not on the metric defined on it. The new conjecture generalizes this statement for functions where the value is also a lattice. As a typical example we can think of the function f ( L )= L ′, where L ′ is the dual of L . When both the domain and the range of the functions are n -dimensional lattices with determinants 1 then, according to the conjecture, every p. c. t. functions are either constant or identical almost everywhere to f ( L )= AL , or f ( L )= AL ′, where A is a suitably chosen linear transformation with determinant one.There is a striking analogy between the new conjecture and theorems describing the uniquely definable functions which assign for each n -dimensional vectorspace an m -dimensional vectorspace. These theorems are closely related to questions about the Axiom of Choice. In this analogy polynomial time computation corresponds to definability (in set theory) and lattices to finite dimensional vectorspaces.

Details

STOC Conference 2003 Conference Paper

The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice

  • Miklós Ajtai

Schnorr's algorithm for finding an approximation for the shortest nonzero vector in an n dimensional lattice depends on a parameter k. He proved that for a fixed k ≤ n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater than the length of a shortest nonzero vector in the lattice by at most a factor of (4k 2 ) n/k . (The time required by the algorithm depends on k.) We show that if k=o(n), this bound on the performance of Schnorr's algorithm cannot be improved (apart from a constant factor in the exponent), namely there is a lattice and a basis so that if they are given as an input to the algorithm then the resulting approximating factor of the output is at least k ε n/k . (For larger integers k if Schnorr's algorithm runs in polynomial time then we have already a polynomial time algorithm for finding the shortest nonzero vector.) We also solve an open problem formulated by Schnorr about the the Korkine-Zolotareff lattice constants α k . We show that his upper bound α k ≤ k 1 + ln k is the best possible apart from a constant factor in the exponent. We prove a similar result about his upper bound β k ≤ 4k 2 , where β k is another lattice constant with an important role in Schnorr's analysis of his algorithm.

Details

STOC Conference 2002 Conference Paper

Approximate counting of inversions in a data stream

  • Miklós Ajtai
  • T. S. Jayram
  • Ravi Kumar 0001
  • D. Sivakumar 0001

(MATH) Inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. Considering the volume of the data sets in these applications, the data stream model {14, 2] is a natural setting to design efficient algorithms.We obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation. The best space bound we achieve is $O(\log n \log \log n)$ through a deterministic algorithm. In contrast, we derive an $\Omega(n)$ lower bound for randomized exact computation for this problem; thus approximation is essential.(MATH) We also consider two generalizations of this problem: (1) approximating the number of inversions between two permutations, for which we obtain a randomized $O(\sqrt{n} \log n)$-space algorithm, and (2) approximating the number of inversions in a general list, for which we obtain a randomized $O(\sqrt{n} \log^2 n)$-space two-pass algorithm. In contrast, we derive $\Omega(n)$-space lower bounds for deterministic approximate computation for these problems; thus both randomization and approximation are essential.All our algorithms use only O (log n ) time per data item.

Details

FOCS Conference 2002 Conference Paper

Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties

  • Miklós Ajtai

We formulate a conjecture about random n-dimensional lattices with a suitable distribution. The conjecture says that every polynomial time computable property of a random lattice holds with a probability either close to 0 or close to 1. Accepting the conjecture we get a large class of hard lattice problems. We describe an analogy between our conjecture and a set theoretical axiom, which cannot be proved in ZFC. This axiom says that there exists a nontrivial /spl sigma/-additive 0 - 1 measure defined on the set of all subsets of some set S.

Details

STOC Conference 2002 Conference Paper

The invasiveness of off-line memory checking

  • Miklós Ajtai

Memory checking is the task of checking the correctness of a sequence of "store" and "retrieve" operations. The operations are performed in a large unreliable memory. A checker using a much smaller but completely reliable memory tries to decide whether they were executed correctly. M. Blum, W. Evans, P. Gemmel, S. Kannan and M. Naor, has shown in 1991 that the off-line checking of a sequence of memory operations concerning a RAM consisting of n registers can be done, in a probabilistic sense, by a checker using only O (log n ) reliable memory and a constant number of RAM operation per each "store" and "retrieve" operations (with log n word length), moreover no unproven cryptographic assumptions are needed in the proof. The probability of error will be polynomially small in n . The solution however requires the checker to store some extra information in the unreliable memory, that is, the checking protocol is invasive. (In this solution the time of each "store" operation must be stored together with the data and must be supplied to the checker at the time of the corresponding retrieve operation.) In this paper we prove that off-line memory checking, in the sense described above, is necessarily invasive, even if we make the problem somewhat easier for the checker to exclude trivial counter-examples. We show that even if the checker is allowed to read a constant number of registers from the large memory after each "store" or "retrieve" instruction, off-line non-invasive memory checking is not possible. Moreover for the case when the invasiveness consists of storing some extra information together with each piece of data and retrieving it together with the data we give a quantitative lower bound on the amount of extra "invasive" information stored in the memory. Namely, if the checker has O(log n) memory and the probability of error is polynomially small than the "invasiveness" of the mentioned method of [5] is optimal upto a constant factor. With other words the total number of extra bits that must be written in the memory is at least ε T log T , where T is the number of store and retrieve operations. In the lower bounds we do not restrict the computational power of the checker at all, in fact we only assume that the checker is an n -way branching program with O (log n ) bits of memory.

Details

STOC Conference 2001 Conference Paper

A sieve algorithm for the shortest lattice vector problem

  • Miklós Ajtai
  • Ravi Kumar 0001
  • D. Sivakumar 0001

We present a randomized 2^{ O(n) } time algorithm to compute a shortest non-zero vector in an n -dimensional rational lattice. The best known time upper bound for this problem was 2^{ O(n \log n )} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.

Details

FOCS Conference 1999 Conference Paper

A Non-linear Time Lower Bound for Boolean Branching Programs

  • Miklós Ajtai

We prove that for all positive integer k and for all sufficiently small /spl epsiv/>0 if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2/sup em/ which for all inputs X/spl sube/{0, 1, .. ., n-1} computes in time kn the parity of the number of elements of the set of all pairs (x, y) with the property x/spl isin/X, y/spl isin/X, x 0 is an absolute constant and n is sufficiently large with respect to /spl delta/.

Details

FOCS Conference 1995 Conference Paper

Improved Algorithms and Analysis for Secretary Problems and Generalizations

  • Miklós Ajtai
  • Nimrod Megiddo
  • Orli Waarts

In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices. Optimal algorithms for the special case of k=1 are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known; even the question of whether or not the expected sum of powers of the ranks of selected items tends to infinity with n has been unresolved. We answer these open questions by obtaining explicit algorithms. For each z/spl ges/1, the resulting expected sum of the zth powers of the ranks of the selected objects is at most k/sup z+1//(z+1)+C(z)/spl middot/k/sup z+0. 5/log k, whereas the best possible value at all is k/sup z+1//(z+1)+O(k/sup z/). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and its expected rank.

Details

FOCS Conference 1994 Conference Paper

A Theory of Competitive Analysis for Distributed Algorithms

  • Miklós Ajtai
  • James Aspnes
  • Cynthia Dwork
  • Orli Waarts

We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Y. Bartal et al. (1992), and of B. Awerbuch et al. (1992), in the context of data management and job scheduling. In these papers, as well as in other subsequent sequent work, the cost of a distributed algorithm is compared to the cost of an optimal global-control algorithm. In this paper we introduce a more refined notion of competitiveness for distributed algorithms, one that reflects the performance of distributed algorithms more accurately. In particular, our theory allows one to compare the cost of a distributed on-line algorithm to the cost of an optimal distributed algorithm. We demonstrate our method by studying the cooperative collect primitive, first abstracted by M. Saks, N. Shavit, and H. Woll (1991). We provide the first algorithms that allow processes to cooperate to finish their work in fewer steps. Specifically, we present two algorithms (with different strengths), and provide a competitive analysis for each one. >

Details

STOC Conference 1992 Conference Paper

A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension

  • Miklós Ajtai
  • Nimrod Megiddo

It is shown that for any fixed number of variables, the linear programming problems with n linear inequalities can be solved deterministically by n parallel processors in sub-logarithmic time. The parallel time bound is O((log log n ) d ) where d is the number of variables. In the one-dimensional case this bound is optimal.

Details

FOCS Conference 1992 Conference Paper

Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths

  • Miklós Ajtai
  • Noga Alon
  • Jehoshua Bruck
  • Robert Cypher
  • Ching-Tien Ho
  • Moni Naor
  • Endre Szemerédi

Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Omega (d square root k). >

Details

FOCS Conference 1992 Conference Paper

Halvers and Expanders

  • Miklós Ajtai
  • János Komlós
  • Endre Szemerédi

The authors investigate the asymptotic efficiency of certain combinatorial networks called halvers, which are basic building blocks of many parallel algorithms. They improve the efficiency of halvers in terms of their depth. The novelty is the use of combinatorial circuits whose basic units are k-sorter switches. >

Details

FOCS Conference 1989 Conference Paper

Datalog vs. First-Order Logic

  • Miklós Ajtai
  • Yuri Gurevich

The relation between the expressive power of datalog and that of first-order languages, is clarified. It is then proved that every first-order expressible datalog query is bounded. A form of compactness theorem for finite structure implied by this result is examined, and counterexamples to natural generalizations of the above result are given. >

Details

FOCS Conference 1988 Conference Paper

Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)

  • Miklós Ajtai
  • Ronald Fagin

It is shown that for directed graphs, reachability can not be expressed by an existential monadic second-order sentence. The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic. However, it is shown that for directed graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence. One reason for the interest in the main result is that while there is considerable empirical evidence (in terms of the efficiency of algorithms that have been discovered) that reachability in directed graphs is 'harder' than reachability in undirected graphs, this is the first proof in a precise technical sense that this is so. >

Details

FOCS Conference 1988 Conference Paper

The Complexity of the Pigeonhole Principle

  • Miklós Ajtai

The pigeonhole principle for n is the statement that there is no one-to-one function between a set of size n and a set of size n-1. This statement can be formulated as an unlimited-fan-in constant depth polynomial-size Boolean formula PHP/sub n/ in n(n-1) variables, PHP/sub n/ can be proved in the propositional calculus; that is, a sequence of Boolean formulas can be given so that each one is either an axiom of the propositional calculus or a consequence of some of the previous ones according to an inference rule of the propositional calculus, the last one being PHP/sub n/. The main result is that the pigeonhole principle cannot be proved in this way if the size of the proof (the total number or symbols of the formulas in the sequence) is polynomial in n and each formula is constant-depth (unlimited-fan-in), polynomial size and contains only the variables of PHP/sub n/. >

Details

STOC Conference 1987 Conference Paper

Deterministic Simulation in LOGSPACE

  • Miklós Ajtai
  • János Komlós
  • Endre Szemerédi

In this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. Namely if there is a test in LOGSPACE so that a random sequence of length (log n ) 2 / log log n passes the test with probability at least 1/ n then a deterministic sequence can be constructed in LOGSPACE which also passes the test. It is important that the machine performing the test gets each bit of the sequence only once. The theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size. The sequence that we construct does not really depend on the test, in the sense that a polynomial family of sequences is constructed so that at least one of them passes any test. This family is the same even if the test is allowed to use an oracle of polynomial size, and it can be constructed in LOGSPACE (without using an oracle).

Details

FOCS Conference 1987 Conference Paper

Recursive Construction for 3-Regular Expanders

  • Miklós Ajtai

We present an algorithm which in n3(log n)3 time constructs a 3- regular expander graph on n vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of length s = [c log n] decreases (for some fixed absolute constant c). When we reach a local minimum in the number of cycles of length s the graph is an expander. The proof is completely elementary, we use only the basic results about the eigenvalues and eigenvectors of symmetric matrices.

Details

FOCS Conference 1985 Conference Paper

Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)

  • Miklós Ajtai
  • Avi Wigderson

We explicitly construct, for every integer n and ε ≫ 0, a family of functions (psuedo-random bit generators) fn, ε: {0, 1}nε → {0, 1}n with the following property: for a random seed, the pseudorandom output "looks random" to any polynomial size, constant depth, unbounded fan-in circuit. Moreover, the functions fn, ε themselves can be computed by uniform polynomial size, constant depth circuits. Some (interrelated) consequences of this result are given below. 1) Deterministic simulation of probabilistic algorithms. The constant depth analogues of the probabilistic complexity classes RP and BPP are contained in the deterministic complexity classes DSPACE(nε) and DTIME(2nε) for any ε ≫ 0. 2) Making probabilistic constructions deterministic. Some probablistic constructions of structures that elude explicit constructions can be simulated in the above complexity classes. 3) Approximate counting. The number of satisfying assignments to a (CNF or DNF) formula, if not too small, can be arbitrarily approximated in DSPACE(nε) and DTIME(2nε), for any ε ≫ 0. We also present two results for the special case of depth 2 circuits. They deal, respectively, with finding a satisfying assignment and approximately counting the number of assignments. For example, for 3-CNF formulas with a fixed fraction of satisfying assignmemts, both tasks can be performed in polynomial time!

Details

STOC Conference 1983 Conference Paper

An O(n log n) Sorting Network

  • Miklós Ajtai
  • János Komlós
  • Endre Szemerédi

The purpose of this paper is to describe a sorting network of size 0(n log n) and depth 0(log n). A natural way of sorting is through consecutive halvings: determine the upper and lower halves of the set, proceed similarly within the halves, and so on. Unfortunately, while one can halve a set using only 0(n) comparisons, this cannot be done in less than log n (parallel) time, and it is known that a halving network needs (½)n log n comparisons. It is possible, however, to construct a network of 0(n) comparisons which halves in constant time with high accuracy. This procedure (ε-halving) and a derived procedure (ε-nearsort) are described below, and our sorting network will be centered around these elementary steps.

Details

FOCS Conference 1983 Conference Paper

Hash Functions for Priority Queues

  • Miklós Ajtai
  • Michael L. Fredman
  • János Komlós

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.

Details
v2026.09.13