DROPS

Volume

LIPIcs, Volume 18

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

FSTTCS 2012, December 15-17, 2012, Hyderabad, India

Editors: Deepak D'Souza, Jaikumar Radhakrishnan, and Kavitha Telikepalli

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.6

Online Facility Location with Weights and Congestion

Authors: Arghya Chakraborty and Rahul Vaze

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study two variants of the online facility location problem; (1) weighted requests and (2) congestion. Both of these variants are motivated by their applications to real life scenarios and the previously known results on online facility location cannot be directly adapted to analyse them. - Weighted requests: In this variant, each demand request is a pair (x,w) where x is the standard location of the demand while w is the corresponding weight of the request. The cost of servicing request (x,w) at facility F is w⋅ d(x,F). For this variant, given n requests, we present an online algorithm attaining a competitive ratio of 𝒪(log n) in the secretarial model for the weighted requests and show that it is optimal. -Congestion: The congestion variant considers the case when there is a congestion cost that grows with the number of requests served by each facility. For this variant, when the congestion cost is a monomial, we show that there exists an algorithm attaining a constant competitive ratio. This constant is a function of the exponent of the monomial and the facility opening cost but independent of the number of requests.

Cite as

Arghya Chakraborty and Rahul Vaze. Online Facility Location with Weights and Congestion. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2023.6,
  author =	{Chakraborty, Arghya and Vaze, Rahul},
  title =	{{Online Facility Location with Weights and Congestion}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.6},
  URN =		{urn:nbn:de:0030-drops-193797},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.6},
  annote =	{Keywords: online algorithms, online facility location, probabilistic method, weighted-requests, congestion}
}

Document

DOI: 10.4230/LIPIcs.CCC.2023.19

Criticality of AC⁰-Formulae

Authors: Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function f : {0,1}ⁿ → {0,1} is the minimum λ ≥ 1 such that for all positive integers t and all p ∈ [0,1], Pr_{ρ∼ℛ_p}[DT_{depth}(f|_ρ) ≥ t] ≤ (pλ)^t, where ℛ_p refers to the distribution of p-random restrictions. Håstad’s celebrated switching lemma shows that the criticality of any k-DNF is at most O(k). Subsequent improvements to correlation bounds of AC⁰-circuits against parity showed that the criticality of any AC⁰-circuit of size S and depth d+1 is at most O(log S)^d and any regular AC⁰-formula of size S and depth d+1 is at most O((1/d)⋅log S)^d. We strengthen these results by showing that the criticality of any AC⁰-formula (not necessarily regular) of size S and depth d+1 is at most O((log S)/d)^d, resolving a conjecture due to Rossman. This result also implies Rossman’s optimal lower bound on the size of any depth-d AC⁰-formula computing parity [Comput. Complexity, 27(2):209-223, 2018.]. Our result implies tight correlation bounds against parity, tight Fourier concentration results and improved #SAT algorithm for AC⁰-formulae.

Cite as

Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar. Criticality of AC⁰-Formulae. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{harsha_et_al:LIPIcs.CCC.2023.19,
  author =	{Harsha, Prahladh and Molli, Tulasimohan and Shankar, Ashutosh},
  title =	{{Criticality of AC⁰-Formulae}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.19},
  URN =		{urn:nbn:de:0030-drops-182898},
  doi =		{10.4230/LIPIcs.CCC.2023.19},
  annote =	{Keywords: AC⁰ circuits, AC⁰ formulae, criticality, switching lemma, correlation bounds}
}

Document

DOI: 10.4230/LIPIcs.ESA.2022.14

An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions

Authors: Florian Barth, Stefan Funke, and Claudius Proissl

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

Graphs with multiple edge costs arise naturally in the route planning domain when apart from travel time other criteria like fuel consumption or positive height difference are also objectives to be minimized. In such a scenario, this paper investigates the number of extreme shortest paths between a given source-target pair s, t. We show that for a fixed but arbitrary number of cost types d ≥ 1 the number of extreme shortest paths is in n^O(log^{d-1}n) in graphs G with n nodes. This is a generalization of known upper bounds for d = 2 and d = 3.

Cite as

Florian Barth, Stefan Funke, and Claudius Proissl. An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.ESA.2022.14,
  author =	{Barth, Florian and Funke, Stefan and Proissl, Claudius},
  title =	{{An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.14},
  URN =		{urn:nbn:de:0030-drops-169525},
  doi =		{10.4230/LIPIcs.ESA.2022.14},
  annote =	{Keywords: Parametric Shortest Paths, Extreme Shortest Paths}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.52

Set Membership with Two Classical and Quantum Bit Probes

Authors: Shyam S. Dhamapurkar, Shubham Vivek Pawar, and Jaikumar Radhakrishnan

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

Abstract

We study the classical and quantum bit-probe versions of the static set membership problem : Given a subset, S (|S| ≤ n) of a universe, 𝒰 (|𝒰| = m ≫ n), represent it as a binary string in memory so that the query "Is x in S?" (x ∈ 𝒰) can be answered by making at most t probes into the string. Let s_{A}(m,n,t) denote the minimum length of the bit string in any scheme that solves this static set membership problem. We show that for n ≥ 4 s_A(m,n,t = 2) = 𝒪(m^{1-1/(n-1)}) (if n = 0 (mod 3)); 𝒪(m^{1-1/n}) (if n = 1,2 (mod 3)); 𝒪(m^{6/7}) (if n = 8,9). These bounds are shown using a common scheme that is based on a graph-theoretic observation on orienting the edges of a graph of high girth. For all n ≥ 4, these bounds substantially improve on the previous best bounds known for this problem, some of which required elaborate constructions [Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2020]. Our schemes are explicit. A lower bound of the form s_A(m,n,2) = Ω(m^{1-1/⌊{n/4}⌋}) was known for this problem. We show an improved lower bound of s_A(m,n,2) = Ω(m^{1-2/(n+3)}); this bound was previously known only for n = 3,5 [Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2020; Mirza Galib Anwarul Husain Baig et al., 2019; Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2018; Mirza Galib Anwarul Husain Baig et al., 2019; Mirza Galib Anwarul Husain Baig and Deepanjan Kesh, 2020]. We consider the quantum version of the problem, where access to the bit-string b ∈ {0,1}^s is provided in the form of a quantum oracle that performs the transformation 𝒪_b: |i⟩ ↦ (-1)^{b_i} |i⟩. Let s_Q(m,n,2) denote the minimum length of the bit string that solves the above set membership problem in the quantum model (with adaptive queries but no error). We show that for all n ≤ m^{1/8}, we have s_{QA}(m,n,2) = 𝒪(m^{7/8}). This upper bound makes crucial use of Nash-William’s theorem [Diestel, 2005] for decomposing a graph into forests. This result is significant because, prior to this work, it was not known if quantum schemes yield any advantage over classical schemes. We also consider schemes that make a small number of quantum non-adaptive probes. In particular, we show that the space required in this case, s_{QN}(m,n = 2,t = 2) = O(√m) and s_{QN}(m,n = 2,t = 3) = O(m^{1/3}); in contrast, it is known that two non-adaptive classical probes yield no savings. Our quantum schemes are simple and use only the fact that the XOR of two bits of memory can be computed using just one quantum query to the oracle.

Cite as

Shyam S. Dhamapurkar, Shubham Vivek Pawar, and Jaikumar Radhakrishnan. Set Membership with Two Classical and Quantum Bit Probes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 52:1-52:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dhamapurkar_et_al:LIPIcs.ICALP.2022.52,
  author =	{Dhamapurkar, Shyam S. and Pawar, Shubham Vivek and Radhakrishnan, Jaikumar},
  title =	{{Set Membership with Two Classical and Quantum Bit Probes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{52:1--52:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.52},
  URN =		{urn:nbn:de:0030-drops-163932},
  doi =		{10.4230/LIPIcs.ICALP.2022.52},
  annote =	{Keywords: set membership problem, bit probe complexity, graphs with high girth, quantum data structure}
}

Document

DOI: 10.4230/LIPIcs.STACS.2022.41

Fairly Popular Matchings and Optimality

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices have strict preferences over their neighbors. A matching M is popular if for any matching N, the number of vertices that prefer M is at least the number that prefer N; thus M does not lose a head-to-head election against any matching where vertices are voters. It is easy to find popular matchings; however when there are edge costs, it is NP-hard to find (or even approximate) a min-cost popular matching. This hardness motivates relaxations of popularity. Here we introduce fairly popular matchings. A fairly popular matching may lose elections but there is no good matching (wrt popularity) that defeats a fairly popular matching. In particular, any matching that defeats a fairly popular matching does not occur in the support of any popular mixed matching. We show that a min-cost fairly popular matching can be computed in polynomial time and the fairly popular matching polytope has a compact extended formulation. We also show the following hardness result: given a matching M, it is NP-complete to decide if there exists a popular matching that defeats M. Interestingly, there exists a set K of at most m popular matchings in G (where |E| = m) such that if a matching is defeated by some popular matching in G then it has to be defeated by one of the matchings in K.

Cite as

Telikepalli Kavitha. Fairly Popular Matchings and Optimality. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.STACS.2022.41,
  author =	{Kavitha, Telikepalli},
  title =	{{Fairly Popular Matchings and Optimality}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{41:1--41:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.41},
  URN =		{urn:nbn:de:0030-drops-158516},
  doi =		{10.4230/LIPIcs.STACS.2022.41},
  annote =	{Keywords: Bipartite graphs, Stable matchings, Mixed matchings, Polytopes}
}

Document

DOI: 10.4230/LIPIcs.STACS.2022.49

One-Way Communication Complexity and Non-Adaptive Decision Trees

Authors: Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. More generally, we show the following when the gadget is Inner Product on 2b input bits for all b ≥ 2, denoted IP. - If f is a total Boolean function that depends on all of its n input bits, then the bounded-error one-way quantum communication complexity of f∘IP equals Ω(n(b-1)). - If f is a partial Boolean function, then the deterministic one-way communication complexity of f∘IP is at least Ω(b ⋅ 𝖣_{dt}^ → (f)), where 𝖣_{dt}^ → (f) denotes non-adaptive decision tree complexity of f. To prove our quantum lower bound, we first show a lower bound on the VC-dimension of f∘IP. We then appeal to a result of Klauck [STOC'00], which immediately yields our quantum lower bound. Our deterministic lower bound relies on a combinatorial result independently proven by Ahlswede and Khachatrian [Adv. Appl. Math.'98], and Frankl and Tokushige [Comb.'99]. It is known due to a result of Montanaro and Osborne [arXiv'09] that the deterministic one-way communication complexity of f∘XOR equals the non-adaptive parity decision tree complexity of f. In contrast, we show the following when the inner gadget is the AND function on 2 input bits. - There exists a function for which even the quantum non-adaptive AND decision tree complexity of f is exponentially large in the deterministic one-way communication complexity of f∘AND. - However, for symmetric functions f, the non-adaptive AND decision tree complexity of f is at most quadratic in the (even two-way) communication complexity of f∘AND. In view of the first bullet, a lower bound on non-adaptive AND decision tree complexity of f does not lift to a lower bound on one-way communication complexity of f∘AND. The proof of the first bullet above uses the well-studied Odd-Max-Bit function. For the second bullet, we first observe a connection between the one-way communication complexity of f and the Möbius sparsity of f, and then give a lower bound on the Möbius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result. It is well known that the rank of the communication matrix of a function F is an upper bound on its deterministic one-way communication complexity. This bound is known to be tight for some F. However, in our final result we show that this is not the case when F = f∘AND. More precisely we show that for all f, the deterministic one-way communication complexity of F = f∘AND is at most (rank(M_{F}))(1 - Ω(1)), where M_{F} denotes the communication matrix of F.

Cite as

Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.STACS.2022.49,
  author =	{Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail},
  title =	{{One-Way Communication Complexity and Non-Adaptive Decision Trees}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.49},
  URN =		{urn:nbn:de:0030-drops-158598},
  doi =		{10.4230/LIPIcs.STACS.2022.49},
  annote =	{Keywords: Decision trees, communication complexity, composed Boolean functions}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2021.31

Property B: Two-Coloring Non-Uniform Hypergraphs

Authors: Jaikumar Radhakrishnan and Aravind Srinivasan

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract

The following is a classical question of Erdős (Nordisk Matematisk Tidskrift, 1963) and of Erdős and Lovász (Colloquia Mathematica Societatis János Bolyai, vol. 10, 1975). Given a hypergraph ℱ with minimum edge-size k, what is the largest function g(k) such that if the expected number of monochromatic edges in ℱ is at most g(k) when the vertices of ℱ are colored red and blue randomly and independently, then we are guaranteed that ℱ is two-colorable? Duraj, Gutowski and Kozik (ICALP 2018) have shown that g(k) ≥ Ω(log k). On the other hand, if ℱ is k-uniform, the lower bound on g(k) is much higher: g(k) ≥ Ω(√{k / log k}) (Radhakrishnan and Srinivasan, Rand. Struct. Alg., 2000). In order to bridge this gap, we define a family of locally-almost-uniform hypergraphs, for which we show, via the randomized algorithm of Cherkashin and Kozik (Rand. Struct. Alg., 2015), that g(k) can be much higher than Ω(log k), e.g., 2^Ω(√{log k}) under suitable conditions.

Cite as

Jaikumar Radhakrishnan and Aravind Srinivasan. Property B: Two-Coloring Non-Uniform Hypergraphs. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 31:1-31:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{radhakrishnan_et_al:LIPIcs.FSTTCS.2021.31,
  author =	{Radhakrishnan, Jaikumar and Srinivasan, Aravind},
  title =	{{Property B: Two-Coloring Non-Uniform Hypergraphs}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{31:1--31:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.31},
  URN =		{urn:nbn:de:0030-drops-155428},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.31},
  annote =	{Keywords: Hypergraph coloring, Propery B}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2020.28

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

Authors: Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m,n,t) (resp. s_N(m,n,t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2,t ≥ ⌊log n⌋+1 . In this work, we improve this bound when the probes are allowed to be superlinear in n, i.e., when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m,n,t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m,n,3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i.e., s_N(m,2,3) ≥ Ω(√m).

Cite as

Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy. Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.MFCS.2020.28,
  author =	{Dey, Palash and Radhakrishnan, Jaikumar and Velusamy, Santhoshini},
  title =	{{Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.28},
  URN =		{urn:nbn:de:0030-drops-126965},
  doi =		{10.4230/LIPIcs.MFCS.2020.28},
  annote =	{Keywords: Set membership, Bit-probe model, Fully-explicit data structures, Adaptive data structures, Error-correcting codes}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.34

Revisiting Alphabet Reduction in Dinur’s PCP

Authors: Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep

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

Abstract

Dinur’s celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the expense of a fixed constant factor loss in the soundness gap). We note that the gap amplification can produce a Label Cover CSP. This allows us to reduce the alphabet size via a direct long-code based reduction from Label Cover to a Boolean CSP. Our composition step thus bypasses the concept of Assignment Testers from Dinur’s proof, and we believe it is more intuitive - it is just a gadget reduction. The analysis also uses only elementary facts (Parseval’s identity) about Fourier Transforms over the hypercube.

Cite as

Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2020.34,
  author =	{Guruswami, Venkatesan and Opr\v{s}al, Jakub and Sandeep, Sai},
  title =	{{Revisiting Alphabet Reduction in Dinur’s PCP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{34:1--34:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.34},
  URN =		{urn:nbn:de:0030-drops-126372},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.34},
  annote =	{Keywords: PCP theorem, CSP, discrete Fourier analysis, label cover, long code}
}

Document

DOI: 10.4230/LIPIcs.CCC.2019.14

Equality Alone Does not Simulate Randomness

Authors: Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is "Equality". In this work we show that even allowing access to an "Equality" oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on n bits with randomized one-sided communication complexity O(log n), but such that every deterministic protocol with access to "Equality" oracle needs Omega(n) cost to compute it. Additionally we exhibit a natural and strict infinite hierarchy within BPP, starting with the class P^{EQ} at its bottom.

Cite as

Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality Alone Does not Simulate Randomness. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 14:1-14:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2019.14,
  author =	{Chattopadhyay, Arkadev and Lovett, Shachar and Vinyals, Marc},
  title =	{{Equality Alone Does not Simulate Randomness}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{14:1--14:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.14},
  URN =		{urn:nbn:de:0030-drops-108368},
  doi =		{10.4230/LIPIcs.CCC.2019.14},
  annote =	{Keywords: Communication lower bound, derandomization}
}

Document

DOI: 10.4230/LIPIcs.ESA.2017.39

Distance-Preserving Subgraphs of Interval Graphs

Authors: Kshitij Gajjar and Jaikumar Radhakrishnan

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We consider the problem of finding small distance-preserving subgraphs of undirected, unweighted interval graphs that have k terminal vertices. We show that every interval graph admits a distance-preserving subgraph with O(k log k) branching vertices. We also prove a matching lower bound by exhibiting an interval graph based on bit-reversal permutation matrices. In addition, we show that interval graphs admit subgraphs with O(k) branching vertices that approximate distances up to an additive term of +1.

Cite as

Kshitij Gajjar and Jaikumar Radhakrishnan. Distance-Preserving Subgraphs of Interval Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gajjar_et_al:LIPIcs.ESA.2017.39,
  author =	{Gajjar, Kshitij and Radhakrishnan, Jaikumar},
  title =	{{Distance-Preserving Subgraphs of Interval Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{39:1--39:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.39},
  URN =		{urn:nbn:de:0030-drops-78798},
  doi =		{10.4230/LIPIcs.ESA.2017.39},
  annote =	{Keywords: interval graphs, shortest path, distance-preserving subgraphs, bit-reversal permutation matrix}
}

Document

DOI: 10.4230/LIPIcs.STACS.2017.38

Set Membership with Non-Adaptive Bit Probes

Authors: Mohit Garg and Jaikumar Radhakrishnan

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract

We consider the non-adaptive bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vector in order to answer membership queries of the form "Is x in S?" by non-adaptively probing the bit vector at t places. Let s_N(m,n,t) be the minimum number of bits of storage needed for such a scheme. In this work, we show existence of non-adaptive and adaptive schemes for a range of t that improves an upper bound of Buhrman, Miltersen, Radhakrishnan and Srinivasan (2002) on s_N(m,n,t). For three non-adaptive probes, we improve the previous best lower bound on s_N(m,n,3) by Alon and Feige (2009).

Cite as

Mohit Garg and Jaikumar Radhakrishnan. Set Membership with Non-Adaptive Bit Probes. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.STACS.2017.38,
  author =	{Garg, Mohit and Radhakrishnan, Jaikumar},
  title =	{{Set Membership with Non-Adaptive Bit Probes}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.38},
  URN =		{urn:nbn:de:0030-drops-69952},
  doi =		{10.4230/LIPIcs.STACS.2017.38},
  annote =	{Keywords: Data Structures, Bit-probe model, Compression, Bloom filters, Expansion}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2016.16

The Zero-Error Randomized Query Complexity of the Pointer Function

Authors: Jaikumar Radhakrishnan and Swagato Sanyal

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

Abstract

The pointer function of Goos, Pitassi and Watson and its variants have recently been used to prove separation results among various measures of complexity such as deterministic, randomized and quantum query complexity, exact and approximate polynomial degree, etc. In particular, Ambainis et al. (STOC 2016) obtained the widest possible (quadratic) separations between deterministic and zero-error randomized query complexity, as well as between bounded-error and zero-error randomized query complexity by considering variants of this pointer function. However, as Ambainis et al. pointed out in their work, the precise zero-error complexity of the original pointer function was not known. We show a lower bound of ~Omega(n^{3/4}) on the zero-error randomized query complexity of the pointer function on Theta(n * log(n)) bits; since an ~O(n^{3/4}) upper bound was already shown by Mukhopadhyay and Sanyal (FSTTCS 2015), our lower bound is optimal up to polylog factors. We, in fact, consider a generalization of the original function and obtain lower bounds for it that are optimal up to polylog factors.

Cite as

Jaikumar Radhakrishnan and Swagato Sanyal. The Zero-Error Randomized Query Complexity of the Pointer Function. 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. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{radhakrishnan_et_al:LIPIcs.FSTTCS.2016.16,
  author =	{Radhakrishnan, Jaikumar and Sanyal, Swagato},
  title =	{{The Zero-Error Randomized Query Complexity of the Pointer Function}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{16:1--16:13},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.16},
  URN =		{urn:nbn:de:0030-drops-68514},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.16},
  annote =	{Keywords: Deterministic Decision Tree, Randomized Decision Tree, Query Complexity, Models of Computation.}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2016.135

Partition Bound Is Quadratically Tight for Product Distributions

Authors: Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

Let f: {0,1}^n*{0,1}^n -> {0,1} be a 2-party function. For every product distribution mu on {0,1}^n*{0,1}^n, we show that CC^{mu}_{0.49}(f) = O(log(prt_{1/8}(f))*log(log(prt_{1/8}(f)))^2), where CC^{mu}_{epsilon}(f) is the distributional communication complexity of f with error at most epsilon under the distribution mu and prt_{1/8}(f) is the partition bound of f, as defined by Jain and Klauck [Proc. 25th CCC, 2010]. We also prove a similar bound in terms of IC_{1/8}(f), the information complexity of f, namely, CC^{mu}_{0.49}(f) = O((IC_{1/8}(f)*log(IC_{1/8}(f)))^2). The latter bound was recently and independently established by Kol [Proc. 48th STOC, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let g: {0,1}^n -> {0,1} be a function. For every bit-wise product distribution mu on {0,1}^n, we show that QC^{mu}_{0.49}(g) = O((log(qprt_{1/8}(g))*log(log(qprt_{1/8}(g))))^2), where QC^{mu}_{epsilon}(g) is the distributional query complexity of f with error at most epsilon under the distribution mu and qprt_{1/8}(g) is the query partition bound of the function g. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for product distributions.

Cite as

Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan. Partition Bound Is Quadratically Tight for Product Distributions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 135:1-135:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{harsha_et_al:LIPIcs.ICALP.2016.135,
  author =	{Harsha, Prahladh and Jain, Rahul and Radhakrishnan, Jaikumar},
  title =	{{Partition Bound Is Quadratically Tight for Product Distributions}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{135:1--135:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.135},
  URN =		{urn:nbn:de:0030-drops-62708},
  doi =		{10.4230/LIPIcs.ICALP.2016.135},
  annote =	{Keywords: partition bound, product distribution, communication complexity, query complexity}
}

66 Search Results for "Radhakrishnan, Jaikumar"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message