DIMACS
DIMACS REU 2021

General Information

Name: Sasha Sami
Email: sashasami03@gmail.com
Home Institution: Charles University

Weekly Summary

Week 1

It was an exciting first week. I met with my mentor and fellow students (Noah and Vishal). I started going through the papers given by our mentor, on results around hardness of MCSP (Minimum circuit size problem) and MKTP (a variant of bounded Kolmogorov complexity). The papers are a thick read. I came across a lot of new complexity classes like TC0, AC0[p], SZK etc. Till now I had only seen polynomial time and logspace reductions, but as part of the reading I came across reductions carried out by circuits as well. We will now start preparing for our first presentation.

Week 2

We had our first presentation on Tuesday. Post that we started looking at the paper on MCSP and Graph Isomorphism, which proves BPP_m reduction from Graph Isomorphism to MKTP. It also had some lemmas (eg. blockking lemma/encoding lemma) which helps extend the result to: reduction from Entropy Approximation (BPP_m) to MKTP (in the REU paper). But the paper also lists down why is to difficult to extend the same technique to MCSP (broadly due to lack of tight bounds for circuit size of boolean functions on n variables). Extending the same technique as for MKTP, would require exponential independent trials (though I could not work out the complete details!, yet to see this for myself).
Post this we started looking at the Coin problem paper, which gives a "reduction" from the Coin problem to MCSP (Coin problem is not a language). The paper proves that Coin problem can be solved in AC0[MCSP]. And using oracles for coin problem one can solve MAJORITY (in AC0). The aim behind reading this paper was to see if it were possible to obtain a projection_m (or AC0_m) reduction from MAJORITY to MCSP. As replacing bunch of oracles for MCSP, with a single oracle in the end seems difficult, we are trying to see what can be said about concatenation of inputs to 2 MCSP oracles in MAJORITY to MCSP (AC0[MCSP]), to a single query to MCSP oracle (actual reduction has bunch of MCSP oracles (polynomially many), but answering this scaled down question also seems quite difficult to me!).

Week 3

We moved our attention to MFSP (Minimum formula size problem), the "memoryless" version of MCSP. The aim being to be able to show coin problem is reducible to MFSP as well, implying there is a AC0 circuit with oracle to MFSP would solve MAJORITY. And come up with a way so that instead of multiple, a single query to oracle is made (AC0_m reduction). As a part of it I started looking at Lupanov theorems for formula sizes. The hope is that given truth tables of f and g it would be easier to argue about formula size of the combined truth table (as opposed to circuit size).

Week 4

I continued to think about the reduction from Majority to Coin problem (and thus to MCSP), trying to think about the simplified version of where we want to combine two queries queries to MCSP into a single one. I started thinking about the natural interpretation where we want to reduce L, the language of pairs of truth tables f and g and a threshold s such that at least one corresponding Boolean function has circuit complexity greater than s. But such a reduction is unknown even under P/Poly reductions. I am still trying to understand if the multiple queries are related in some manner. I was made aware by Eric and Noah that the tools available (as per book by Wegner), in relation to circuit complexity for Boolean functions to their direct product (f(x,y) = g(x) V h(y)) are not good enough to help us combine truth tables (and making one query). Though I don't quite fully understand why and how direct product fits in, I intend to look into it more.

Week 5

Noah came up with approach using ideas in the Coin problem paper, to give a randomized projection from Majority to MCSP. I tried to just follow the approach he mentioned to check it for myself. I had some basic doubts which he Noah helped me clear. There was a place where with the given Union bound with the ceoncentraion inequality did not go through. But Noah was able to adjust the bound (went through as polynomial sampling involved), converting it to determinstic projection (non-uniform). Later I still thought about some minute details, as to me the proof helped distinguish between strings having < pN and [pN,1/2] ones (N is the input length). I connected with Noah later, and got the underlying idea was to pad the original string enough to reduce to the problem mentioned. Though I was not fully convinced, and plan to connect with Noah again once he writes down the proof.

Week 6

I went through the paper on NP-hardness of constant depth formula version of MCSP (under quasi-polynomial time randomized reduction, by Rahul Illango). The intention being to see if the reduction can be computed in AC_0 (Turing reduction, quasi polynomial sized circuits). The paper was a thick read for me. Though I could not digest the proofs in entirety, the reduction seems to have broadly three parts to be checked for. Along with that I started reading the paper by Bin Fu, which shows that if MCSP is ZPP-hard under polynomial truth table reduction, then it would imply ZPP != EXP (an open question). The intention to check see if one can prove that showing such a result is difficult ie. ZPP hardness under quasi poly. sized AC_0 reduction would imply ZPP != EXP.

Week 7

I completed reading the paper by Bin Fu (Implication of ZPP Hardness of MCSP). With minor modifications to the proof we were able to show that: If MCSP is ZPP hard under uniform quasi-polynomial sized AC0 non-adaptive Turing reduction, would imply EXP != ZPP.
I switched back to looking at the part around hardness of approximation of min-DNF (one of the three parts in Illango's construction). I started reading the paper by Allender et. al. (on Hardness of Min-DNF). Looking at the reductions: Max3SAT ---> Lable Cover ---> Set Cover ---> min-DNF(*) ---> Min-DNF (Gap versions of these problems), all seem to possible using quasi-polynomial sized uniform AC0_m reduction, except for one part where "partial set systems" are to be created (though this is possible with non-uniform circuits). The partial set system construction seems to be crucial for reduction from Lablel cover to Set cover (though I have to look more into it). We also noticed a trivial observation that NISZK_L = NISZK_{NC^1} (relates to one of the open questions given by our mentor, around robustness of NISZK_L).

Week 8

I continued looking into hardness of approximation of min-DNF. The original proof gives an \omega(log^{\delta}(n)) approximation ratio (which implies hardness for approximation within constant factor, which is what we are interested in). I found The proof for deterministic construction of "partial set systems" difficult to understand. A simple randomized reduction exists though (in Set-Cover Hardness of Approximation, by Feige). Towards the end of the week, Eric told us that he thinks randomization would be necessary while proving [Illango] construction holds for quasi polynomial AC_0 reduction as well. SO I reverted to look at the randomized construction of partial set systems. I plan to verify this construction goes through quasi-poly. AC_0. I am yet to look into the various parts involved in proving the hardness of approximation of Set Cover.

Week 9

We worked on our final report and presentation. We came across some gaps in our work while writing down the report, namely

  1. Fu result cannot be extended to constant depth formula/circuit version of MCSP.
  2. Though likely to be true, expected circuit complexity for p-biased (p \in [0,1/2]) strings is a monotonic function, is an open question (which was required for the proof for Majority to MCSP reduction).


Our team


Presentations


References & Links

Here are some relevant resources:
  1. Previous REU paper
  2. MCSP and Graph Isomorphism
  3. Coin Problem to MCSP
  4. Majority to Coin problem
  5. Book by Ingo Wegener on Complexity of Boolean circuits
  6. Boolean Function Complexity (book by Jukna, Stasys)
  7. Hardness of Constant depth formula version of MCSP
  8. Implication of ZPP Hardness of MCSP (under tt-p reductions)
  9. Hardness of Min-DNF
  10. Hardness of Approximating Minimization problems
  11. Set-Cover Hardness of Approximation

Acknowledgements

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