Hardness Condensation and Log Approximate Rank Conjecture

October 20, 2023

2023   ·   query   algorithms     ·   fall-2023  

Speaker

Artur Riazanov October 20, 2023.

Abstract

Can a function f: {0,1}^n -> {0,1} of query complexity k « n be restricted to O(k) variables such that its query complexity remains to be Omega(k)? That is, can query complexity be condensed via restriction? We study this question for query and communication complexity. On the negative side, we show that query complexity can not be condensed. In this talk, however, I will focus on a positive result in this direction: a function Sink o XOR that was used to falsify the log approximate rank conjecture (LARC) can be condensed in the sense above. The condensation is itself a stronger counterexample to LARC which was sought by Chattopadhyay, Garg, and Sherif (2021). Based on the joint work with Mika Göös, Ilan Newman, and Dmitry Sokolov.



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • On the Probabilistic Degree of an n-variate Boolean Function
  • Improved Quantum Query Upper Bounds Based on Classical Decision Trees
  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • A better-than-3 log n depth lower bound for De Morgan formulas with restrictions on top gates
  • Are quantum speedups for learning expressive classes possible?