0
votes
0answers
3 views
Justifying simplifying assumption about message distributions for perfectly secret encryption?
I am currently reviewing my way through Katz and Lindell's Intro to Modern Cryptography, and have found the following question early in the book (exercise 2.6) surprisingly difficult to answer ...
-1
votes
0answers
28 views
Is a PDA as powerful as a CPU? [migrated]
Yes this is a question I have stumbled upon in my exam revision and it is intriguing.
Question : My computer is blue and it has a massive graphics card and a DVD and every-
thing so which is more ...
2
votes
0answers
36 views
Avarage Monotone Circiut Lower Bounds
I have some questions on Ben Rossman's papaer "The Monotone Complexity of k-clique" at FOCS10
(1)Definition of $P$-minterm
His definition is as follows:
For a pattern $P$ ( which is a constant size ...
2
votes
2answers
76 views
Algorithm Design for only Mutual Information Sharing
Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their ...
1
vote
1answer
74 views
Boolean Circuit in a Black Box?
Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here.
Let's equip a normal Turing machine with a "black box ...
1
vote
0answers
85 views
Minimal context-free Grammar for a special one-letter Language
For natural numbers $n \geq 5$, $m \geq 2^{n-2} + 1$ the following context-free language is given:
$$
L_{n,m} = \{ a^i | 2 \leq i \leq m \} \setminus \{a^{2^i}|2 \leq i \leq n-2\}
$$
Find and ...
5
votes
0answers
74 views
Cover time and spectral gap for reversible random walks
I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, ...
11
votes
0answers
201 views
Are theoretically sound pseudorandom generators used in practice?
As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they ...
-7
votes
0answers
106 views
Can lightning be used to solve NP-complete problems [closed]
[Originally posted on StackOverflow and now reposted on Physics SE]
Lightning seems to follow the "easiest" path to a given destination, as opposed to just the shortest path. This seems analogous ...
-1
votes
0answers
48 views
Can anyone explain Nilsson's sequence score in 8-puzzle more clearly?
I am learning A* algorithm on 8-puzzle problem.
I don't have questions about A*, but have some for the heuristic score - Nilsson's sequence score.
Justin Heyes-Jones web pages - A* Algorithm ...
6
votes
2answers
200 views
A variation on discrepancy involving random graphs
Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is ...
4
votes
1answer
106 views
Complexity of optimization over unitary group
What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$?
A typical task, arising often in quantum information theory, would be maximizing a ...
-1
votes
0answers
178 views
$NP^C \neq coNP^C$. How to find $C$?
How to prove that $NP^C \neq coNP^C$ ? I am just looking for a such oracle TM $M$ and a recursive language $L(M) = L$ for which this holds. I know the proof where you show that there is an oracle $A$ ...
-4
votes
0answers
33 views
Mixed-strategy Nash equilibria
I didn't find in books, so I'm asking - Mixed-strategy Nash equilibria is always only one or doesn't exist for the one certain game? And I know that there can be several(and can not be at all) pure ...
-1
votes
0answers
19 views
Are there problems in NP that aren't NP Complete? [migrated]
Are there any known problems in NP that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.
If ...
-7
votes
0answers
91 views
what is the TM time/space complexity of the ackermann function?
recently asked another broad question[1] that was imho misunderstood & am working on restating it in a airtight way [plz revisit that Q if this one makes sense & then makes sense in retrospect ...
-3
votes
0answers
91 views
Sorting a queue with another queue [closed]
ow can I sort a queue of size N, using just another queue of size N, and a finite number of variables?
the naïve implementation - finding the minimum of the queue and pushing it to the empty queue, ...
-1
votes
0answers
80 views
A probabilistic method [closed]
I am trying to study for a exam and i found a assignmet, that i cant solve.
Consider a board of $n$ x $n$ cells, where $n = 2k, k≥2$. Each of the numbers from $S = \{1,...,\frac{n^2}{2}\}$ is written ...
-1
votes
0answers
61 views
Bit fixing on hypercubes [closed]
2 weeks ago we discussed bit fixing on hypercubes in class. Then it was clear for me, but now i have problems to understand it.
We had an assignment:
We look at a particular packet $p$ while ...
-1
votes
0answers
94 views
Why Viola Jones is the most used/most popular object detection algorithm? [closed]
Possible Duplicate:
Viola Jones algorithm information/descriprion
I know that this algorithm is very robust. But why it is most used? Why another methods arent' used almost? I know other ...
1
vote
1answer
95 views
Discerning the best model for a problem
This is a vague question. I will do my best, I think it has definite answers. I am hoping for answers of the form "Read book x, learn this specific topic, read this paper/s".
What is bothering me is ...
0
votes
1answer
91 views
Advantages of ANN classifiers over the AdaBoost
So what are the advantages of ANN classifiers over the AdaBoost or Boosting algorithm?
-3
votes
0answers
75 views
Regular expression for all strings with at least two 0s over alphabet {0,1} [closed]
My answer :
(0+1)* 0 (0+1)* 0 (0+1)*
Why is this incorrect? Can somebody explain to me what the correct answer is and why?
0
votes
0answers
142 views
CS complexity of famous complex (“fast-growing”) mathematical functions [closed]
there is a branch of mathematics that has developed roughly in parallel with CS complexity theory that studies "complex" in the sense of "hard-to-compute" functions (because of the property of ...
6
votes
1answer
152 views
Techniques for proving NP completeness for a specific sequence of instances
Most NP-completeness proofs I have seen pertain to proving that a problem on a class of instances is NP-complete. E.g., satisfiability is NP-complete on the class of instances with clauses having ...
15
votes
2answers
310 views
Problem in BPP but not known to be in RP or co-RP
Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
-1
votes
0answers
32 views
I want to classify accelerometry data. What method should I use?
I have sets of accelerometer data collected over a couple of minutes. Each set has about 300 (x, y, z) tuples, which when plotted looks like this(1) or this(2). I want to classify each of the sets as ...
17
votes
1answer
268 views
What is $\mathsf{NP}$ restricted to linear size witnesses?
This is related to the question Is the Witness Size of Membership for Every NP Language Already Known?
Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying ...
1
vote
0answers
109 views
How much variation is allowed before an algorithm is no longer a quicksort? [closed]
Possible Duplicate:
When are two algorithms said to be “similar”?
Generic Overview of promblem:
I read somewhere once that a quicksort could be done without recursion in O(1) ...
-3
votes
0answers
39 views
Search & replace a constant string with a variable one inside a file [closed]
I asked this question on a different forum, but got no answers. Hope to get answer from this section.
I have hundreds of HTML documents named as 001.html 002.html 003.html and so on.
All of these ...
12
votes
1answer
351 views
How hard is Mafia?
Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.
Basically, it works as follows:
At the beginning, ...
0
votes
0answers
14 views
Explain $\log_2\ n$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort [migrated]
Reading from Page 1, the section titled CREW Mergesort in:
http://www.inf.ed.ac.uk/teaching/courses/dapa/note3.pdf
it is stated in the final paragraph of the section:
"Each such step (in a ...
8
votes
1answer
299 views
+50
Büchi automata with acceptance strategy
The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense ...
-2
votes
0answers
37 views
Dijsktra's algorithm applied to travelling salesman problem [migrated]
I am a novice(total newbie to computational complexity theory) and I have a question.
Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it?
...
4
votes
1answer
122 views
Shortest paths when randomly scrambling a Rubik's cube
I saw a previous question about local maxima for the number of moves in a Rubik's cube solution, and I wondered what is known about the distribution of shortest paths when randomly scrambling a ...
1
vote
0answers
28 views
How do I classify my emulator input optimization problem, and with which algorithm should I approach it? [migrated]
Before I start: I understand the scope of this StackExchange site (I think), but do pardon if I'm off-topic. My question is an intersection of mathematics, computer science, and software engineering, ...
5
votes
1answer
123 views
Scrambling a Rubik's cube by an adversarial noob
My friend dislikes Rubik's cubes, and he asked me how to frustrate amateur solvers by adversarially scrambling the cube. I expect that the answer depends highly on the particular solving algorithm.
...
-3
votes
0answers
81 views
Can anyone explain the algorithm this program used to generate primes? [closed]
The PG7.8 python program
I stared at the script for an hour but still have no idea how it works.
Thanks!
3
votes
0answers
62 views
Term rewriting for proving inequalities
Suppose $f$ is a submodular set function on a universe $U$ of size $n$.
For $k \in \{0,\ldots,n\}$, let
$$ F(k) = \operatorname*{\mathbb{E}}_{X \in \binom{U}{k}} f(X), $$
where $\binom{U}{k}$ is the ...
4
votes
1answer
118 views
What are the limitations on formal proofs of Erlang systems?
Well, today I just got my 15 minutes of fame, but now I think I am wrong on the point about formal proofs on Erlang systems. The discussion on news.ycombinator.com suggests that Erlang code may or ...
-1
votes
0answers
42 views
Turmite variation
Are there any variations on turmites (think of Langton's Ant) in which there are multiples turmites/ants on the same grid/board and they influence each other when they meet (like passing information, ...
-1
votes
0answers
69 views
t If an artificial neural network can simulate a biological neural network, can a large enough ANN simulate a human mind? [closed]
If the human mind is just the activity of a bunch of neurons (many billion), would it be theoretically possible to create a mind, with the capacity for emotions and thought, with a large enough ...
4
votes
3answers
117 views
Are there websites for TCS announcements that maintain mailing-lists or web feeds?
For a while, I have been wondering if there exists some site where you can subscribe to receive TCS-conference announcements via e-mail, or, alternatively, that offers some periodically-updated ...
7
votes
0answers
54 views
Can one find good distance-2-separators in planar graphs?
It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.
However, it seems that ...
10
votes
2answers
256 views
Regular languages from category-theoretical point of view
I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a ...
4
votes
2answers
109 views
Selection in a genetic algorithm
I have a working genetic algorithm which uses a few genetic operators on pairs of individuals.
These two individuals are selected by fitness-proportional (roulette-wheel) selection, that is, an ...
6
votes
1answer
97 views
Non-uniform hierarchy theorem for approximating functions
It is easy to show (by probabilistic argument) that there exist functions that require circuits of size $O(2^n/n)$. This, in turn, can be used to prove a non-deterministic hierarchy theorem showing ...
-2
votes
0answers
71 views
Diskret Fourier Transformation [closed]
The diskret fourier transformation is defined as:
$$\sum_{n=0}^{N-1}s(n)e^{-j\frac{2\pi}{N}kn}\quad k=0,...,N-1$$
proofe that for real signals s(n) is:
$$S(l)=S(N-l)^*$$
and S(N-l)^* is the conjugted ...
18
votes
1answer
295 views
Generating a tower defense maze, aka Finding the K most vital nodes (“nodewise interdiction”) in an unweighted grid-graph
In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.
Enemies take the shortest path from start to finish without passing through any walls (they aren't ...
1
vote
0answers
26 views
Uni-directional synchronization and locking issues
Suppose there are 2 databases, 1 and 2. Let's further assume 1 is always up and 2 can be down sometimes. (When it goes up again, it has to restart.)
1 is filled by say a dozen other systems with ...
