Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR13-074 | 9th May 2013
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

Helly Circular-Arc Graph Isomorphism is in Logspace

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

TR10-043 | 5th March 2010
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

Interval Graphs: Canonical Representation in Logspace

Revisions: 1

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

TR97-054 | 17th November 1997
Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

Arthur-Merlin Games in Boolean Decision Trees

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

TR95-013 | 24th February 1995
Oleg Verbitsky

The Parallel Repetition Conjecture for Trees is True

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

ISSN 1433-8092 | Imprint