BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Extending the idea in [Impagliazzo, R., Moore, C. and Russell, A., An entropic proof of Chang's inequality. SIAM Journal on Discrete Mathematics, 28(1), pp.173-176.] we give a short information theoretic proof for Chang's lemma that is based on Pinsker's inequality.
We show conflict complexity of every total Boolean function, recently introduced in [Swagato Sanyal. A composition theorem via conict complexity. arXiv preprint arXiv:1801.03285, 2018.] to prove a composition theorem of randomized decision tree complexity, is at least a half of its block sensitivity. We propose to compare conflict complexity with certificate complexity, and explain why it could be interesting.
We introduce a new type of adversary for online graph problems. The new adversary is parameterized by a single integer κ, which upper bounds the number of connected components that the adversary can use at any time during the presentation of the online graph G. We call this adversary "κ components bounded", or κ-CB for short. On one hand, this adversary is restricted compared to the classical adversary because of the κ-CB constraint. On the other hand, we seek competitive ratios parameterized only by κ with no dependence on the input length n, thereby giving the new adversary power to use arbitrarily large inputs. We study online coloring under the κ-CB adversary. We obtain finer analysis of the existing algorithms FirstFit and CBIP by computing their competitive ratios on trees and bipartite graphs under the new adversary. Surprisingly, FirstFit outperforms CBIP on trees. When it comes to bipartite graphs FirstFit is no longer competitive under the new adversary, while CBIP uses at most 2κ colors. We also study several well known classes of graphs, such as 3-colorable, Ck-free, d-inductive, planar, and bounded treewidth, with respect to online coloring under the κ-CB adversary. We demonstrate that the extra adversarial power of unbounded input length outweighs the restriction on the number of connected components leading to non existence of competitive algorithms for these classes.
We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of ε. For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order Ω(h(ε)) and O(h(ε)). Here h denotes the binary entropy function. We analyze the case of the two-bit AND function in detail to show that for this function the gain is Θ(h(ε)). This answers a question of [M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, From information to exact communication (extended abstract), STOC'13]. We obtain sharp bounds for the set disjointness function of order n. For the case of the distributional error, we introduce a new protocol that achieves a gain of Θ(h(ε)) provided that n is sufficiently large. We apply these results to answer another of question of Braverman et al. regarding the randomized communication complexity of the set disjointness function. Answering a question of [Mark Braverman, Interactive information complexity, STOC'12], we apply our analysis of the set disjointness function to establish a gap between the two different notions of the prior-free information cost. This implies that amortized randomized communication complexity is not necessarily equal to the amortized distributional communication complexity with respect to the hardest distribution.
Given α1,...,αm∈(0,1), we characterize all integrable functions f:[0,1]m→C satisfying ∫A1×...×Amf=0 for any collection of disjoint sets A1,...,Am⊆[0,1] of respective measures α1,...,αm. We use this characterization to settle some of the conjectures in [S. Janson and V. Sós, More on quasi-random graphs, subgraph counts and graph limits, arXiv:1405.6808].
For any pair of real numbers (i,j) with 0<i,j<1 and i+j=1, we prove that the set of p-adic mixed (i,j)-badly approximable numbers $\bad_p(i, j)$ is 1/2-winning in the sense of Schmidt's game. This improves a recent result of Badziahin, Levesley, and Velani on mixed Schmidt conjecture.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.