Previous Conferences & Workshops

I want to show proofs for two things: (1) what kind of complicated structures can a player build in a "generalized Tic-Tac-Toe game", and (2) how to get the "exact solutions" of infinitely many games. I'll try to illustrate the ideas on simple...

We present new PCPs for NP-complete languages. The PCPs are only n poly log n bits long, when proving satisfiability of formulae of length n. However, the probabilistic verifier needs to query poly log n bits of the proof to verify it. In contrast...

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed...

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a graph G=(V,E) and a set of pairs of vertices (s_1,t_1), (s_2,t_2), ..., (s_k,t_k). The objective is to decide if all the pairs can be...