A selection from the ITCS'18 program

Here is a partial list of papers (which I read and liked) that will be part of the ITCS'18 program.

Oded's comments

Pseudo-Deterministic Proofs by Shafi Goldwasser, Ofer Grossman and Dhiraj Holden

This work extends the notion of Pseudo-Determinism (see posts Nr 80 and 206) to the domain of proofs. A search problem $R$ is said to have a pseudodeterministic interactive proof system (psdIP) if there exists a function $s$ such that the set $\{(x,s(x)):x\in S_R\}$ has an interactive proof system, where $S_R$ denote the set of instances that have solutions wrt $R$. Among the results is a two-round psdIP for graph isomorphism, and a characterization of the latter class. (Note that psdIP coindices with search problems computable in polynomial space.)

Zero-Knowledge Proofs of Proximity by Itay Berman, Ron Rothblum and Vinod Vaikuntanathan

This work applies the notion of zero-knowledge to the domain of proofs of proximity, where the verifier runs in time that is sublinear in the length of the input. In this context, zero-knowledge means that whatever can be obtained from the prover in significantly sub-linear time can also be obtained from scratch. In particular, the prover should not yield bits of information that require reading the entire input.

Relaxed Locally Correctable Codes by Tom Gur, Govind Ramnarayan and Ron Rothblum

This work extends the notion of relaxed locally decodable codes to the case of locally correctable codes (LCC). The relaxation (see Sec 4.2 in HERE) means that the decoder/corrector may announce failure if the codeword is corrupted, and otherwise output the correct value (whp). The work presents rLCC both in the constant query regime and in the constant rate regime.

Learning by Refuting by Pravesh K Kothari and Roi Livni

An independent result of Salil Vadhan relates distribution-free PAC learning to refutation. The current result realted agnostic learning wrt a fixed distribution to a notion of imperfect refutation.

Edge Estimation with Independent Set Oracles by Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian and Makrand Sinha

This paper considers estimating the number of edges in a graph when allowed powerful queries such as are there edges between two disjoint sets of vertices. I think it is interesting to explore the power of this (and other) natural types of queries.

ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network by Irit Dinur and Pasin Manurangsi

This paper considers the complexity of 2-CSPs as a function of the number of the number of variables, when the alphabet size may be much bigger (i.e., super-polynomial in the number of variables). Using ETH, it shows an almost optimal hardness result for this regime.

Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs by Shay Solomon

For a graph property $\Pi$, a measure of approximation (wrt $\Pi$), and a family of input graphs (e.g., bounded aboricity), the paper considers the problem of producing a graph of bounded degree that is a subgraph of the input graph and approximates the value wrt $\Pi$. For example, finds a bounded-egree graph that approximates the size of the vertex cover in the input graph, which (only) has bounbded aboricity.

The original abstracts

See the ITCS'16 program.

Back to list of Oded's choices.