## 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

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.)
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.
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.
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.
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.
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.