Batuhan Arasli

Mr. Batuhan Arasli

orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 November 2019 in Information
Verified
Journal Article
Open access
PDF file
YWYi-Peng Wei
Yi-Peng Wei
BABatuhan Arasli
Batuhan Arasli
KBKarim Banawan
Karim Banawan
SUSennur Ulukus
Sennur Ulukus
We consider the private information retrieval (PIR) problem from decentralized uncoded caching databases. There are two phases in our problem setting, a caching phase, and a retrieval phase. In the caching phase, a data center containing all the K files, where each file is of size L bits, and several databases with storage size constraint μ K L bits exist in the system. Each database independently chooses μ K L bits out of the total K L bits from the data center to cache through the same probability distribution in a decentralized manner. In the retrieval phase, a user (retriever) accesses N databases in addition to the data center, and wishes to retrieve a desired file privately. We characterize the optimal normalized download cost to be D * = ∑ n = 1 N + 1 N n − 1 μ n − 1 ( 1 − μ ) N + 1 − n 1 + 1 n + ⋯ + 1 n K − 1. We show that uniform and random caching scheme which is originally proposed for decentralized coded caching by Maddah-Ali and Niesen, along with Sun and Jafar retrieval scheme which is originally proposed for PIR from replicated databases surprisingly results in the lowest normalized download cost. This is the decentralized counterpart of the recent result of Attia, Kumar, and Tandon for the centralized case. The converse proof contains several ingredients such as interference lower bound, induction lemma, replacing queries and answering string random variables with the content of distributed databases, the nature of decentralized uncoded caching databases, and bit marginalization of joint caching distributions.

12 January 2023 in Information
Verified
Journal Article
Open access
PDF file
BABatuhan Arasli
Batuhan Arasli
SUSennur Ulukus
Sennur Ulukus
The group testing idea is an efficient infection identification approach based on pooling the test samples of a group of individuals, which results in identification with less number of tests than individually testing the population. In our work, we propose a novel infection spread model based on a random connection graph which represents connections between n individuals. Infection spreads via connections between individuals, and this results in a probabilistic cluster formation structure as well as non-i.i.d. (correlated) infection statuses for individuals. We propose a class of two-step sampled group testing algorithms where we exploit the known probabilistic infection spread model. We investigate the metrics associated with two-step sampled group testing algorithms. To demonstrate our results, for analytically tractable exponentially split cluster formation trees, we calculate the required number of tests and the expected number of false classifications in terms of the system parameters, and identify the trade-off between them. For such exponentially split cluster formation trees, for zero-error construction, we prove that the required number of tests is O(log2n). Thus, for such cluster formation trees, our algorithm outperforms any zero-error non-adaptive group test, binary splitting algorithm, and Hwang’s generalized binary splitting algorithm. Our results imply that, by exploiting probabilistic information on the connections of individuals, group testing can be used to reduce the number of required tests significantly even when the infection rate is high, contrasting the prevalent belief that group testing is useful only when the infection rate is low.

2 January 2023 in Algorithms
Verified
Journal Article
Open access
PDF file
BABatuhan Arasli
Batuhan Arasli
SUSennur Ulukus
Sennur Ulukus
Group testing idea is an efficient approach to detect prevalence of an infection in the test samples taken from a group of individuals. It is based on the idea of pooling the test samples and performing tests to the mixed samples. This approach results in possible reduction in the required number of tests to identify infections. Classical group testing works consider static settings where the infection statuses of the individuals do not change throughout the testing process. In our paper, we study a dynamic infection spread model, inspired by the discrete time SIR model, where infections are spread via non-isolated infected individuals, while infection keeps spreading over time, a limited capacity testing is performed at each time instance as well. In contrast to the classical, static group testing problem, the objective in our setup is not to find the minimum number of required tests to identify the infection status of every individual in the population, but to control the infection spread by detecting and isolating the infections over time by using the given, limited number of tests. In order to analyze the performance of the proposed algorithms, we focus on the average-case analysis of the number of individuals that remain non-infected throughout the process of controlling the infection. We propose two dynamic algorithms that both use given limited number of tests to identify and isolate the infections over time, while the infection spreads, while the first algorithm is a dynamic randomized individual testing algorithm, in the second algorithm we employ the group testing approach similar to the original work of Dorfman. By considering weak versions of our algorithms, we obtain lower bounds for the performance of our algorithms. Finally, we implement our algorithms and run simulations to gather numerical results and compare our algorithms and theoretical approximation results under different sets of system parameters.

1 July 2019
Verified
Conference Paper
Closed access
KBKarim Banawan
Karim Banawan
BABatuhan Arasli
Batuhan Arasli
YWYi-Peng Wei
Yi-Peng Wei
SUSennur Ulukus
Sennur Ulukus
We consider private information retrieval (PIR) of a single file out of K files from N non-colluding databases with heterogeneous storage constraints m = (m 1 , ⋯, m N ). The aim of this work is to jointly design the content placement phase and the retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint $\mu = \frac{1}{N}\sum\nolimits_{n = 1}^N {{m_n}} $. We show the optimum content placement explicitly for N = 3.

25 February 2019 in arXiv
Verified
Preprint
Open access
PDF file
KBKarim Banawan
Karim Banawan
BABatuhan Arasli
Batuhan Arasli
YWYi-Peng Wei
Yi-Peng Wei
SUSennur Ulukus
Sennur Ulukus
We consider private information retrieval (PIR) of a single file out of $K$ files from $N$ non-colluding databases with heterogeneous storage constraints $\mathbf{m}=(m_1, \cdots, m_N)$. The aim of this work is to jointly design the content placement phase and the information retrieval phase in order to minimize the download cost in the PIR phase. We characterize the optimal PIR download cost as a linear program. By analyzing the structure of the optimal solution of this linear program, we show that, surprisingly, the optimal download cost in our heterogeneous case matches its homogeneous counterpart where all databases have the same average storage constraint $\mu=\frac{1}{N} \sum_{n=1}^{N} m_n$. Thus, we show that there is no loss in the PIR capacity due to heterogeneity of storage spaces of the databases. We provide the optimum content placement explicitly for $N=3$.

29 March 2022 in arXiv
Verified
Preprint
Open access
PDF file
BABatuhan Arasli
Batuhan Arasli
SUSennur Ulukus
Sennur Ulukus
We propose a novel infection spread model based on a random connection graph which represents connections between $n$ individuals. Infection spreads via connections between individuals and this results in a probabilistic cluster formation structure as well as a non-i.i.d. (correlated) infection status for individuals. We propose a class of two-step sampled group testing algorithms where we exploit the known probabilistic infection spread model. We investigate the metrics associated with two-step sampled group testing algorithms. To demonstrate our results, for analytically tractable exponentially split cluster formation trees, we calculate the required number of tests and the expected number of false classifications in terms of the system parameters, and identify the trade-off between them. For such exponentially split cluster formation trees, for zero-error construction, we prove that the required number of tests is $O(\log_2n)$. Thus, for such cluster formation trees, our algorithm outperforms any zero-error non-adaptive group test, binary splitting algorithm, and Hwang's generalized binary splitting algorithm. Our results imply that, by exploiting probabilistic information on the connections of individuals, group testing can be used to reduce the number of required tests significantly even when infection rate is high, contrasting the prevalent belief that group testing is useful only when infection rate is low.