Source author record

Miklos Ajtai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Sorting and Selection with Imprecise Comparisons

We consider a simple model of imprecise comparisons: there exists some $δ>0$ such that when a subject is given two elements to compare, if the values of those elements (as perceived by the subject) differ by at least $δ$ , then the comparison will be made correctly; when the two elements have values that are within $δ$ , the outcome of the comparison is unpredictable. This model is inspired by both imprecision in human judgment of values and also by bounded but potentially adversarial errors in the outcomes of sporting tournaments. Our model is closely related to a number of models commonly considered in the psychophysics literature where $δ$ corresponds to the {\em just noticeable difference unit (JND)} or {\em difference threshold}. In experimental psychology, the method of paired comparisons was proposed as a means for ranking preferences amongst $n$ elements of a human subject. The method requires performing all $\binom{n}{2}$ comparisons, then sorting elements according to the number of wins. The large number of comparisons is performed to counter the potentially faulty decision-making of the human subject, who acts as an imprecise comparator. We show that in our model the method of paired comparisons has optimal accuracy, minimizing the errors introduced by the imprecise comparisons. However, it is also wasteful, as it requires all $\binom{n}{2}$ . We show that the same optimal guarantees can be achieved using $4 n^{3/2}$ comparisons, and we prove the optimality of our method. We then explore the general tradeoff between the guarantees on the error that can be made and number of comparisons for the problems of sorting, max-finding, and selection. Our results provide strong lower bounds and close-to-optimal solutions for each of these problems.

preprint2013arXiv

Lower Bounds for RAMs and Quantifier Elimination

We are considering RAMs $N_{n}$ , with wordlength $n=2^{d}$ , whose arithmetic instructions are the arithmetic operations multiplication and addition modulo $2^{n}$ , the unary function $\min\lbrace 2^{x}, 2^{n}-1\rbrace$ , the binary functions $\lfloor x/y\rfloor$ (with $\lfloor x/0 \rfloor =0$ ), $\max(x,y)$ , $\min(x,y)$ , and the boolean vector operations $\wedge,\vee,\neg$ defined on $0,1$ sequences of length $n$ . It also has the 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)^{\frac{1}{2}} (\log \log d)^{-1}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.