All reports by Author Mario Szegedy:

__
TR15-102
| 22nd June 2015
__

Mario Szegedy#### An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game

__
TR09-059
| 2nd July 2009
__

Gábor Kun, Mario Szegedy#### A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

__
TR05-001
| 1st January 2005
__

Mario Szegedy#### Near optimality of the priority sampling procedure

__
TR98-008
| 15th January 1998
__

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy#### Proof verification and the hardness of approximation problems.

__
| 22nd June 2015 (removed)
__

Mario Szegedy#### An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game

Mario Szegedy

We give an $5\cdot n^{\log_{30}5}$ upper bund on the complexity of the communication game introduced by G. Gilmer, M. Kouck\'y and M. Saks \cite{saks} to study the Sensitivity Conjecture \cite{linial}, improving on their

$\sqrt{999\over 1000}\sqrt{n}$ bound. We also determine the exact complexity of the game up to $n\le 9$.

more >>>

Gábor Kun, Mario Szegedy

The well known dichotomy conjecture of Feder and

Vardi states that for every ﬁnite family Γ of constraints CSP(Γ) is

either polynomially solvable or NP-hard. Bulatov and Jeavons re-

formulated this conjecture in terms of the properties of the algebra

P ol(Γ), where the latter is ...
more >>>

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

Mario Szegedy

Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured

that the variance of their highly successful priority sampling procedure

is not larger than the variance of the threshold sampling procedure with sample size one smaller.

The conjecture's significance is that the latter procedure is provably optimal ...
more >>>

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

We show that every language in NP has a probablistic verifier

that checks membership proofs for it using

logarithmic number of random bits and by examining a

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Mario Szegedy