All reports by Author Jacobo Toran:

__
TR24-042
| 22nd February 2024
__

Lisa Jaser, Jacobo Toran#### Pebble Games and Algebraic Proof Systems Meet Again

Comments: 1

__
TR23-063
| 2nd May 2023
__

Jacobo Toran, Florian Wörz#### Cutting Planes Width and the Complexity of Graph Isomorphism Refutations

__
TR21-097
| 7th July 2021
__

Jacobo Toran, Florian Wörz#### Number of Variables for Graph Identification and the Resolution of GI Formulas

__
TR19-097
| 4th July 2019
__

Jacobo Toran, Florian Wörz#### Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

Revisions: 1
,
Comments: 1

__
TR18-170
| 4th October 2018
__

Nicola Galesi, Navid Talebanfard, Jacobo Toran#### Cops-Robber games and the resolution of Tseitin formulas

__
TR16-157
| 13th October 2016
__

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran#### Parameterized Complexity of Small Weight Automorphisms

__
TR16-024
| 22nd February 2016
__

Patrick Scharpfenecker, Jacobo Toran#### Solution-Graphs of Boolean Formulas and Isomorphism

__
TR15-100
| 16th June 2015
__

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran#### Succinct Encodings of Graph Isomorphism

__
TR14-096
| 29th July 2014
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran#### Solving Linear Equations Parameterized by Hamming Weight

__
TR10-117
| 22nd July 2010
__

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner#### Graph Isomorphism is not AC^0 reducible to Group Isomorphism

__
TR09-094
| 7th October 2009
__

Bireswar Das, Jacobo Toran, Fabian Wagner#### Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

__
TR07-071
| 1st August 2007
__

Jacobo Toran#### Reductions to Graph Isomorphism

__
TR04-008
| 27th November 2003
__

Vikraman Arvind, Jacobo Toran#### Solvable Group Isomorphism is (almost) in NP\cap coNP

__
TR03-044
| 12th May 2003
__

Juan Luis Esteban, Jacobo Toran#### A Combinatorial Characterization of Treelike Resolution Space

__
TR98-027
| 15th April 1998
__

Vikraman Arvind, Jacobo Toran#### Sparse sets, approximable sets, and parallel queries to NP

__
TR97-026
| 18th June 1997
__

Jochen Me\3ner, Jacobo Toran#### Optimal proof systems for Propositional Logic and complete sets

Lisa Jaser, Jacobo Toran

Analyzing refutations of the well known

pebbling formulas we prove some new strong connections between pebble games and algebraic proof system, showing that

there is a parallelism between the reversible, black and black-white pebbling games on one side, and

the three algebraic proof systems NS, MC and ...
more >>>

Jacobo Toran, Florian Wörz

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>

Jacobo Toran, Florian Wörz

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>

Jacobo Toran, Florian Wörz

We show a new connection between the space measure in tree-like resolution and the reversible pebble game in graphs. Using this connection we provide several formula classes for which there is a logarithmic factor separation between the space complexity measure in tree-like and general resolution. We show that these separations ... more >>>

Nicola Galesi, Navid Talebanfard, Jacobo Toran

We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed ... more >>>

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran

We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the ... more >>>

Patrick Scharpfenecker, Jacobo Toran

The solution graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures ... more >>>

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:

1. Does $Ax=b$ have a solution of weight at most $t$?

2. Does $Ax=b$ have a solution of weight exactly $t$?

3. Does $Ax=b$ have a ...
more >>>

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner

We give a new upper bound for the Group and Quasigroup

Isomorphism problems when the input structures

are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with $O(\log\log n)$ depth and $O(\log^2 n)$ nondeterministic bits, ...
more >>>

Bireswar Das, Jacobo Toran, Fabian Wagner

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width

are known to be solvable in polynomial time \cite{Bo90},\cite{YBFT}.

We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>>

Jacobo Toran

We show that several reducibility notions coincide when applied to the

Graph Isomorphism (GI) problem. In particular we show that if a set is

many-one logspace reducible to GI, then it is in fact many-one AC^0

reducible to GI. For the case of Turing reducibilities we show that ...
more >>>

Vikraman Arvind, Jacobo Toran

The Group Isomorphism problem consists in deciding whether two input

groups $G_1$ and $G_2$ given by their multiplication tables are

isomorphic. We first give a 2-round Arthur-Merlin protocol for the

Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$

of size $n$, Arthur uses ...
more >>>

Juan Luis Esteban, Jacobo Toran

We show that the Player-Adversary game from a paper

by Pudlak and Impagliazzo played over

CNF propositional formulas gives

an exact characterization of the space needed

in treelike resolution refutations. This

characterization is purely combinatorial

and independent of the notion of resolution.

We use this characterization to give ...
more >>>

Vikraman Arvind, Jacobo Toran

We relate the existence of disjunctive hard sets for NP to

other well studied hypotheses in complexity theory showing

that if an NP-complete set or a coNP-complete set is

polynomial-time disjunctively reducible

to a sparse set then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$. Using

a similar argument we obtain also that ...
more >>>

Jochen Me\3ner, Jacobo Toran

A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range

is the set of tautologies in Propositional Logic (TAUT), is called

a proof system. Cook and Reckhow defined this concept

and in order to compare the relative strenth of different proof systems,

they considered the notion ...
more >>>