Search Results

Documents authored by Chandrasekaran, Karthekeyan

Document
DOI: 10.4230/LIPIcs.ESA.2024.22
Hypergraph Connectivity Augmentation in Strongly Polynomial Time

Authors: Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. For graph network design problems where the goal is to construct a graph that satisfies certain connectivity requirements, the number of edges in every feasible solution is at most quadratic in the number of vertices. In contrast, for hypergraph network design problems, we might have feasible solutions in which the number of hyperedges is exponential in the number of vertices. This presents an additional technical challenge in hypergraph network design problems compared to graph network design problems: in order to solve the problem in polynomial time, we first need to show that there exists a feasible solution in which the number of hyperedges is polynomial in the input size. The central theme of this work is to overcome this additional technical challenge for certain hypergraph network design problems. We show that these hypergraph network design problems admit solutions in which the number of hyperedges is polynomial in the number of vertices and moreover, can be solved in strongly polynomial time. Our work improves on the previous fastest pseudo-polynomial run-time for these problems. As applications of our results, we derive the first strongly polynomial time algorithms for (i) degree-specified hypergraph connectivity augmentation using hyperedges and (ii) degree-specified hypergraph node-to-area connectivity augmentation using hyperedges.
Cite as

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni. Hypergraph Connectivity Augmentation in Strongly Polynomial Time. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ESA.2024.22,
  author =	{B\'{e}rczi, Krist\'{o}f and Chandrasekaran, Karthekeyan and Kir\'{a}ly, Tam\'{a}s and Kulkarni, Shubhang},
  title =	{{Hypergraph Connectivity Augmentation in Strongly Polynomial Time}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.22},
  URN =		{urn:nbn:de:0030-drops-210938},
  doi =		{10.4230/LIPIcs.ESA.2024.22},
  annote =	{Keywords: Hypergraphs, Hypergraph Connectivity, Submodular Functions, Combinatorial Optimization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.9
On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms

Authors: Karthekeyan Chandrasekaran, Chandra Chekuri, Manuel R. Torres, and Weihao Zhu

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Dense subgraph discovery is an important problem in graph mining and network analysis with several applications. Two canonical polynomial-time solvable problems here are to find a maxcore (subgraph of maximum min degree) and to find a densest subgraph (subgraph of maximum average degree). Both of these problems can be solved in polynomial time. Veldt, Benson, and Kleinberg [Veldt et al., 2021] introduced the generalized p-mean densest subgraph problem which captures the maxcore problem when p = -∞ and the densest subgraph problem when p = 1. They observed that for p ≥ 1, the objective function is supermodular and hence the problem can be solved in polynomial time. In this work, we focus on the p-mean densest subgraph problem for p ∈ (-∞, 1). We prove that for every p ∈ (-∞,1), the problem is NP-hard, thus resolving an open question from [Veldt et al., 2021]. We also show that for every p ∈ (0,1), the weighted version of the problem is APX-hard. On the algorithmic front, we describe two simple 1/2-approximation algorithms for every p ∈ (-∞, 1). We complement the approximation algorithms by exhibiting non-trivial instances on which the algorithms simultaneously achieve an approximation factor of at most 1/2.
Cite as

Karthekeyan Chandrasekaran, Chandra Chekuri, Manuel R. Torres, and Weihao Zhu. On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.APPROX/RANDOM.2024.9,
  author =	{Chandrasekaran, Karthekeyan and Chekuri, Chandra and Torres, Manuel R. and Zhu, Weihao},
  title =	{{On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.9},
  URN =		{urn:nbn:de:0030-drops-210025},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.9},
  annote =	{Keywords: Densest subgraph problem, Hardness of approximation, Approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.23
Splitting-Off in Hypergraphs

Authors: Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of that vertex while preserving their degrees. Lovász [Lov{á}sz, 1974; Lov{á}sz, 1993] and Mader [Mader, 1978] showed the existence of this operation while preserving global and local connectivities respectively in graphs under certain conditions. These results have far-reaching applications in graph algorithms literature [Lovász, 1976; Mader, 1978; Frank, 1993; Frank and Király, 2002; Király and Lau, 2008; Frank, 1992; Goemans and Bertsimas, 1993; Frank, 1994; Bang-Jensen et al., 1995; Frank, 2011; Nagamochi and Ibaraki, 2008; Nagamochi et al., 1997; Henzinger and Williamson, 1996; Goemans, 2001; Jordán, 2003; Kriesell, 2003; Jain et al., 2003; Chan et al., 2011; Bhalgat et al., 2008; Lau, 2007; Chekuri and Shepherd, 2008; Nägele and Zenklusen, 2020; Blauth and Nägele, 2023]. In this work, we introduce a splitting-off operation in hypergraphs. We show that there exists a local connectivity preserving complete splitting-off in hypergraphs and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs. We illustrate the usefulness of our splitting-off operation in hypergraphs by showing two applications: (1) we give a constructive characterization of k-hyperedge-connected hypergraphs and (2) we give an alternate proof of an approximate min-max relation for max Steiner rooted-connected orientation of graphs and hypergraphs (due to Király and Lau [Király and Lau, 2008]). Our proof of the approximate min-max relation for graphs circumvents the Nash-Williams' strong orientation theorem and uses tools developed for hypergraphs.
Cite as

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Shubhang Kulkarni. Splitting-Off in Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ICALP.2024.23,
  author =	{B\'{e}rczi, Krist\'{o}f and Chandrasekaran, Karthekeyan and Kir\'{a}ly, Tam\'{a}s and Kulkarni, Shubhang},
  title =	{{Splitting-Off in Hypergraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.23},
  URN =		{urn:nbn:de:0030-drops-201660},
  doi =		{10.4230/LIPIcs.ICALP.2024.23},
  annote =	{Keywords: Hypergraphs, Hypergraph Connectivity, Splitting-off, Constructive Characterizations, Hypergraph Orientations, Submodular Functions, Combinatorial Optimization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.3
Approximating Submodular k-Partition via Principal Partition Sequence

Authors: Karthekeyan Chandrasekaran and Weihang Wang

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
In submodular k-partition, the input is a submodular function f:2^V → ℝ_{≥ 0} (given by an evaluation oracle) along with a positive integer k and the goal is to find a partition of the ground set V into k non-empty parts V_1, V_2, …, V_k in order to minimize ∑_{i=1}^k f(V_i). Narayanan, Roy, and Patkar [Narayanan et al., 1996] designed an algorithm for submodular k-partition based on the principal partition sequence and showed that the approximation factor of their algorithm is 2 for the special case of graph cut functions (which was subsequently rediscovered by Ravi and Sinha [R. Ravi and A. Sinha, 2008]). In this work, we study the approximation factor of their algorithm for three subfamilies of submodular functions - namely monotone, symmetric, and posimodular and show the following results: 1) The approximation factor of their algorithm for monotone submodular k-partition is 4/3. This result improves on the 2-factor that was known to be achievable for monotone submodular k-partition via other algorithms. Moreover, our upper bound of 4/3 matches the recently shown lower bound under polynomial number of function evaluation queries [Santiago, 2021]. Our upper bound of 4/3 is also the first improvement beyond 2 for a certain graph partitioning problem that is a special case of monotone submodular k-partition. 2) The approximation factor of their algorithm for symmetric submodular k-partition is 2. This result generalizes their approximation factor analysis beyond graph cut functions. 3) The approximation factor of their algorithm for posimodular submodular k-partition is 2. We also construct an example to show that the approximation factor of their algorithm for arbitrary submodular functions is Ω(n/k).
Cite as

Karthekeyan Chandrasekaran and Weihang Wang. Approximating Submodular k-Partition via Principal Partition Sequence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.APPROX/RANDOM.2023.3,
  author =	{Chandrasekaran, Karthekeyan and Wang, Weihang},
  title =	{{Approximating Submodular k-Partition via Principal Partition Sequence}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.3},
  URN =		{urn:nbn:de:0030-drops-188284},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.3},
  annote =	{Keywords: Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.6
Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions

Authors: Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, and Chao Xu

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Submodular functions are fundamental to combinatorial optimization. Many interesting problems can be formulated as special cases of problems involving submodular functions. In this work, we consider the problem of approximating symmetric submodular functions everywhere using hypergraph cut functions. Devanur, Dughmi, Schwartz, Sharma, and Singh [Devanur et al., 2013] showed that symmetric submodular functions over n-element ground sets cannot be approximated within (n/8)-factor using a graph cut function and raised the question of approximating them using hypergraph cut functions. Our main result is that there exist symmetric submodular functions over n-element ground sets that cannot be approximated within a o(n^{1/3}/log² n)-factor using a hypergraph cut function. On the positive side, we show that symmetrized concave linear functions and symmetrized rank functions of uniform matroids and partition matroids can be constant-approximated using hypergraph cut functions.
Cite as

Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, and Chao Xu. Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{beideman_et_al:LIPIcs.FSTTCS.2022.6,
  author =	{Beideman, Calvin and Chandrasekaran, Karthekeyan and Chekuri, Chandra and Xu, Chao},
  title =	{{Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.6},
  URN =		{urn:nbn:de:0030-drops-173986},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.6},
  annote =	{Keywords: Submodular Functions, Hypergraphs, Approximation, Representation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.16
Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k

Authors: Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems - namely, Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. The input in hypergraph k-partitioning problems is a hypergraph G = (V, E) with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k non-empty parts (V₁, V₂, …, V_k) - known as a k-partition - so as to minimize an objective of interest. 1) If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-k-Partition. A subset of hyperedges is a minmax-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Minmax-Hypergraph-k-Partition. 2) If the objective of interest is the total cost of hyperedges crossing the k-partition, then the problem is known as Hypergraph-k-Cut. A subset of hyperedges is a min-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Hypergraph-k-Cut. We give the first polynomial bound on the number of minmax-k-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed k. Our technique is strong enough to also enable an n^{O(k)}p-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known n^{O(k²)}p-time deterministic algorithm, where n is the number of vertices and p is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).
Cite as

Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang. Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{beideman_et_al:LIPIcs.ICALP.2022.16,
  author =	{Beideman, Calvin and Chandrasekaran, Karthekeyan and Wang, Weihang},
  title =	{{Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.16},
  URN =		{urn:nbn:de:0030-drops-163578},
  doi =		{10.4230/LIPIcs.ICALP.2022.16},
  annote =	{Keywords: hypergraphs, k-partitioning, counting, enumeration}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.29
𝓁_p-Norm Multiway Cut

Authors: Karthekeyan Chandrasekaran and Weihang Wang

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We introduce and study 𝓁_p-norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along with k terminals and the goal is to find a partition of the vertex set into k parts each containing exactly one terminal so as to minimize the 𝓁_p-norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when p = 1) and min-max multiway cut (when p = ∞), both of which are well-studied classic problems in the graph partitioning literature. We show that 𝓁_p-norm-multiway-cut is NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an O(log² n)-approximation for all p ≥ 1. We also show an integrality gap of Ω(k^{1-1/p}) for a natural convex program and an O(k^{1-1/p-ε})-inapproximability for any constant ε > 0 assuming the small set expansion hypothesis.
Cite as

Karthekeyan Chandrasekaran and Weihang Wang. 𝓁_p-Norm Multiway Cut. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.ESA.2021.29,
  author =	{Chandrasekaran, Karthekeyan and Wang, Weihang},
  title =	{{𝓁\underlinep-Norm Multiway Cut}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.29},
  URN =		{urn:nbn:de:0030-drops-146103},
  doi =		{10.4230/LIPIcs.ESA.2021.29},
  annote =	{Keywords: multiway cut, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.7
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree

Authors: Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, and Minshen Zhu

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
A heapable sequence is a sequence of numbers that can be arranged in a min-heap data structure. Finding a longest heapable subsequence of a given sequence was proposed by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011) as a generalization of the well-studied longest increasing subsequence problem and its complexity still remains open. An equivalent formulation of the longest heapable subsequence problem is that of finding a maximum-sized binary tree in a given permutation directed acyclic graph (permutation DAG). In this work, we study parameterized algorithms for both longest heapable subsequence and maximum-sized binary tree. We introduce alphabet size as a new parameter in the study of computational problems in permutation DAGs and show that this parameter with respect to a fixed topological ordering admits a complete characterization and a polynomial time algorithm. We believe that this parameter is likely to be useful in the context of optimization problems defined over permutation DAGs.
Cite as

Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, and Minshen Zhu. Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.IPEC.2020.7,
  author =	{Chandrasekaran, Karthekeyan and Grigorescu, Elena and Istrate, Gabriel and Kulkarni, Shubhang and Lin, Young-San and Zhu, Minshen},
  title =	{{Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.7},
  URN =		{urn:nbn:de:0030-drops-133102},
  doi =		{10.4230/LIPIcs.IPEC.2020.7},
  annote =	{Keywords: maximum binary tree, heapability, permutation directed acyclic graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.30
The Maximum Binary Tree Problem

Authors: Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, and Minshen Zhu

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient exp(-O(log n/ log log n))-approximation algorithm under the exponential time hypothesis, where n is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient exp(-O(log^0.63 n))-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming P ≠ NP. In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on n vertices contains a binary tree of size k in 2^k poly(n) time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas, ANALCO 2011, which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs.
Cite as

Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, and Minshen Zhu. The Maximum Binary Tree Problem. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.ESA.2020.30,
  author =	{Chandrasekaran, Karthekeyan and Grigorescu, Elena and Istrate, Gabriel and Kulkarni, Shubhang and Lin, Young-San and Zhu, Minshen},
  title =	{{The Maximum Binary Tree Problem}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{30:1--30:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.30},
  URN =		{urn:nbn:de:0030-drops-128967},
  doi =		{10.4230/LIPIcs.ESA.2020.30},
  annote =	{Keywords: maximum binary tree, heapability, inapproximability, fixed-parameter tractability}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.17
Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs

Authors: Calvin Beideman, Karthekeyan Chandrasekaran, and Chao Xu

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
We address counting and optimization variants of multicriteria global min-cut and size-constrained min-k-cut in hypergraphs. 1) For an r-rank n-vertex hypergraph endowed with t hyperedge-cost functions, we show that the number of multiobjective min-cuts is O(r2^{tr}n^{3t-1}). In particular, this shows that the number of parametric min-cuts in constant rank hypergraphs for a constant number of criteria is strongly polynomial, thus resolving an open question by Aissi, Mahjoub, McCormick, and Queyranne [Aissi et al., 2015]. In addition, we give randomized algorithms to enumerate all multiobjective min-cuts and all pareto-optimal cuts in strongly polynomial-time. 2) We also address node-budgeted multiobjective min-cuts: For an n-vertex hypergraph endowed with t vertex-weight functions, we show that the number of node-budgeted multiobjective min-cuts is O(r2^{r}n^{t+2}), where r is the rank of the hypergraph, and the number of node-budgeted b-multiobjective min-cuts for a fixed budget-vector b ∈ ℝ^t_+ is O(n²). 3) We show that min-k-cut in hypergraphs subject to constant lower bounds on part sizes is solvable in polynomial-time for constant k, thus resolving an open problem posed by Queyranne [Guinez and Queyranne, 2012]. Our technique also shows that the number of optimal solutions is polynomial. All of our results build on the random contraction approach of Karger [Karger, 1993]. Our techniques illustrate the versatility of the random contraction approach to address counting and algorithmic problems concerning multiobjective min-cuts and size-constrained k-cuts in hypergraphs.
Cite as

Calvin Beideman, Karthekeyan Chandrasekaran, and Chao Xu. Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beideman_et_al:LIPIcs.APPROX/RANDOM.2020.17,
  author =	{Beideman, Calvin and Chandrasekaran, Karthekeyan and Xu, Chao},
  title =	{{Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.17},
  URN =		{urn:nbn:de:0030-drops-126203},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.17},
  annote =	{Keywords: Multiobjective Optimization, Hypergraph min-cut, Hypergraph-k-cut}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.81
Spectral Aspects of Symmetric Matrix Signings

Authors: Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, and Alexandra Kolla

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Our results are the following: 1) We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2) We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3) We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.
Cite as

Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, and Alexandra Kolla. Spectral Aspects of Symmetric Matrix Signings. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{carlson_et_al:LIPIcs.MFCS.2019.81,
  author =	{Carlson, Charles and Chandrasekaran, Karthekeyan and Chang, Hsien-Chih and Kakimura, Naonori and Kolla, Alexandra},
  title =	{{Spectral Aspects of Symmetric Matrix Signings}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.81},
  URN =		{urn:nbn:de:0030-drops-110258},
  doi =		{10.4230/LIPIcs.MFCS.2019.81},
  annote =	{Keywords: Spectral Graph Theory, Matrix Signing, Matchings}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.12
Odd Multiway Cut in Directed Acyclic Graphs

Authors: Karthekeyan Chandrasekaran and Sahand Mozaffari

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes and the goal is to find a smallest subset of non-terminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is an extension of the shadow-removal framework for parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for 2 terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for 2 terminals.
Cite as

Karthekeyan Chandrasekaran and Sahand Mozaffari. Odd Multiway Cut in Directed Acyclic Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.IPEC.2017.12,
  author =	{Chandrasekaran, Karthekeyan and Mozaffari, Sahand},
  title =	{{Odd Multiway Cut in Directed Acyclic Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.12},
  URN =		{urn:nbn:de:0030-drops-85470},
  doi =		{10.4230/LIPIcs.IPEC.2017.12},
  annote =	{Keywords: Odd Multiway Cut, Fixed-Parameter Tractability, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.42
Lattice-based Locality Sensitive Hashing is Optimal

Authors: Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota, and Elena Grigorescu

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
Locality sensitive hashing (LSH) was introduced by Indyk and Motwani (STOC'98) to give the first sublinear time algorithm for the c-approximate nearest neighbor (ANN) problem using only polynomial space. At a high level, an LSH family hashes "nearby" points to the same bucket and "far away" points to different buckets. The quality of measure of an LSH family is its LSH exponent, which helps determine both query time and space usage. In a seminal work, Andoni and Indyk (FOCS '06) constructed an LSH family based on random ball partitionings of space that achieves an LSH exponent of 1/c^2 for the l_2 norm, which was later shown to be optimal by Motwani, Naor and Panigrahy (SIDMA '07) and O'Donnell, Wu and Zhou (TOCT '14). Although optimal in the LSH exponent, the ball partitioning approach is computationally expensive. So, in the same work, Andoni and Indyk proposed a simpler and more practical hashing scheme based on Euclidean lattices and provided computational results using the 24-dimensional Leech lattice. However, no theoretical analysis of the scheme was given, thus leaving open the question of finding the exponent of lattice based LSH. In this work, we resolve this question by showing the existence of lattices achieving the optimal LSH exponent of 1/c^2 using techniques from the geometry of numbers. At a more conceptual level, our results show that optimal LSH space partitions can have periodic structure. Understanding the extent to which additional structure can be imposed on these partitions, e.g. to yield low space and query complexity, remains an important open problem.
Cite as

Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota, and Elena Grigorescu. Lattice-based Locality Sensitive Hashing is Optimal. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.ITCS.2018.42,
  author =	{Chandrasekaran, Karthekeyan and Dadush, Daniel and Gandikota, Venkata and Grigorescu, Elena},
  title =	{{Lattice-based Locality Sensitive Hashing is Optimal}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.42},
  URN =		{urn:nbn:de:0030-drops-83470},
  doi =		{10.4230/LIPIcs.ITCS.2018.42},
  annote =	{Keywords: Locality Sensitive Hashing, Approximate Nearest Neighbor Search, Random Lattices}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.2
Global and Fixed-Terminal Cuts in Digraphs

Authors: Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, and Chao Xu

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
The computational complexity of multicut-like problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of this phenomenon in two types of cut problems in directed graphs: double cut and bicut. 1. Fixed-terminal edge-weighted double cut is known to be solvable efficiently. We show that fixed-terminal node-weighted double cut cannot be approximated to a factor smaller than 2 under the Unique Games Conjecture (UGC), and we also give a 2-approximation algorithm. For the global version of the problem, we prove an inapproximability bound of 3/2 under UGC. 2. Fixed-terminal edge-weighted bicut is known to have an approximability factor of 2 that is tight under UGC. We show that the global edge-weighted bicut is approximable to a factor strictly better than 2, and that the global node-weighted bicut cannot be approximated to a factor smaller than 3/2 under UGC. 3. In relation to these investigations, we also prove two results on undirected graphs which are of independent interest. First, we show NP-completeness and a tight inapproximability bound of 4/3 for the node-weighted 3-cut problem under UGC. Second, we show that for constant k, there exists an efficient algorithm to solve the minimum {s,t}-separating k-cut problem. Our techniques for the algorithms are combinatorial, based on LPs and based on the enumeration of approximate min-cuts. Our hardness results are based on combinatorial reductions and integrality gap instances.
Cite as

Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, and Chao Xu. Global and Fixed-Terminal Cuts in Digraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.APPROX-RANDOM.2017.2,
  author =	{B\'{e}rczi, Krist\'{o}f and Chandrasekaran, Karthekeyan and Kir\'{a}ly, Tam\'{a}s and Lee, Euiwoong and Xu, Chao},
  title =	{{Global and Fixed-Terminal Cuts in Digraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.2},
  URN =		{urn:nbn:de:0030-drops-75511},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.2},
  annote =	{Keywords: Directed Graphs, Arborescence, Graph Cuts, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.24
On the Expansion of Group-Based Lifts

Authors: Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, and Vivek Madan

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
A k-lift of an n-vertex base graph G is a graph H on nxk vertices, where each vertex v of G is replaced by k vertices v_1,...,v_k and each edge uv in G is replaced by a matching representing a bijection pi_{uv} so that the edges of H are of the form (u_i,v_{pi_{uv}(i)}). Lifts have been investigated as a means to efficiently construct expanders. In this work, we study lifts obtained from groups and group actions. We derive the spectrum of such lifts via the representation theory principles of the underlying group. Our main results are: 1. A uniform random lift by a cyclic group of order k of any n-vertex d-regular base graph G, with the nontrivial eigenvalues of the adjacency matrix of G bounded by lambda in magnitude, has the new nontrivial eigenvalues bounded by lambda+O(sqrt{d}) in magnitude with probability 1-ke^{-Omega(n/d^2)}. The probability bounds as well as the dependency on lambda are almost optimal. As a special case, we obtain that there is a constant c_1 such that for every k<=2^{c_1n/d^2}, there exists a lift H of every Ramanujan graph by a cyclic group of order k such that H is almost Ramanujan (nontrivial eigenvalues of the adjacency matrix at most O(sqrt{d}) in magnitude). We also show how this result leads to a quasi-polynomial time deterministic algorithm to construct almost Ramanujan expanders. 2. There is a constant c_2 such that for every k>=2^{c_2nd}, there does not exist an abelian k-lift H of any n-vertex d-regular base graph such that H is almost Ramanujan. This can be viewed as an analogue of the well-known no-expansion result for constant degree abelian Cayley graphs. Suppose k_0 is the order of the largest abelian group that produces expanding lifts. Our two results highlight lower and upper bounds on k_0 that are tight upto a factor of d^3 in the exponent, thus suggesting a threshold phenomenon.
Cite as

Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, and Vivek Madan. On the Expansion of Group-Based Lifts. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.APPROX-RANDOM.2017.24,
  author =	{Agarwal, Naman and Chandrasekaran, Karthekeyan and Kolla, Alexandra and Madan, Vivek},
  title =	{{On the Expansion of Group-Based Lifts}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.24},
  URN =		{urn:nbn:de:0030-drops-75739},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.24},
  annote =	{Keywords: Expanders, Lifts, Spectral Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.46
Local Testing for Membership in Lattices

Authors: Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in lattice-based communication and cryptography. In this work, we initiate a systematic study of local testing for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following: 1. We show that in order to achieve low query complexity, it is sufficient to design one-sided non-adaptive canonical tests. This result is akin to, and based on an analogous result for error-correcting codes due to Ben-Sasson et al. (SIAM J. Computing, 35(1):1-21). 2. We demonstrate upper and lower bounds on the query complexity of local testing for membership in code formula lattices. We instantiate our results for code formula lattices constructed from Reed-Muller codes to obtain nearly-matching upper and lower bounds on the query complexity of testing such lattices. 3. We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing low-dimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in knapsack lattices. On the other hand, we show that knapsack lattices with bounded coefficients have low-query testers if the inputs are promised to lie in the span of the lattice.
Cite as

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu. Local Testing for Membership in Lattices. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.FSTTCS.2016.46,
  author =	{Chandrasekaran, Karthekeyan and Cheraghchi, Mahdi and Gandikota, Venkata and Grigorescu, Elena},
  title =	{{Local Testing for Membership in Lattices}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.46},
  URN =		{urn:nbn:de:0030-drops-68818},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.46},
  annote =	{Keywords: Lattices, Property Testing, Locally Testable Codes, Complexity Theory}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.151
Deciding Orthogonality in Construction-A Lattices

Authors: Karthekeyan Chandrasekaran, Venkata Gandikota, and Elena Grigorescu

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
Lattices are discrete mathematical objects with widespread applications to integer programs as well as modern cryptography. A fundamental problem in both domains is the Closest Vector Problem (popularly known as CVP). It is well-known that CVP can be easily solved in lattices that have an orthogonal basis if the orthogonal basis is specified. This motivates the orthogonality decision problem: verify whether a given lattice has an orthogonal basis. Surprisingly, the orthogonality decision problem is not known to be either NP-complete or in P. In this paper, we focus on the orthogonality decision problem for a well-known family of lattices, namely Construction-A lattices. These are lattices of the form C + qZ^n, where C is an error-correcting q-ary code, and are studied in communication settings. We provide a complete characterization of lattices obtained from binary and ternary codes using Construction- A that have an orthogonal basis. This characterization leads to an efficient algorithm solving the orthogonality decision problem, which also finds an orthogonal basis if one exists for this family of lattices. We believe that these results could provide a better understanding of the complexity of the orthogonality decision problem in general.
Cite as

Karthekeyan Chandrasekaran, Venkata Gandikota, and Elena Grigorescu. Deciding Orthogonality in Construction-A Lattices. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 151-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.FSTTCS.2015.151,
  author =	{Chandrasekaran, Karthekeyan and Gandikota, Venkata and Grigorescu, Elena},
  title =	{{Deciding Orthogonality in Construction-A Lattices}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{151--162},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.151},
  URN =		{urn:nbn:de:0030-drops-56509},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.151},
  annote =	{Keywords: Orthogonal Lattices, Construction-A, Orthogonal Decomposition, Lattice isomorphism}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact