3 papers
cs.DS2022
The White-Box Adversarial Data Stream Model
Miklos Ajtai, Vladimir Braverman, T. S. Jayram +4
We study streaming algorithms in the white-box adversarial model, where the stream is chosen adaptively by an adversary who observes the entire internal state of the algorithm at e…
cs.DS2015
Sorting and Selection with Imprecise Comparisons
Miklos Ajtai, Vitaly Feldman, Avinatan Hassidim +1
We consider a simple model of imprecise comparisons: there exists some such that when a subject is given two elements to compare, if the values of those elements (as perceive…
cs.CC2013
Lower Bounds for RAMs and Quantifier Elimination
Miklos Ajtai
We are considering RAMs , with wordlength , whose arithmetic instructions are the arithmetic operations multiplication and addition modulo , the unary functi…