In this talk I will describe nondeterministic reductions which yield new direct product theorems (DPTs) for Boolean circuits. In our theorems one assumes that a function F is "mildly hard" against *nondeterministic* circuits of some size s(n) , and concludes that the t-fold direct product F^t is "extremely hard" against probabilistic circuits of only polynomially smaller size s'(n) . The main advantage of these results compared with previous DPTs is the strength of the size bound in our conclusion.
Computer Science and Discrete Mathematics (CSDM)
We present practically efficient methods for proving correctness of announced results of a computation while keeping input and intermediate values information theoretically secret. These methods are applied to solve the long standing problem of preventing collusion in second-price auctions.
Informally, uncertainty principle says that function and its Fourier transform can not be both concentrated. Uncertainty principle has a lot of applications in areas like compressed sensing, error correcting codes, number theory and many others. In this talk we will try to survey different formulations of uncertainty principle. In this talk we will be mostly focused on the discreet analog of uncertainty principle.
We propose an “analytical” framework for studying parallel repetitions of one-round two-prover games. We define a new relaxation of the value of a game, val+, and prove that it is both multiplicative and a good approximation for the true value of the game. These two properties imply Raz's parallel repetition theorem as
$val(G^k) ~ val+(G^k) = val+(G)^k ~ val(G)^k$
Using this approach, we will describe a reasonably simple proof for the NP-hardness for $label-cover(1,delta)$, the starting point of many inapproximability results.
We give an arithmetic version of the recent proof of the improved triangle removal lemma by Fox [Fox11], for the group $F_2^n$.