All reports by Author Gábor Tardos:

__
TR05-095
| 26th August 2005
__

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin#### Partitioning multi-dimensional sets in a small number of ``uniform'' parts

__
TR98-036
| 11th June 1998
__

Vince Grolmusz, Gábor Tardos#### Lower Bounds for (MOD p -- MOD m) Circuits

__
TR97-054
| 17th November 1997
__

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin#### Arthur-Merlin Games in Boolean Decision Trees

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>

Vince Grolmusz, Gábor Tardos

Modular gates are known to be immune for the random

restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and

Hastad. We demonstrate here a random clustering technique which

overcomes this difficulty and is capable to prove generalizations of

several known modular circuit lower bounds of Barrington, Straubing,

Therien; Krause ...
more >>>

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

It is well known that probabilistic boolean decision trees

cannot be much more powerful than deterministic ones (N.~Nisan, SIAM

Journal on Computing, 20(6):999--1007, 1991). Motivated by a question

if randomization can significantly speed up a nondeterministic

computation via a boolean decision tree, we address structural

properties of Arthur-Merlin games ...
more >>>