Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA common variable minimax theorem for graphs
121
0
0.0
(
0
)
Added by
Nicholas Marshall
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $mathcal{G} = {G_1 = (V, E_1), dots, G_m = (V, E_m)}$ be a collection of $m$ graphs defined on a common set of vertices $V$ but with different edge sets $E_1, dots, E_m$. Informally, a function $f :V rightarrow mathbb{R}$ is smooth with respect to $G_k = (V,E_k)$ if $f(u) sim f(v)$ whenever $(u, v) in E_k$. We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in $mathcal{G}$, simultaneously, and how to find it if it exists.
rate research
Read More
We show that the spectral flow of a one-parameter family of Schrodinger operators on a metric graph is equal to the Maslov index of a path of Lagrangian subspaces describing the vertex conditions. In addition, we derive an Hadamard-type formula for the derivatives of the eigenvalue curves via the Maslov crossing form.
A limit theorem for a sequence of diffusion processes on graphs is proved in a case when vary both parameters of the processes (the drift and diffusion coefficients on every edge and the asymmetry coefficients in every vertex), and configuration of graphs, where the processes are set on. The explicit formulae for the parameters of asymmetry for the vertices of the limiting graph are given in the case, when, in the pre-limiting graphs, some groups of vertices form knots contracting into a points.
The celebrated minimax principle of Yao (1977) says that for any Boolean-valued function $f$ with finite domain, there is a distribution $mu$ over the domain of $f$ such that computing $f$ to error $epsilon$ against inputs from $mu$ is just as hard as computing $f$ to error $epsilon$ on worst-case inputs. Notably, however, the distribution $mu$ depends on the target error level $epsilon$: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels. In this work, we introduce a new type of minimax theorem which can provide a hard distribution $mu$ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzos hardcore lemma. Our proofs rely on two innovations over the classical approach of using Von Neumanns minimax theorem or linear programming duality. First, we use Sions minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms. Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as forecasting algorithms evaluated by a proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties: for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required.
Given a graph with a designated set of boundary vertices, we define a new notion of a Neumann Laplace operator on a graph using a reflection principle. We show that the first eigenvalue of this Neumann graph Laplacian satisfies a Cheeger inequality.
Given $n times n$ real symmetric matrices $A_1, dots, A_m$, the following {it spectral minimax} property holds: $$min_{X in mathbf{Delta}_n} max_{y in S_m} sum_{i=1}^m y_iA_i bullet X=max_{y in S_m} min_{X in mathbf{Delta}_n} sum_{i=1}^m y_iA_i bullet X,$$ where $S_m$ is the simplex and $mathbf{Delta}_n$ the spectraplex. For diagonal $A_i$s this reduces to the classic minimax.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
