# Tag Info

## New answers tagged reference-request

-3

an example & proof is given in Introduction to Automata Theory, Languages, and Computation Hopcroft/ Ullman Thm13.16 that any nondeterministic algorithm for the first-order theory of reals with addition is NExpTime-hard. therefore it is presumably also NExpSpace-hard unless some theoretical breakthrough proves it can be solved "in tighter space" but of ...

6

Extending the example pointed out by Emil Jerabek in the comments, $\mathsf{EXPSPACE}$-complete problems arise naturally all over algebraic geometry. This started (I think) with the Ideal Membership Problem (Mayr–Meyer and Mayr) and hence the computation of Gröbner bases. This was then extended to the computation of syzygies (Bayer and Stillman). ...

7

Many problems that are PSPACE-complete become EXPSPACE-complete when the input is given "succinctly", i.e., via some encoding that lets you describe inputs that would normally be of exponential size. Here is an example on finite automata (equivalently, on directed graphs with labeled edges): deciding whether two automata accept the same language (have the ...

1

The book Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume published this summer (July 2014) largely agrees with the consensus that we reached here. On page 199, it says: To the best of my knowledge, it is even not known whether [the problem of computing tensor rank] over $\mathbb{Q}$ is decidable. Over $\mathbb{R}$, the ...

8

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 ...

1

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.

Top 50 recent answers are included