419 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Massachusetts Institute of TechnologyUS181 papers
- Vilnius UniversityLT180 papers
- Boğaziçi UniversityTR178 papers
- Deutsches Elektronen-Synchrotron DESYDE178 papers
- University of Nebraska–LincolnUS178 papers
- Bulgarian Academy of SciencesBG176 papers
- Sofia University "St. Kliment Ohridski"BG175 papers
- University of BristolGB175 papers
- University of HelsinkiFI175 papers
- University of AntwerpBE174 papers
- University of BelgradeRS174 papers
- University of Notre DameUS174 papers
Showing 2015 · cs.CCShow all
2 papers · 2 filters
cs.CC2015★ 19 cited
Nearly optimal separations between communication (or query) complexity and partitions
Robin Kothari
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a r…
cs.CC2015
Almost quadratic gap between partition complexity and query/communication complexity
Andris Ambainis, Martins Kokainis
We show nearly quadratic separations between two pairs of complexity measures: 1. We show that there is a Boolean function with where is t…