Depth Tradeoffs for Clique and Connectivity

October 06, 2023

2023   ·   distributed   algorithms     ·   fall-2023  

Speaker

Ben Rossman October 6, 2023.

Abstract

This talk will give an overview of size-depth tradeoffs for the important k-CLIQUE and DISTANCE-k CONNECTIVITY problems. In particular, I will discuss recent lower bounds for AC0 circuits and formulas that were obtained – via a novel “lifting” technique – from tradeoffs in the parameters of simpler combinatorial objects (e.g. subgraph coverings of the order-k path graph). In the talk, I will explain the underlying combinatorial tradeoffs; say a few words about lifting technique; and discuss the big-picture questions of P vs NP and NC1 vs L that motivate this work.



Enjoy Reading This Article?

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

  • Glauber Dynamics, expander graphs, and rapid mixing, a survey of problems and techniques
  • Foundations of Lattice-based Cryptography
  • Improved Quantum Query Upper Bounds Based on Classical Decision Trees
  • Machine Learning for Quantum Many-body Physics
  • On Probabilistic Approximations of Boolean Functions via Polynomials, and Polynomial Closure Statements over the Boolean Cube