All reports by Author Oleg Verbitsky:

__
TR15-032
| 21st February 2015
__

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky#### Graph Isomorphism, Color Refinement, and Compactness

Revisions: 2

__
TR13-074
| 9th May 2013
__

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky#### Helly Circular-Arc Graph Isomorphism is in Logspace

__
TR10-043
| 5th March 2010
__

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky#### Interval Graphs: Canonical Representation in Logspace

Revisions: 1

__
TR97-054
| 17th November 1997
__

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

__
TR95-013
| 24th February 1995
__

Oleg Verbitsky#### The Parallel Repetition Conjecture for Trees is True

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky

Color refinement is a classical technique used to show that two given graphs $G$ and $H$

are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph $G$ amenable to color refinement if the color-refinement procedure succeeds in distinguishing $G$ from any non-isomorphic ...
more >>>

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>

Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.

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 >>>

Oleg Verbitsky

The parallel repetition conjecture (PRC) of Feige and Lovasz says that the

error probability of a two prover one round interactive protocol repeated $n$

times in parallel is exponentially small in $n$.

We show that the PRC is true in the case when

the bipartite graph of dependence between ...
more >>>