Tag Info

New answers tagged

6

I will present an equivalent but simpler-looking formulation of the problem, and show a lower bound of (n/k − 1) / (n−1). I also show a connection to an open problem in quantum information. [Edit in revision 3: In earlier revisions, I claimed that an exact characterization of the cases in which the lower bound shown below is attained is likely to be ...


3

The classical theory of fault tolerance was pioneered by John von Neumann. I think this is the original reference: von Neumann, J. (1956). "Probabilistic Logics and Synthesis of Reliable Organisms from Unreliable Components", in Automata Studies, eds. C. Shannon and J. McCarthy, Princeton University Press, pp. 43–98


5

The quick and dirty answer to the question is "no, the variance can be smaller": Let $v_1, v_2, \ldots, v_k$ be the standard basis, and consider the following random process: pick a pair of distinct integers i,j from $\{1,2,\ldots,k+1\}$, and set $x_i = x_j = v_1$. For the other vectors $x_t$ (for $t \notin \{i,j\}$) assign them to $v_2, \ldots, v_k$ in a ...


3

Here is a recent one: http://link.springer.com/chapter/10.1007%2F978-3-319-09284-3_17 You can get the fulltext here: http://arxiv.org/abs/1402.2184 It uses some state-of-the-art SAT solvers (see http://fmv.jku.at/lingeling/) to solve a member of a family of problems called "Erdős Discrepancy Conjecture". They encoded the problem as SAT instances and the SAT ...


1

From the abstract of: Dobrynin, Andrey A., Roger Entringer, and Ivan Gutman. "Wiener index of trees: theory and applications." Acta Applicandae Mathematica 66, no. 3 (2001): 211-249 The Wiener index W is the sum of distances between all pairs of vertices of a (connected) graph. The paper outlines the results known for W of trees: methods for computation ...


2

On the same page there was a section: relation to chemical properties (http://en.wikipedia.org/wiki/Wiener_index#Relation_to_chemical_properties) Maybe references in that section mentions more about how this index can be used for graphs. Seems like you can estimate the overall structure of the graph if it is dense (low index) or sparse. Because the lengths ...


3

Answering the other half of the question - here is a proof sketch for a $c \cdot \log n$ lower bound for the treewidth for some constant $c$. The bound is independent of the size or any other aspect of the circuit. In the rest of the argument $C$ is the circuit, $t$ is the treewidth of $C$ and $n$ is the number of input gates. The first step is to use the ...


5

Answering half of Samir's question. Let $G=(V,E)$ be a DAG and $V_1,V_2\subseteq V$ be two subsets of vertices of $G$. We denote by $E(V_1,V_2)$ the set of all edges in $G$ with one endpoint in $V_1$ and other endpoint in $V_2$. If $\omega = (v_1,...,v_n)$ is a total ordering of the vertices of $G$ then we let $$\mathbf{ow}(G,\omega) = \max_{i}\; ...


2

There's something on the multiplicatively weighted farthest neighbor query problem (but not on the associated Voronoi diagram) in my paper Approximate weighted farthest neighbors and minimum dilation stars. J. Augustine, D. Eppstein, and K. Wortman. arXiv:cs.CG/0602029. Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010), ...


4

Since your question is: "What is known?" Here's something: http://arxiv.org/abs/1307.3033 This gives an average case analysis of the Ford-Johnson Algorithm. The expected number of comparisons is $\log n! +cn$ for a surprisingly small constant $c$ (about .05).


1

As one of the topics of your lecture, the problems from combinatorics might be good candidates.Generally, a high school student has some conception on permutation, combination and high school geometry. So, following examples illustrates what i mean. Take arbitary points on plane. Can we always find a line such that the number of points above and below the ...


9

Here's an amusing approach by Brock-Nannestad and Schürmann: Truthful Monadic Abstractions The idea is to try to translate first-order sentences into monadic first-order logic, by "forgetting" some of the arguments. Certainly the translation isn't complete: there are some consistent sentences which become inconsistent after translation. However, monadic ...


0

on some search there do not seem to be much published general implementations of surreal numbers. heres an implementation of surreal numbers in coq. Surreal numbers in coq / Mamane, TYPES'04 Proceedings of the 2004 international conference on Types for Proofs and Programs Surreal Numbers form a totally ordered (commutative) Field, containing copies of ...


4

I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an open-source program to aid research in combinatorial game theory" (which I first learned about here). It includes an implementation of various standard ...


0

In the same spirit of Sanjeev Arora's notes that @umar posted, I like Madhur Tulsiani's lecture notes and exercises for his "Mathematical Toolkit" class posted at the course webpage. In addition to Arora's excellent material his notes have a nice coverage of spectral graph theory as well as the multiplicative weights update method.


2

In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe a new storage schema with a set of indexed structures to support an efficient execution of a slightly modified version of the Dijkstra's algorithm. In the ...



Top 50 recent answers are included