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

__
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

__
TR14-132
| 23rd October 2014
__

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky#### Information Complexity for Multiparty Communication

Revisions: 2

__
TR14-057
| 17th April 2014
__

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar#### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

Revisions: 3

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

__
TR06-029
| 21st February 2006
__

Diptarka Chakraborty, Nikhil R. Devanur, Vijay V. Vazirani#### Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

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

Diptarka Chakraborty, Raghunath Tewari

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

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

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

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

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

\cite{Lutz:DISS}.

We show that this definition ...
more >>>

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang

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

Diptarka Chakraborty, Nikhil R. Devanur, Vijay V. Vazirani

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