Found 2 Possible Name Variants:

Document

**Published in:** LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

A code is called a q-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index i and a received word w close to an encoding of a message x, outputs x_i by querying only at most q coordinates of w. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for 3-query binary LDC’s of dimension k and length n, the best known bounds are: 2^{k^o(1)} ≥ n ≥ Ω ̃(k²).
In this work, we take a second look at binary 3-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of Ω ̃(k²) for the length of strong 3-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to 2-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.

Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal. Combinatorial Lower Bounds for 3-Query LDCs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 85:1-85:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhattacharyya_et_al:LIPIcs.ITCS.2020.85, author = {Bhattacharyya, Arnab and Chandran, L. Sunil and Ghoshal, Suprovat}, title = {{Combinatorial Lower Bounds for 3-Query LDCs}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {85:1--85:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.85}, URN = {urn:nbn:de:0030-drops-117704}, doi = {10.4230/LIPIcs.ITCS.2020.85}, annote = {Keywords: Coding theory, Graph theory, Hypergraphs} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

We study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no tree-edge routing too many of the original edges.
For any general connected graph with n vertices and m edges, we show that its STC is at most O(sqrt{mn}), which is asymptotically optimal since we also demonstrate graphs with STC at least Omega(sqrt{mn}). We present a polynomial-time algorithm which computes a spanning tree with congestion O(sqrt{mn}* log n). We also present another algorithm for computing a spanning tree with congestion O(sqrt{mn}); this algorithm runs in sub-exponential time when m = omega(n log^2 n).
For achieving the above results, an important intermediate theorem is generalized Györi-Lovász theorem. Chen et al. [Jiangzhuo Chen et al., 2007] gave a non-constructive proof. We give the first elementary and constructive proof with a local search algorithm of running time O^*(4^n). We discuss some consequences of the theorem concerning graph partitioning, which might be of independent interest.
We also show that for any graph which satisfies certain expanding properties, its STC is at most O(n), and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC Theta(n) with high probability.

L. Sunil Chandran, Yun Kuen Cheung, and Davis Issac. Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chandran_et_al:LIPIcs.ICALP.2018.32, author = {Chandran, L. Sunil and Cheung, Yun Kuen and Issac, Davis}, title = {{Spanning Tree Congestion and Computation of Generalized Gy\"{o}ri-Lov\'{a}sz Partition}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.32}, URN = {urn:nbn:de:0030-drops-90361}, doi = {10.4230/LIPIcs.ICALP.2018.32}, annote = {Keywords: Spanning Tree Congestion, Graph Sparsification, Graph Partitioning, Min-Max Graph Partitioning, k-Vertex-Connected Graphs, Gy\"{o}ri-Lov\'{a}sz Theorem} }

Document

**Published in:** LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one path in which no two edges are coloured the same. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Chakraborty, Fischer, Matsliah and Yuster have shown that it is NP-hard to compute the rainbow connection number of graphs [J. Comb. Optim., 2011]. Basavaraju, Chandran, Rajendraprasad and Ramaswamy have reported an (r+3)-factor approximation algorithm to rainbow colour any graph of radius r [Graphs and Combinatorics, 2012]. In this article, we use a result of Guruswami, Håstad and Sudan on the NP-hardness of colouring a 2-colourable 4-uniform hypergraph using constantly many
colours [SIAM J. Comput., 2002] to show that for every positive integer k, it is NP-hard to distinguish between graphs with rainbow connection number 2k+2 and 4k+2. This, in turn, implies that there cannot exist a polynomial time algorithm to rainbow colour graphs with less than twice the optimum number of colours, unless P=NP.
The authors have earlier shown that the rainbow connection number problem remains NP-hard even when restricted to the class of chordal graphs, though in this case a 4-factor approximation algorithm is available [COCOON, 2012]. In this article, we improve upon the 4-factor approximation algorithm to design a linear-time algorithm that can rainbow colour a chordal graph G using at most 3/2 times the minimum number of colours if G is bridgeless and at most 5/2 times the minimum number of colours otherwise. Finally we show that the rainbow connection number of bridgeless chordal graphs cannot be polynomial-time approximated to a factor less than 5/4, unless P=NP.

L. Sunil Chandran and Deepak Rajendraprasad. Inapproximability of Rainbow Colouring. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 153-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chandran_et_al:LIPIcs.FSTTCS.2013.153, author = {Chandran, L. Sunil and Rajendraprasad, Deepak}, title = {{Inapproximability of Rainbow Colouring}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {153--162}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.153}, URN = {urn:nbn:de:0030-drops-43689}, doi = {10.4230/LIPIcs.FSTTCS.2013.153}, annote = {Keywords: rainbow connectivity, rainbow colouring, approximation hardness} }

Document

**Published in:** LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

A k-box B=(R_1,R_2,...,R_k), where each R_i is a closed interval on the real line, is defined to be the Cartesian product R_1 X R_2 X ... X R_k. If each R_i is a unit length interval, we call B a k-cube. Boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes.
It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan. Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/0607092, 2006.] that, for a graph G with maximum degree \Delta, cub(G) <= \lceil 4(\Delta +1) ln n\rceil. In this paper we show that, for a k-degenerate graph G, cub(G) <= (k+2) \lceil 2e log n \rceil. Since k is at most \Delta and can be much lower, this clearly is a stronger result. We also give an efficient deterministic algorithm that runs in O(n^2k) time to output a 8k(\lceil 2.42 log n\rceil + 1) dimensional cube representation for G.
The crossing number of a graph G, denoted as CR(G), is the minimum number of crossing pairs of edges, over all drawings of G in the plane. An important consequence of the above result is that if the crossing number of a graph G is t, then box(G) is O(t^{1/4}{\lceil log t\rceil}^{3/4}) . This bound is tight upto a factor of O((log t)^{3/4}).
Let (P,\leq) be a partially ordered set and let G_{P} denote its underlying comparability graph. Let dim(P) denote the poset dimension of P. Another interesting consequence of our result is to show that dim(P) \leq 2(k+2) \lceil 2e \log n \rceil, where k denotes the degeneracy of G_{P}. Also, we get a deterministic algorithm that runs in O(n^2k) time to construct a 16k(\lceil 2.42 log n\rceil + 1) sized realizer for P. As far as we know, though very good upper bounds exist for poset dimension in terms of maximum degree of its underlying comparability graph, no upper bounds in terms of the degeneracy of the underlying comparability graph is seen in the literature.

Abhijin Adiga, L. Sunil Chandran, and Rogers Mathew. Cubicity, Degeneracy, and Crossing Number. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 176-190, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{adiga_et_al:LIPIcs.FSTTCS.2011.176, author = {Adiga, Abhijin and Chandran, L. Sunil and Mathew, Rogers}, title = {{Cubicity, Degeneracy, and Crossing Number}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {176--190}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.176}, URN = {urn:nbn:de:0030-drops-33428}, doi = {10.4230/LIPIcs.FSTTCS.2011.176}, annote = {Keywords: Degeneracy, Cubicity, Boxicity, Crossing Number, Interval Graph, Intersection Graph, Poset Dimension, Comparability Graph} }

Document

**Published in:** LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Given a bipartite graph G, we consider the decision problem called BicliqueCover for a fixed positive integer parameter k where we are asked whether the edges of G can be covered with at most k complete bipartite subgraphs (a.k.a. bicliques). In the BicliquePartition problem, we have the additional constraint that each edge should appear in exactly one of the k bicliques. These problems are both known to be NP-complete but fixed parameter tractable. However, the known FPT algorithms have a running time that is doubly exponential in k, and the best known kernel for both problems is exponential in k. We build on this kernel and improve the running time for BicliquePartition to O*(2^{2k^2+k*log(k)+k}) by exploiting a linear algebraic view on this problem. On the other hand, we show that no such improvement is possible for BicliqueCover unless the Exponential Time Hypothesis (ETH) is false by proving a doubly exponential lower bound on the running time. We achieve this by giving a reduction from 3SAT on n variables to an instance of BicliqueCover with k=O(log(n)). As a further consequence of this reduction, we show that there is no subexponential kernel for BicliqueCover unless P=NP. Finally, we point out the significance of the exponential kernel mentioned above for the design of polynomial-time approximation algorithms for the optimization versions of both problems. That is, we show that it is possible to obtain approximation factors of n/log(n) for both problems, whereas the previous best approximation factor was n/sqrt(log(n)).

Sunil Chandran, Davis Issac, and Andreas Karrenbauer. On the Parameterized Complexity of Biclique Cover and Partition. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chandran_et_al:LIPIcs.IPEC.2016.11, author = {Chandran, Sunil and Issac, Davis and Karrenbauer, Andreas}, title = {{On the Parameterized Complexity of Biclique Cover and Partition}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.11}, URN = {urn:nbn:de:0030-drops-69293}, doi = {10.4230/LIPIcs.IPEC.2016.11}, annote = {Keywords: Biclique Cover/Partition, Linear algebra in finite fields, Lower bound} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail