1,902 research outputs found
sj-pdf-1-jbr-10.1177_07487304221077662 – Supplemental material for VANESSA—Shiny Apps for Accelerated Time-series Analysis and Visualization of Drosophila Circadian Rhythm and Sleep Data
No full textSupplemental material, sj-pdf-1-jbr-10.1177_07487304221077662 for VANESSA—Shiny Apps for Accelerated Time-series Analysis and Visualization of Drosophila Circadian Rhythm and Sleep Data by Arijit Ghosh and Vasu Sheeba in Journal of Biological Rhythms</p
On the complexity of triangle counting using emptiness queries
No full textBeame et al. [ITCS'18 & TALG'20] introduced and used the Bipartite Independent Set (BIS) and Independent Set (IS) oracle access to an unknown, simple, unweighted and undirected graph and solved the edge estimation problem. The introduction of this oracle set forth a series of works in a short time that either solved open questions mentioned by Beame et al. or were generalizations of their work as in Dell and Lapinskas [STOC'18 and TOCT'21], Dell, Lapinskas, and Meeks [SODA'20 and SICOMP'22], Bhattacharya et al. [ISAAC'19 & TOCS'21], and Chen et al. [SODA'20]. Edge estimation using BIS can be done using polylogarithmic queries, while IS queries need sub-linear but more than polylogarithmic queries. Chen et al. improved Beame et al.’s upper bound result for edge estimation using IS and also showed an almost matching lower bound. Beame et al. in their introductory work asked a few open questions out of which one was on estimating structures of higher order than edges, like triangles and cliques, using BIS queries. In this work, we almost resolve the query complexity of estimating triangles using BIS oracle. While doing so, we prove a lower bound for an even stronger query oracle called Edge Emptiness (EE) oracle, recently introduced by Assadi, Chakrabarty, and Khanna [ESA'21] to test graph connectivity
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube
No full textUsing geometric techniques like projection and dimensionality reduction, we show that there exists a randomized sub-linear time algorithm that can estimate the Hamming distance between two matrices. Consider two matrices A and B of size n × n whose dimensions are known to the algorithm but the entries are not. The entries of the matrix are real numbers. The access to any matrix is through an oracle that computes the projection of a row (or a column) of the matrix on a vector in {0,1}ⁿ. We call this query oracle to be an Inner Product oracle (shortened as IP). We show that our algorithm returns a (1± ε) approximation to {D}_M (A,B) with high probability by making O(n/(√{{D)_M (A,B)}}poly(log n, 1/(ε))) oracle queries, where {D}_M (A,B) denotes the Hamming distance (the number of corresponding entries in which A and B differ) between two matrices A and B of size n × n. We also show a matching lower bound on the number of such IP queries needed. Though our main result is on estimating {D}_M (A,B) using IP, we also compare our results with other query models
Abhilashetal_eclosion_temperature_SOM_revision2_15082019_1 – Supplemental material for Selection for Timing of Eclosion Results in Co-evolution of Temperature Responsiveness in Drosophila melanogaster
No full textSupplemental material, Abhilashetal_eclosion_temperature_SOM_revision2_15082019_1 for Selection for Timing of Eclosion Results in Co-evolution of Temperature Responsiveness in Drosophila melanogaster by Lakshman Abhilash, Arijit Ghosh and Vasu Sheeba in Journal of Biological Rhythms</p
Replication Project, Code Repository - Can Technology Solve the Principal-Agent Problem? Evidence from China’s War on Air Pollution (Greenstone et al, 2022)
No full textThis page is respiratory for the [additional] code used in the replication of the paper by Greenstone et al (2022): Can Technology Solve the Principal-Agent Problem? Evidence from China’s War on Air Pollution. This paper was replicated as part of the replication games project led by Abel Brodeur with the Institute for Replication (https://i4replication.org/). The replication team consisted of Cloé Garnache (Oslo Metropolitan University), Garreth Gibney (University of Galway) and Ghosh Arijit (TBC). The code uploaded is complementary to the replication package for the paper. You can find this replication package at: https://www.openicpsr.org/openicpsr/project/125321/version/V1/vie
Query Complexity of Global Minimum Cut
No full textIn this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, where the graph can be accessed through local queries like Degree, Neighbor, and Adjacency queries.
Given ε ∈ (0,1), the algorithm with high probability outputs an estimate t̂ satisfying the following (1-ε) t ≤ t̂ ≤ (1+ε) t, where t is the size of minimum cut in the graph. The expected number of local queries used by our algorithm is min{m+n,m/t}poly(log n,1/(ε)) where n and m are the number of vertices and edges in the graph, respectively. Eden and Rosenbaum showed that Ω(m/t) local queries are required for approximating the size of minimum cut in graphs, {but no local query based algorithm was known. Our algorithmic result coupled with the lower bound of Eden and Rosenbaum [APPROX 2018] resolve the query complexity of the problem of estimating the size of minimum cut in graphs using local queries.}
Building on the lower bound of Eden and Rosenbaum, we show that, for all t ∈ ℕ, Ω(m) local queries are required to decide if the size of the minimum cut in the graph is t or t-2. Also, we show that, for any t ∈ ℕ, Ω(m) local queries are required to find all the minimum cut edges even if it is promised that the input graph has a minimum cut of size t. Both of our lower bound results are randomized, and hold even if we can make Random Edge queries in addition to local queries
Almost optimal query algorithm for hitting set using a subset query
No full textGiven access to the hypergraph through a subset query oracle in the query
model, we give sublinear time algorithms for Hitting-Set with almost tight
parameterized query complexity. In parameterized query complexity, we estimate
the number of queries to the oracle based on the parameter , the size of the
Hitting-Set. The subset query oracle we use in this paper is called Generalized
-partite Independent Set query oracle (GPIS) and it was introduced by Bishnu
et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite
Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and
TALG'20) for estimating the number of edges in graphs. Formally, GPIS is
defined as follows: GPIS oracle for a -uniform hypergraph
takes as input pairwise disjoint non-empty subsets of
vertices in and answers whether there is a hyperedge in
that intersects each set , where . } For
, the GPIS oracle is nothing but BIS oracle.
We show that -Hitting-Set, the hitting set problem for -uniform
hypergraphs, can be solved using GPIS
queries. Additionally, we also showed that -Decesion-Hitting-Set, the
decision version of -Hitting-Set can be solved with
{\sc GPIS} queries. We complement these parameterized upper bounds
with an almost matching parameterized lower bound that states that any
algorithm that solves -Decesion-Hitting-Set requires GPIS queries.Comment: 22 pages. A preliminary version has appeared in ISAAC'19 and the full
version has been accepted in JCS
Triangle Estimation Using Tripartite Independent Set Queries
No full textEstimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an approximate triangle counting algorithm using only polylogarithmic queries when the number of triangles on any edge in the graph is polylogarithmically bounded. Our query oracle Tripartite Independent Set (TIS) takes three disjoint sets of vertices A, B and C as input, and answers whether there exists a triangle having one endpoint in each of these three sets. Our query model generally belongs to the class of group queries (Ron and Tsur, ACM ToCT, 2016; Dell and Lapinskas, STOC 2018) and in particular is inspired by the Bipartite Independent Set (BIS) query oracle of Beame et al. (ITCS 2018). We extend the algorithmic framework of Beame et al., with TIS replacing BIS, for triangle counting using ideas from color coding due to Alon et al. (J. ACM, 1995) and a concentration inequality for sums of random variables with bounded dependency (Janson, Rand. Struct. Alg., 2004)
Counting and Sampling from Substructures Using Linear Algebraic Queries
No full textFor an unknown n × n matrix A having non-negative entries, the inner product (IP) oracle takes as inputs a specified row (or a column) of A and a vector ∈ ℝⁿ with non-negative entries, and returns their inner product. Given two input vectors x and y in ℝⁿ with non-negative entries, and an unknown matrix A with non-negative entries with IP oracle access, we design almost optimal sublinear time algorithms for the following two fundamental matrix problems:
- Find an estimate for the bilinear form x^T A y such that ≈ x^T A y.
- Designing a sampler for the entries of the matrix A such that ℙ( = (i,j)) ≈ x_i A_{ij} y_j /(x^T A y), where x_i and y_j are i-th and j-th coordinate of and respectively. As special cases of the above results, for any submatrix of an unknown matrix with non-negative entries and IP oracle access, we can efficiently estimate the sum of the entries of any submatrix, and also sample a random entry from the submatrix with probability proportional to its weight. We will show that the above results imply that if we are given IP oracle access to the adjacency matrix of a graph, with non-negative weights on the edges, then we can design sublinear time algorithms for the following two fundamental graph problems:
- Estimating the sum of the weights of the edges of an induced subgraph, and
- Sampling edges proportional to their weights from an induced subgraph. We show that compared to the classical local queries (degree, adjacency, and neighbor queries) on graphs, we can get a quadratic speedup if we use IP oracle access for the above two problems.
Apart from the above, we study several matrix problems through the lens of IP oracle, like testing if the matrix is diagonal, symmetric, doubly stochastic, etc. Note that IP oracle is in the class of linear algebraic queries used lately in a series of works by Ben-Eliezer et al. [SODA'08], Nisan [SODA'21], Rashtchian et al. [RANDOM'20], Sun et al. [ICALP'19], and Shi and Woodruff [AAAI'19]. Recently, IP oracle was used by Bishnu et al. [RANDOM'21] to estimate dissimilarities between two matrices
Faster Counting and Sampling Algorithms Using Colorful Decision Oracle
No full textIn this work, we consider d-Hyperedge Estimation and d-Hyperedge Sample problem in a hypergraph H(U(H),F(H)) in the query complexity framework, where U(H) denotes the set of vertices and F(H) denotes the set of hyperedges. The oracle access to the hypergraph is called Colorful Independence Oracle (CID), which takes d (non-empty) pairwise disjoint subsets of vertices A₁,…, A_d ⊆ U(ℋ) as input, and answers whether there exists a hyperedge in H having (exactly) one vertex in each A_i, i ∈ {1,2,…,d}. The problem of d-Hyperedge Estimation and d-Hyperedge Sample with CID oracle access is important in its own right as a combinatorial problem. Also, Dell et al. [SODA '20] established that decision vs counting complexities of a number of combinatorial optimization problems can be abstracted out as d-Hyperedge Estimation problems with a CID oracle access.
The main technical contribution of the paper is an algorithm that estimates m = |F(H)| with m̂ such that
1/(C_{d)log^{d-1} n) ≤ m̂/m ≤ C_{d} log ^{d-1} n.
by using at most C_{d}log ^{d+2} n many CID queries, where n denotes the number of vertices in the hypergraph H and C_d is a constant that depends only on d}. Our result coupled with the framework of Dell et al. [SODA '21] implies improved bounds for the following fundamental problems:
Edge Estimation using the Bipartite Independent Set (BIS). We improve the bound obtained by Beame et al. [ITCS '18, TALG '20].
Triangle Estimation using the Tripartite Independent Set (TIS). The previous best bound for the case of graphs with low co-degree (Co-degree for an edge in the graph is the number of triangles incident to that edge in the graph) was due to Bhattacharya et al. [ISAAC '19, TOCS '21], and Dell {et al.}’s result gives the best bound for the case of general graphs [SODA '21]. We improve both of these bounds.
Hyperedge Estimation & Sampling using Colorful Independence Oracle (CID). We give an improvement over the bounds obtained by Dell et al. [SODA '21]
- …
