Tung's page

About me

See my page at my home institution.
Project
Fine-grained space complexity. Mentored by Marshall Ball at NYU.
Research interests
Parameterized and approximation algorithms (preferably both at the same time :) ), computational complexity.

About my project

Edit Distance can be solved in quadratic time (using dynamic programming). An algorithm with truly subquadratic time seems elusive. Fine-grained complexity tries to answer why this is the case. Surprisingly, if Strong Exponential Time Hypothesis, which is a conjecture about NP-complete problems, holds, then it implies that Edit Distance (among other problems in P) cannot be solved faster than using a naive algorithm.

The goal is to develop theory similar to fine-grained complexity for memory instead of running time.

Weekly log

Week 7 & Week 8

Writing and making slides.

Week 6

I have started to write down the black-box separation of collision-resistant hash functions and sequentially hard functions. The main difficulty is that the papers I used to learn about these types of separations (1, 2) use the term "reduction" differently than what I am used to from complexity. The audacity.

Week 5

We have decided that the most attainable goal for now is to prove that collision-resistant hash functions do not imply sequentially hard functions.

We received news from Stefano Tessaro about a fix to the "Proofs of Space" paper. The fix concerns the strong assumptions mentioned previously. The updated version is called "Proofs of Catalytic Space". Michal Koucký wrote a very nice crash course on Catalytic Computation.

Week 4

I met my co-worker, Peter Fenteany, for the first time on Monday. We tried to break collision resistance of cryptographic hash functions under the assumption that we can break their sequentiality. There's not much progress in this direction yet.

We have decided that the goal for the foreseeable future is to construct explicit languages that is not parallelizable (i.e., not solvable by resource-constrained circuits) on average.

Week 3

I met my mentor in person for the first time in NYC. We realized that the paper "Proofs of Sequential Work" is not of much interest to us. Instead, we will try to understand whether worst-case space hardness implies anything about average-case space hardness. My mentor also gave me a crash course in worst-case to average-case reductions.

Also, we managed to switch topics twice in a week and now we will also focus black-box reductions.

Week 2

We have realized that what we originally wanted to extend (Proofs of Space) require too strong of assumptions. Thus we are shifting gears a little bit and returning to Proofs of Sequential Work. (do not confuse with Proofs of Work used by e.g. Bitcoin)

Week 1

After my arrival to the US, I connected with my mentor and his graduate student, who I will be working with. I prepared a presentation on what I think my research topic will be.

Log of a first-timer in the US

I found sweetn't bread in a grocery store. Photo documentation is coming soon. The pictures will be clear, unlike pictures of a yeti or the Loch Ness monster. I didn't do a taste test though.

I managed to fix some bicycles.

Wendy's 5 for 5 (plus tax of course) and their selection of drinks is my biggest discovery of this week.

Target >> Walmart. I cannot believe the graduate coordinator suggested Walmart over Target for the initial grocery trip.

Also I my advisor had a breakthrough in my PhD research project. Nevermind, it didn't work.

Presentations

Acknowledgements

This work was carried out while the author Tung Anh Vu was a participant in the 2022 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.