14

SODA 2023 | Gödel's Lost Letter and P=NP

 2 years ago
source link: https://rjlipton.wpcomstaging.com/2023/03/01/soda-2023/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Traces of strings, plus ways of tracing accepted papers

Anindya De was at Northwestern University and is now at the University of Pennsylvania—see here.

ad.jpg?resize=250%2C250&ssl=1

He was advised by two of the top advisors ever there were: Luca Trevisan and Umesh Vazirani.

Traces

I recently ran across a great paper by Anindya titled Approximate Trace Reconstruction from a Single Trace. It is co-authored with Xi Chen (Columbia University), Chin Ho Lee (Harvard University), and Rocco Servedio and Sandip Sinha (Columbia University). Notice that we did not put an Oxford comma between Servedio and Sinha as they are both from Columbia. The paper appeared at SODA 2023 this January.

Here are pointers to the almost 200 papers that were in the conference. I put this together before discovering the site conference-publishing.com, which as mentioned in my STOC 2023 post generates paper lists with links for a host of conferences. So I did all the following links myself. Do scroll past the list to the bottom to read a little more about traces which Ken and I put together.

The Trace Result

The trace problem begins by sending a binary string of length through a deletion channel with parameter . Each bit entering the channel survives with probability to be part of the output string . That is, is deleted with probability . The deletions are independent. For an unknown string , the problem is:

Given strings produced by runs of the channel on , reconstruct if possible. Else, calculate a binary string of length that minimizes a distance metric . The metric of choice is to maximize the length of the longest common subsequence (not necessarily contiguous) of and , which corresponds to minimizing their edit distance.

As indicated by its title “Approximate Trace Reconstruction from a Single Trace,” the paper tackles the extreme case . Of course one cannot reconstruct (unless no deletions occur so ) so the game is to find that are most likely to have produced the lone observed . The scoring function takes the expectation of over both the generation of from the true and the run of the algorithm guessing from . There are two main questions:

  • How well does the algorithm perform—relative to theoretically optimal choices given —when itself is generated uniformly at random?
  • How well does the algorithm perform when is generated adversarially? Note that is still probabilistic, and the performance of both the theoretical optimal algorithm and their algorithm are evaluated based on the distribution of for the fixed (unseen) .

These questions are posed for small, medium, and large values of . When the deletion probability is close to , the strings are most often tiny. One would think they offer no help in coming close to . However, they do help efficient algorithms come close to the optimal policy for a worst-case chosen . The paradoxical results of their paper, in their own words (but reversing their order), are:

  1. In the average-case setting, having access to a single trace is provably not very useful: no algorithm, computationally efficient or otherwise, can achieve significantly higher accuracy given one trace that is bits long than it could with no traces.
  2. Having access to a single trace is already quite useful for worst-case trace reconstruction: an efficient algorithm can perform much more accurate reconstruction, given one trace that is even only a few bits long, than it could given no traces at all.

The deep point is that when as well as is random, seeing gives little advantage to both the optimal strategy (which does not know ) and their algorithm. Whereas, when is fixed, the knowledge of is more valuable to the optimal strategy and separates it from the case of not seeing at all. However, the profit given by even a short is one that is apprehendable by a complexity-limited deterministic algorithm that sees only . That’s our attempt at an intuitive takeaway; as always we invite readers to consult the paper in detail.

Open Problems

Comparing my list of pointer to the papers from SODA, which was a bit of trouble to create by hand, to the STOC’23 output from the conference-publishing site, leads to a curious question:

Do we scan lists of papers more by looking for subject words in their titles or looking for authors we know?

Well, I have not found SODA’23 on that website, where authors too would be given; for me, copying the authors would more than double the manual work.

Like this:

Loading...

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK