Reviews: Solving Marginal MAP Problems with NP Oracles and Parity Constraints

There are pros and cons in this article. On the one hand, the idea of approximating complex MMAP queries using a series of random constrained optimization problems is conceptually simple and opens the door to many potential improvements. Furthermore, I really appreciated the diversity of experimental domains used to evaluate the method. On the other hand, I have several concerns about the approximation bounds and the optimization oracle. For the unweighted case, we have a bound of 4 c and, to ensure that the denominator \alpha(c) of the complexity parameter T is greater or equal than 1, c must be greater or equal than 5, which roughly means an approximation constant about one thousand.