اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDisjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
74
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The disjointness problem - where Alice and Bob are given two subsets of ${1, dots, n}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $Theta(n)$, it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik-Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by $d$, we analyze how large can the deterministic and randomized communication complexities be, as a function of $d$ and $n$. In this paper, we construct two natural set systems of VC dimension $d$, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be $widetilde{Theta}left(dlog left( n/d right)right)$ for set systems of VC dimension $d$ and this matches the deterministic upper bound for all set systems of VC dimension $d$. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exists set systems of VC dimension $d$ such that both deterministic and randomized (one-way and multi-round) complexity for the set intersection problem can be as high as $Thetaleft( dlog left( n/d right) right)$, and this is tight among all set systems of VC dimension $d$.
قيم البحث
اقرأ أيضاً
We investigate the feasibility of sample average approximation (SAA) for general stochastic optimization problems, including two-stage stochastic programming without the relatively complete recourse assumption. Instead of analyzing problems with spec
ific structures, we utilize results from the Vapnik-Chervonenkis (VC) dimension and Probably Approximately Correct learning to provide a general framework that offers explicit feasibility bounds for SAA solutions under minimal structural or distributional assumption. We show that, as long as the hypothesis class formed by the feasbible region has a finite VC dimension, the infeasibility of SAA solutions decreases exponentially with computable rates and explicitly identifiable accompanying constants. We demonstrate how our bounds apply more generally and competitively compared to existing results.
We show that disjointness requires randomized communication Omega(n^{1/(k+1)}/2^{2^k}) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound for k >= 3 was log(n)/(k-1). Our results give a separation between
nondeterministic and randomized multiparty number-on-the-forehead communication complexity for up to k=log log n - O(log log log n) many players. Also by a reduction of Beame, Pitassi, and Segerlind, these results imply subexponential lower bounds on the size of proofs needed to refute certain unsatisfiable CNFs in a broad class of proof systems, including tree-like Lovasz-Schrijver proofs.
We study the complexity of computing the projection of an arbitrary $d$-polytope along $k$ orthogonal vectors for various input and output forms. We show that if $d$ and $k$ are part of the input (i.e. not a constant) and we are interested in output-
sensitive algorithms, then in most forms the problem is equivalent to enumerating vertices of polytopes, except in two where it is NP-hard. In two other forms the problem is trivial. We also review the complexity of computing projections when the projection directions are in some sense non-degenerate. For full-dimensional polytopes containing origin in the interior, projection is an operation dual to intersecting the polytope with a suitable linear subspace and so the results in this paper can be dualized by interchanging vertices with facets and projection with intersection. To compare the complexity of projection and vertex enumeration, we define new complexity classes based on the complexity of Vertex Enumeration.
It is well known that any graph admits a crossing-free straight-line drawing in $mathbb{R}^3$ and that any planar graph admits the same even in $mathbb{R}^2$. For a graph $G$ and $d in {2,3}$, let $rho^1_d(G)$ denote the minimum number of lines in $m
athbb{R}^d$ that together can cover all edges of a drawing of $G$. For $d=2$, $G$ must be planar. We investigate the complexity of computing these parameters and obtain the following hardness and algorithmic results. - For $din{2,3}$, we prove that deciding whether $rho^1_d(G)le k$ for a given graph $G$ and integer $k$ is ${existsmathbb{R}}$-complete. - Since $mathrm{NP}subseteq{existsmathbb{R}}$, deciding $rho^1_d(G)le k$ is NP-hard for $din{2,3}$. On the positive side, we show that the problem is fixed-parameter tractable with respect to $k$. - Since ${existsmathbb{R}}subseteqmathrm{PSPACE}$, both $rho^1_2(G)$ and $rho^1_3(G)$ are computable in polynomial space. On the negative side, we show that drawings that are optimal with respect to $rho^1_2$ or $rho^1_3$ sometimes require irrational coordinates. - Let $rho^2_3(G)$ be the minimum number of planes in $mathbb{R}^3$ needed to cover a straight-line drawing of a graph $G$. We prove that deciding whether $rho^2_3(G)le k$ is NP-hard for any fixed $k ge 2$. Hence, the problem is not fixed-parameter tractable with respect to $k$ unless $mathrm{P}=mathrm{NP}$.
We prove three results on the dimension structure of complexity classes. 1. The Point-to-Set Principle, which has recently been used to prove several new theorems in fractal geometry, has resource-bounded instances. These instances characterize the
resource-bounded dimension of a set $X$ of languages in terms of the relativized resource-bounded dimensions of the individual elements of $X$, provided that the former resource bound is large enough to parameterize the latter. Thus for example, the dimension of a class $X$ of languages in EXP is characterized in terms of the relativized p-dimensions of the individual elements of $X$. 2. Every language that is $leq^P_m$-reducible to a p-selective set has p-dimension 0, and this fact holds relative to arbitrary oracles. Combined with a resource-bounded instance of the Point-to-Set Principle, this implies that if NP has positive dimension in EXP, then no quasipolynomial time selective language is $leq^P_m$-hard for NP. 3. If the set of all disjoint pairs of NP languages has dimension 1 in the set of all disjoint pairs of EXP languages, then NP has positive dimension in EXP.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
