On a Generalization of the Erd}os-Szekeres Theorem (2007)
We consider a generalization of the theorem of Erd}os and Szekeres on monotone subsequences. 1
Ups and Downs of First Order Sentences on Random Graphs (2007)
hierarchy Shelah and Spencer [1] proved that the zero-one law holds for the rst order sentences on random graphs G(n; n) whenever is a xed positive irrational. This raises the question what zero-one...
On roughly transitive amenable graphs and harmonic Dirichlet functions (2007)
Abstract. We introduce the notion of rough transitivity and prove that there exist no non-constant harmonic Dirichlet functions on amenable roughly transitive graphs. 1
Covering lattice points by subspaces (2007)
Gergely Harcos, J Anos Pach, G Abor Tardos
Abstract. We nd tight estimates for the minimum number of proper subspaces needed to cover all lattice points in an n-dimensional convex body C, symmetric about the origin 0. This enables us to prove...
Martin Dietzfelbinger, Peter Bro Miltersen, G Abor Tardos, Noga Alon, Noga Alon, Erez Petrank, ...
et al.:
A lower bound on the mod 6 degree of the or function (1998)
We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in boolean variables over Zm. In particular, we say that a polynomial P...
The Communication Complexity of the Universal Relation (1997)
Gábor Tardos, G Abor Tardos, Uri Zwick
Consider the following communication problem. Alice gets a word x 2 f0; 1g n and Bob gets a word y 2 f0; 1g n . Alice and Bob are told that x 6= y. Their goal is to find an index 1 i n such that x i...