Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Reconstructing weighted voting schemes from partial information about
  their power indices   A number of recent works [Goldberg 2006; O'Donnell and Servedio 2011; De,
Diakonikolas, and Servedio 2017; De, Diakonikolas, Feldman, and Servedio 2014]
have considered the problem of approximately reconstructing an unknown weighted
voting scheme given information about various sorts of ``power indices'' that
characterize the level of control that individual voters have over the final
outcome. In the language of theoretical computer science, this is the problem
of approximating an unknown linear threshold function (LTF) over $\{-1, 1\}^n$
given some numerical measure (such as the function's $n$ ``Chow parameters,''
a.k.a. its degree-1 Fourier coefficients, or the vector of its $n$ Shapley
indices) of how much each of the $n$ individual input variables affects the
outcome of the function.
  In this paper we consider the problem of reconstructing an LTF given only
partial information about its Chow parameters or Shapley indices; i.e. we are
given only the Chow parameters or the Shapley indices corresponding to a subset
$S \subseteq [n]$ of the $n$ input variables. A natural goal in this partial
information setting is to find an LTF whose Chow parameters or Shapley indices
corresponding to indices in $S$ accurately match the given Chow parameters or
Shapley indices of the unknown LTF. We refer to this as the Partial Inverse
Power Index Problem.
  Our main results are a polynomial time algorithm for the
($\varepsilon$-approximate) Chow Parameters Partial Inverse Power Index Problem
and a quasi-polynomial time algorithm for the ($\varepsilon$-approximate)
Shapley Indices Partial Inverse Power Index Problem.

10
The categories of this paper are: q-bio
29
The categories of this paper are: funct-an
0
The categories of this paper are: hep-ph
35
The categories of this paper are: mtrl-th
19
The categories of this paper are: eess
9
The categories of this paper are: nlin
14
The categories of this paper are: math-ph
27
The categories of this paper are: comp-gas
20
The categories of this paper are: acc-phys
36
The categories of this paper are: cmp-lg
4
The categories of this paper are: cond-mat
17
The categories of this paper are: q-fin
34
The categories of this paper are: chem-ph
11
The categories of this paper are: hep-lat
12
The categories of this paper are: nucl-th
22
The categories of this paper are: chao-dyn