BIBLIOS

   Ciências References Management System

Visitor Mode (Login)
Need help?


Back

Publication details

Document type
Conference papers

Document subtype
Full paper

Title
One-Way Communication Complexity and Non-Adaptive Decision Trees

Participants in the publication
Nikhil S. Mande (Author)
Swagato Sanyal (Author)
Suhail Sherif (Author)
Dep. Matemática
Summary
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs.

Date of Publication
2022-03-09

Event
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Publication Identifiers
ISBN - 9783959772228

Document Identifiers
DOI - https://doi.org/10.4230/LIPIcs.STACS.2022.49

Rankings
CORE A (2021) - - 4613 - Theory of computation

Download

Export

APA
Nikhil S. Mande, Swagato Sanyal, Suhail Sherif, (2022). One-Way Communication Complexity and Non-Adaptive Decision Trees. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), -

IEEE
Nikhil S. Mande, Swagato Sanyal, Suhail Sherif, "One-Way Communication Complexity and Non-Adaptive Decision Trees" in 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), , 2022, pp. -, doi: 10.4230/LIPIcs.STACS.2022.49

BIBTEX
@InProceedings{60205, author = {Nikhil S. Mande and Swagato Sanyal and Suhail Sherif}, title = {One-Way Communication Complexity and Non-Adaptive Decision Trees}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, year = 2022, pages = {-}, address = {}, publisher = {} }