Zobrazeno 1 - 10
of 44
pro vyhledávání: '"Varma, Nithin"'
In this paper, we study the problem of finding an envy-free allocation of indivisible goods among multiple agents. EFX, which stands for envy-freeness up to any good, is a well-studied relaxation of the envy-free allocation problem and has been shown
Externí odkaz:
http://arxiv.org/abs/2410.13580
A binary code Enc$:\{0,1\}^k \to \{0,1\}^n$ is $(0.5-\epsilon,L)$-list decodable if for all $w \in \{0,1\}^n$, the set List$(w)$ of all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between Enc$(m)$ and $w$ is at most $0.5 -\epsi
Externí odkaz:
http://arxiv.org/abs/2409.01708
In this paper, we address the problem of determining an envy-free allocation of indivisible goods among multiple agents. EFX, which stands for envy-free up to any good, is a well-studied problem that has been shown to exist for specific scenarios, su
Externí odkaz:
http://arxiv.org/abs/2301.10632
In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain $[n]$. Specifically, we present a nonadaptive algorithm that, given inputs $\eps \in (0,1), s \in \mathbb{N}$, and oracle
Externí odkaz:
http://arxiv.org/abs/2110.13012
Publikováno v:
Proceedings, Innovations in Theoretical Computer Science (ITCS), 2022
We initiate the study of sublinear-time algorithms that access their input via an online adversarial erasure oracle. After answering each query to the input object, such an oracle can erase $t$ input values. Our goal is to understand the complexity o
Externí odkaz:
http://arxiv.org/abs/2109.08745
Autor:
Newman, Ilan, Varma, Nithin
Publikováno v:
TheoretiCS, Volume 3 (January 12, 2024) theoretics:10131
For a permutation $\pi:[k] \to [k]$, a function $f:[n] \to \mathbb{R}$ contains a $\pi$-appearance if there exists $1 \leq i_1 < i_2 < \dots < i_k \leq n$ such that for all $s,t \in [k]$, $f(i_s) < f(i_t)$ if and only if $\pi(s) < \pi(t)$. The functi
Externí odkaz:
http://arxiv.org/abs/2106.04856
We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjac
Externí odkaz:
http://arxiv.org/abs/2011.14291
Autor:
Newman, Ilan, Varma, Nithin
Estimating the length of the longest increasing subsequence (LIS) in an array is a problem of fundamental importance. Despite the significance of the LIS estimation problem and the amount of attention it has received, there are important aspects of t
Externí odkaz:
http://arxiv.org/abs/2010.05805
Autor:
Varma, Nithin, Yoshida, Yuichi
In modern applications of graphs algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full information of a graph being studied. Hence, it is desirable to use algorithms
Externí odkaz:
http://arxiv.org/abs/1904.03248
Autor:
Chikhi, Rayan, Jovicic, Vladan, Kratsch, Stefan, Medvedev, Paul, Milanic, Martin, Raskhodnikova, Sofya, Varma, Nithin
We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bioinformatics. The behavior of the parameter is poorly understood. The c
Externí odkaz:
http://arxiv.org/abs/1805.04765