Zobrazeno 1 - 10
of 36
pro vyhledávání: '"Vasudev, Yadu"'
Autor:
Roy, Sampriti, Vasudev, Yadu
We study distribution testing in the standard access model and the conditional access model when the memory available to the testing algorithm is bounded. In both scenarios, the samples appear in an online fashion and the goal is to test the properti
Externí odkaz:
http://arxiv.org/abs/2309.03245
Autor:
Arvind, V., Datta, Samir, Khan, Asif, Sharma, Shivdutt, Vasudev, Yadu, Vasudevan, Shankar Ram
Let $G$ be a finite group given as input by its multiplication table. For a subset $S$ of $G$ and an element $g\in G$ the Cayley Group Membership Problem (denoted CGM) is to check if $g$ belongs to the subgroup generated by $S$. While this problem is
Externí odkaz:
http://arxiv.org/abs/2308.10073
Dynamic Complexity was introduced by Immerman and Patnaik PI97 in the nineties and has seen a resurgence of interest with the positive resolution of their conjecture on directed reachability in DynFO DKMSZ18. Since then many natural problems related
Externí odkaz:
http://arxiv.org/abs/2206.00371
Dynamic Complexity was introduced by Immerman and Patnaik \cite{PatnaikImmerman97} (see also \cite{DongST95}). It has seen a resurgence of interest in the recent past, see \cite{DattaHK14,ZeumeS15,MunozVZ16,BouyerJ17,Zeume17,DKMSZ18,DMVZ18,BarceloRZ1
Externí odkaz:
http://arxiv.org/abs/2008.05728
Publikováno v:
45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 52:1-52:14, 2018
We consider one-sided error property testing of $\mathcal{F}$-minor freeness in bounded-degree graphs for any finite family of graphs $\mathcal{F}$ that contains a minor of $K_{2,k}$, the $k$-circus graph, or the $(k\times 2)$-grid for any $k\in\math
Externí odkaz:
http://arxiv.org/abs/1707.06126
Autor:
Fichtenberger, Hendrik, Vasudev, Yadu
We study the problem of testing conductance in the setting of distributed computing and give a two-sided tester that takes $\mathcal{O}(\log(n) / (\epsilon \Phi^2))$ rounds to decide if a graph has conductance at least $\Phi$ or is $\epsilon$-far fro
Externí odkaz:
http://arxiv.org/abs/1705.08174
Distribution testing deals with what information can be deduced about an unknown distribution over $\{1,\ldots,n\}$, where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended
Externí odkaz:
http://arxiv.org/abs/1609.06736
We initiate a thorough study of \emph{distributed property testing} -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called \emph{dense} testing model we emulate sequential tes
Externí odkaz:
http://arxiv.org/abs/1602.03718
We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a f
Externí odkaz:
http://arxiv.org/abs/1504.00695
Let $G =$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. M
Externí odkaz:
http://arxiv.org/abs/1201.3181