ﻻ يوجد ملخص باللغة العربية
The {em Total Influence} ({em Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function ifnumplusminus=1 $f: {pm1}^n longrightarrow {pm1}$, else $f: bitset^n to bitset$, fi which we denote by $I[f]$. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of $(1pm eps)$ by performing $O(frac{sqrt{n}log n}{I[f]} poly(1/eps)) $ queries. % mnote{D: say something about technique?} We also prove a lower bound of % $Omega(frac{sqrt{n/log n}}{I[f]})$ $Omega(frac{sqrt{n}}{log n cdot I[f]})$ on the query complexity of any constant-factor approximation algorithm for this problem (which holds for $I[f] = Omega(1)$), % and $I[f] = O(sqrt{n}/log n)$), hence showing that our algorithm is almost optimal in terms of its dependence on $n$. For general functions we give a lower bound of $Omega(frac{n}{I[f]})$, which matches the complexity of a simple sampling algorithm.
We study the problem of maximizing a monotone $k$-submodular function $f$ under a knapsack constraint, where a $k$-submodular function is a natural generalization of a submodular function to $k$ dimensions. We present a deterministic $(frac12-frac{1}
Submodular maximization is a general optimization problem with a wide range of applications in machine learning (e.g., active learning, clustering, and feature selection). In large-scale optimization, the parallel running time of an algorithm is gove
We consider the well-studied problem of finding a perfect matching in $d$-regular bipartite graphs with $2n$ vertices and $m = nd$ edges. While the best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes $O(m sqrt{n})$ time
We study variants of Mastermind, a popular board game in which the objective is sequence reconstruction. In this two-player game, the so-called textit{codemaker} constructs a hidden sequence $H = (h_1, h_2, ldots, h_n)$ of colors selected from an alp
Sorting a Permutation by Transpositions (SPbT) is an important problem in Bioinformtics. In this paper, we improve the running time of the best known approximation algorithm for SPbT. We use the permutation tree data structure of Feng and Zhu and imp