Abstract-In a coordination problem, users in a network observing correlated inputs collaborate to evaluate possibly randomized functions of the inputs. Problems of this kind have been widely studied in the information theory literature.
Abstract: In modern applications of graph 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.
Abstract: We present a general framework, applicable to both truthful and non-truthful auctions, for designing approximately revenue-optimal mechanisms for multi-item additive auctions.
Abstract: We study the sum of squares (*SOS*) representation of polynomials, i.e. f = \sum_{i\in s} c_i f_i^2 , where c_i are field elements and f_i(x_1,\ldots,x_n) are polynomials.