Reference-request is used when the author needs to know about work related to the question.

learn more… | top users | synonyms

9
votes
1answer
101 views

First order satisfiability that doesn't have finite models

We know from Church's theorem that determining first order satisfiability is undecidable in general, but there are several techniques we can use to determine first order satisfiability. The most ...
7
votes
2answers
164 views

Implementation of surreal numbers for games

There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
9
votes
0answers
90 views

References for de-amortization

I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against ...
2
votes
0answers
99 views

Strong Dependence

I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and ...
5
votes
1answer
114 views

Ref question: K-nearest neighbours in a graph

Given an undirected graph $G$ with $n$ vertices, $m$ edges, and positive weights on the edges, I am interested in the problem of computing for each vertex the $k$ distinct vertices in $G$ that are ...
0
votes
0answers
140 views

Problems which are solvable using Linear Programming

Can anyone share a link to a good survey/book about the different problem types for which we have a linear programming based solution for, as well as the related techniques?
3
votes
0answers
123 views

Restricted-Input Automaton

In the classic setting, an automaton for a language $L$ is required to accept all words in $L$ and reject/get stuck on every word in $\Sigma^*\setminus L$. All of the related concepts are then ...
2
votes
0answers
76 views

efficient data structures for generalized tensor products

The usual tensor product of vectors is a matrix. There has been tons of research into efficiently storing and operating on matrices in computers. But we can generalize the tensor product quite a ...
16
votes
1answer
253 views

Lower bounds for the size of nondeterministic circuits

It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method. Recently, I noticed that the ...
-1
votes
2answers
79 views

Arrangements of Objects

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ ...
8
votes
1answer
360 views

Problem that is in P only if P!=NP

Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time? A simple example would be: If P!=NP, compute a primality test for a random ...
13
votes
1answer
480 views

The complexity of counting simple paths in a directed graph

Let $G$ be a digraph (not necessarily a DAG) and let $s,t \in V(G)$. What is the complexity of counting the number of simple $s-t$ paths in $G$. I would expect the problem to be #${\mathsf ...
7
votes
1answer
269 views
0
votes
0answers
129 views

proving speedup phenomenon does not apply to any open complexity class separations

Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question. the Blum speedup ...
1
vote
0answers
93 views

How to define deep learning? [closed]

Ive read some articles about deep learning but I found its hard to provide a clear definition of deep learning. For me its like an intelligent feature selection method. But it seems that its not ...
2
votes
0answers
66 views

Which paper to cite when referring to reservoir sampling *with replacement*?

As far as I can tell, the term "reservoir sampling" is commonly used to refer to sampling without replacement and references [1], [2], and [3] are cited while mentioning it. When referring to ...
7
votes
0answers
90 views

Computing the most likely winner in elections : intermediate case between Kemeny and Borda?

Given $n$ possible alternatives satisfying some unknown linear ordering, a multiset of pairwise votes, i.e., a matrix $M\in\mathbb{N}^{n\times n}$: $M_{i,j}$ counts the number of votes for which ...
5
votes
1answer
133 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
4
votes
0answers
87 views

extracting/ exploiting similarity of SAT instances by solver

suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas ...
6
votes
1answer
280 views

Describing state machines mathematically

The short paper "Computer Science and State Machines" by Leslie Lamport seems quite strange to me. On the one hand, I am surprised to see that an important hardware protocol called "two-phase ...
1
vote
0answers
136 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
4
votes
1answer
263 views

Hardness of UNAMBIGUOUS-3DM

Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution. Is there a ...
2
votes
1answer
101 views

Resource listing models with known VC dimension

Is there any reference resource gathering models with known VC dimension? I am looking for an exhaustive list of models with their VC dimension (and ideally the associated proof or a pointer to it). ...
13
votes
0answers
300 views

How can one find the “hard” probability distribution on the input for recursive boolean functions?

Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
3
votes
0answers
77 views

minimal languages that “cover” grammar productions

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically ...
0
votes
0answers
77 views

Graph database indexing

Graph databases are usually defined as index-free adjacency and that applies mostly to many current implementations - for example Neo4j - My question is: Is there are any references or papers with ...
6
votes
0answers
46 views

Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
19
votes
0answers
319 views

$RL=L$ Progress Since 2006

Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (http://dl.acm.org/citation.cfm?id=1132583) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are ...
7
votes
0answers
172 views

Gaussian elimination for inverting matrices modulo prime power

Can I use Gaussian elimination to compute matrix inverse over the ring $\mathbb{Z}_{p^k}$ (ring of residues modulo $p^k$) where $p$ is prime and $k$ is an integer greater than $1$? Such matrix is ...
4
votes
1answer
93 views

any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big ...
12
votes
1answer
641 views

A course for learning algebraic complexity

I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT. Is there a set of lecture notes, books, papers and surveys for students who have read standard ...
4
votes
1answer
207 views

What characterizations exist for the grammars that can express subsets of the context-free languages?

It is well known that CFGs and PDAs are equivalent, and there has been extensive research about the relationship between deterministic pushdowns and $LR(1)$ grammars, as $DCFL$ is a subset of $LR(1)$. ...
6
votes
2answers
118 views

Are deterministic context-free languages closed under outfix (or other erasing operations)

Define the outfix of a language $L$ to be $Outf(L) = \{xy \mid \exists z. xzy \in L \}$. Are any known results about whether deterministic context-free languages are closed under this operation, or ...
1
vote
0answers
68 views

Proof of convergence of alternative minimization/maximization [duplicate]

Given a problem \begin{equation} \max_{x\in X} \min_{y \in Y} f(x,y) \end{equation} where $f$ is strongly convex in $Y$ and strongly concave in $X$ How to show that the following iterative ...
0
votes
0answers
80 views

Regularlity lemma and exceptional set

Regularity lemma is one of the most basic tools in algorithmic thoery and pure math theory like additive number theory and combinatorics. This lemma is stated two ways: the existence of a partion ...
5
votes
0answers
100 views

Spectrum of absorbing random walk for regular graphs

I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as ...
3
votes
0answers
82 views

Probability distributions and computational complexity

Some probability distributions are easier to work with than others. Consider the following two problems. Given a number $n$, return $i$ with $0 \leq i < n$ with uniform probability, i.e. ...
6
votes
0answers
90 views

What is known about reduction by “$P_1$ interprets $P_2$” for generalized programming languages?

Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") ...
0
votes
0answers
38 views

Eioknal Equation solver with different grid densities

The Fast Marching Method, Fast Iterative Method, and Fast Sweeping Method are three ways of solving the Eikonal Equation on a discrete grid, essentially just a wavefront spreading out from initial ...
3
votes
2answers
155 views

Iteratively minimizing the function

Consider the problem \begin{equation} \min_{x\in X, y \in Y} f(x,y) \end{equation} Can I solve the problem by iteratively solving the following two sub problems? \begin{equation} x_{k+1} = ...
21
votes
1answer
548 views

A flowchart for concentration bounds

When I teach tail bounds, I use the usual progression: If your r.v is positive, you can apply Markov's inequality If you have independence and also bounded variance, you can apply Chebyshev's ...
11
votes
1answer
250 views

Identifying useless edges for shortest path

Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex ...
12
votes
2answers
1k views

Hamiltonian cycle on graphs without small cycles

While answering this question on cstheory, I (informally) proved on the fly the following theorem: Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if ...
6
votes
0answers
86 views

Hard extendability problems

In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other ...
5
votes
1answer
245 views

A good exposition of the random restriction method

I'm wondering if there are good references that describe the random restriction method as a lower bound technique ? I'm aware that it's linked to the switching lemma and shows up in many different ...
-1
votes
1answer
97 views

SAT formula specifying that exactly $k$ of $N$ boolean variables are active using less than $N$-choose-$k$ terms

Is there a way to express the condition that exactly $k$ of $N$ boolean variables are active without writing a disjunction of $N$-choose-$k$ terms, i.e., all possible configurations of the $N$ ...
1
vote
1answer
89 views

description of continuous probability distribution

The minimum description length of the realization of a random variable $x$ is given by the entropy of its probability mass function. Entropy of the representation of a (generic) probability ...
1
vote
0answers
109 views

Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
13
votes
1answer
286 views

Las Vegas vs Monte Carlo randomized decision tree complexity

Background: Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of ...
0
votes
1answer
47 views

How to define the _regret_ in multiagent systems? Any good definition please?

I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent ...