Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Hardness Condensation by Restriction
 
conference paper

Hardness Condensation by Restriction

Göös, Mika  
•
Newman, Ilan
•
Riazanov, Artur  
Show more
Mohar, Bojan
•
Shinkar, Igor
Show more
June 10, 2024
Proceedings of the Annual ACM Symposium on Theory of Computing
56 ACM Symposium on Theory of Computing

Can every n-bit boolean function with deterministic query complexity k≪ n be restricted to O(k) variables such that the query complexity remains ω(k)? That is, can query complexity be condensed via restriction? We study such hardness condensation questions in both query and communication complexity, proving two main results. Negative: Query complexity cannot be condensed in general: There is a function f with query complexity k such that any restriction of f to O(k) variables has query complexity O(k3/4). Positive: Randomised communication complexity can be condensed for the sink-of-xor function. This yields a quantitatively improved counterexample to the log-approximate-rank conjecture, achieving parameters conjectured by Chattopadhyay, Garg, and Sherif (2021). Along the way we show the existence of Shearer extractors - a new type of seeded extractor whose output bits satisfy prescribed dependencies across distinct seeds.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3618260.3649711
Scopus ID

2-s2.0-85196645564

Author(s)
Göös, Mika  

École Polytechnique Fédérale de Lausanne

Newman, Ilan

University of Haifa

Riazanov, Artur  

École Polytechnique Fédérale de Lausanne

Sokolov, Dmitry

École Polytechnique Fédérale de Lausanne

Editors
Mohar, Bojan
•
Shinkar, Igor
•
O�Donnell, Ryan
Date Issued

2024-06-10

Publisher

Association for Computing Machinery

Published in
Proceedings of the Annual ACM Symposium on Theory of Computing
ISBN of the book

9798400703836

Start page

2016

End page

2027

Subjects

communication complexity

•

hardness condensation

•

query complexity

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL5  
Event nameEvent acronymEvent placeEvent date
56 ACM Symposium on Theory of Computing

Vancouver, Canada

2024-06-24 - 2024-06-28

Available on Infoscience
January 26, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/244944
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés