New answers tagged reference-request
1
Here is a link, may be it can help you. http://fc.isima.fr/~nourine/publications.php
M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.
1
a3nm's answer shows that the problem is hard on 3-regular multigraphs. In this post I show that it is also hard on bipartite graphs (in fact, $2$-$3$--regular bipartite simple graphs), which is what I needed.
I reduce from the problem on $3$-regular multigraphs. Let $G=(V,E)$ be a $3$-regular multigraph. Construct $G'$ by adding a node in the middle of ...
3
This is a late response.
First, to correct what you wrote:
Cryptographic pseudorandomness (the one obtained from OWFs) doesn't have enough stretch to derandomize "naturally defined" computational complexity classes. In an old paper (beginning of 80s) Andrew Yao shows some subexponential time derandomization for RP etc using these objects (btw, this is ...
10
Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily.
First, let's notice that for $b_n=a_{2^n}$, we have the recurrence
$$b_n = 3b_{n-1}^2 - 2b_{n-2}^4.$$
Now, let's assume that $b_n = r s^{2^n}$. The equation ...
7
Here is a rather sloppy proof sketch. Let $S = \sum_{i=1}^n \delta_i \sqrt{a_i}$ where $\delta_i \in \{\pm 1\}$. This is an algebraic number of degree at most $2^n$ and height at most $H = (max(a_i))^{n}$. Now it is easy to check if $S = 0$ (can be done even in $TC^0$ -- see this).If $S \neq 0$ then it is bounded away from $0$ by a quantity (because it is an ...
4
Here are some additional notes: lecture notes by Dieter van Melkebeek , notes from Luca Trevisan's course on expanders.
8
You can look at this survey by Hoory, Linial, and Wigderson [1]. Chapter 9, specifically (p. 508) is on the zigzag product.
9.The zig-zag product
9.1. Introduction
9.2. Construction of an expander family using zig-zag
9.3. Definition and analysis of the zig-zag product
9.4. Entropy analysis
9.5. An application to complexity theory: SL=L
...
1
"We use a suitable Gödel numbering of descriptions of context-sensitive grammars. For example, a context-sensitive grammar may be represented by a string of characters in some accepted formalism. Obviously, such a string is represented by a finite sequence of bits in computer memory, which is the Gödel code in question."
This will do in a research paper (we'...
Top 50 recent answers are included
