Emirhan Gürpınar

Emirhan Gürpınar

Auto-generated profile, based on publicly available information

Emirhan Gürpınar

LIRMM, CNRS and Univ. Montpellier, Montpellier, France

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

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

Representative Publications

View All Publications
14 April 2020
Verified
Book Chapter
Open access
PDF file
SBSiddharth Barman
Siddharth Barman
OFOmar Fawzi
Omar Fawzi
SGSuprovat Ghoshal
Suprovat Ghoshal
EGEmirhan Gürpınar
Emirhan Gürpınar
In the classic maximum coverage problem, we are given subsets \(T_1, \dots , T_m\) of a universe [n] along with an integer k and the objective is to find a subset \(S \subseteq [m]\) of size k that maximizes \(C(S) := |\cup _{i \in S} T_i|\). It is well-known that the greedy algorithm for this problem achieves an approximation ratio of \((1-e^{-1})\) and there is a matching inapproximability result. We note that in the maximum coverage problem if an element \(e \in [n]\) is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, \(C^{(\infty )}(S) = \sum _{i \in S} |T_i|\), which can be easily maximized under a cardinality constraint. We study the maximum \(\ell \)-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to \(\ell \) times but no more; hence, we consider maximizing the function \(C^{(\ell )}(S) = \sum _{e \in [n]} \min \{\ell , |\{i \in S : e \in T_i\}| \}\), subject to the constraint \(|S| \le k\). Note that the case of \(\ell = 1\) corresponds to the standard maximum coverage setting and \(\ell = \infty \) gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of \(1 - \frac{\ell ^{\ell }e^{-\ell }}{\ell !}\) for the \(\ell \)-multi-coverage problem. In particular, when \(\ell = 2\), this factor is \(1-2e^{-2} \approx 0.73\) and as \(\ell \) grows the approximation ratio behaves as \(1 - \frac{1}{\sqrt{2\pi \ell }}\). We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture. This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as combinatorial auctions.

10 September 2024 in ACM Transactions on Computation Theory
Verified
Journal Article
Open access
EGEmirhan Gürpιnar
Emirhan Gürpιnar
ARAndrei Romashchenko
Andrei Romashchenko
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y , respectively. We determine the worst-case communication complexity of this problem for the setting where the parties can use private sources of random bits. We show that for some x , y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key, the size of which is much smaller than the mutual information between x and y . However, we discuss a natural class of x , y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses the spectral properties of appropriate graphs and the expander mixing lemma, as well as information-theoretic techniques, including constraint information inequalities and Muchnik’s conditional descriptions. A preliminary version of this article was published in the proceedings of MFCS 2020. In the present version, we give full proofs of all theorems and get rid of the assumption that the number of random bits used in the communication protocols is polynomial.

26 June 2022
Verified
Conference Paper
Open access
EGEmirhan Gürpınar
Emirhan Gürpınar
Secret sharing is a central topic in information-theoretical cryptography. In a secret sharing scheme a random secret is distributed among participants so that only the qualified subsets of parties can recover the secret. In this paper we improve previously known [13] lower bounds on the size of the largest share for several specific access structures. Our approach is based on non-Shannon-type information inequalities. We employ the linear programming (LP) technique that permits to apply new information inequalities indirectly. To reduce computational complexity of the involved linear programs we extensively use symmetry considerations.

18 October 2023 in arXiv
Verified
Preprint
Open access
PDF file
EGEmirhan Gürpınar
Emirhan Gürpınar
This paper is on developing some computer-assisted proof methods involving non-classical inequalities for Shannon entropy. Two areas of the applications of information inequalities are studied: Secret sharing schemes and hat guessing games. In the former a random secret value is transformed into shares distributed among several participants in such a way that only the qualified groups of participants can recover the secret value. In the latter each participant is assigned a hat colour and they try to guess theirs while seeing only some of the others'. The aim is to maximize the probability that every player guesses correctly, the optimal probability depends on the underlying sight graph. We use for both problems the method of non-Shannon-type information inequalities going back to Z. Zhang and R. W. Yeung. We employ the linear programming technique that allows to apply new information inequalities indirectly, without even writing them down explicitly. To reduce the complexity of the problems of linear programming involved in the bounds we extensively use symmetry considerations. Using these tools, we improve lower bounds on the ratio of key size to secret size for the former problem and an upper bound for one of the ten vertex graphs related to an open question by Riis for the latter problem.