Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Diptarka Chakraborty:

TR15-111 | 8th July 2015
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Low Distortion Embedding from Edit to Hamming Distance using Coupling

Revisions: 1

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. ... more >>>

TR15-016 | 16th January 2015
Diptarka Chakraborty, Raghunath Tewari

An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Revisions: 1

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for ... more >>>

TR14-132 | 23rd October 2014
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

Information Complexity for Multiparty Communication

Revisions: 2

In this paper, we have studied the information complexity for the communication model involving more than two parties. A lot of work has already been done on the information complexity in two party communication model and the question of extending the definition of information complexity to the multiparty communication model ... more >>>

TR14-057 | 17th April 2014
Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

Revisions: 3

In this paper, we propose a quantification of distributions on a set
of strings, in terms of how close to pseudorandom the distribution
is. The quantification is an adaptation of the theory of dimension of
sets of infinite sequences first introduced by Lutz
We show that this definition ... more >>>

TR14-035 | 13th March 2014
Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang

New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs.

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.
(1) A polynomial-time,
$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ... more >>>

TR06-029 | 21st February 2006
Diptarka Chakraborty, Nikhil R. Devanur, Vijay V. Vazirani

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity

We study the structure of EG[2], the class of Eisenberg-Gale markets
with two agents. We prove that all markets in this class are rational and they
admit strongly polynomial algorithms whenever
the polytope containing the set of feasible utilities of the two agents can be described
via a combinatorial LP. ... more >>>

ISSN 1433-8092 | Imprint