Most Popular
1500 questions
17
votes
1 answer
Computing parity of a permutation in a streaming-fashion way
I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of the permutation. The question I'm interested in…
Vsevolod Oparin
- 511
- 2
- 7
17
votes
2 answers
Minimal cumulative set sum
Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$.
Are there known algorithms for this? What is its complexity? I haven't been…
Antimony
- 917
- 5
- 15
17
votes
0 answers
Practically Good Algorithms of a Very Low Computational Complexity Class
I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties:
1) Solving the problems in $\cal A$ exactly or even approximately…
Gil Kalai
- 6,033
- 35
- 73
17
votes
0 answers
What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?
Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows.
Is there a result comparable to the Karp-Lipton theorem starting from the assumption…
Damiano Mazza
- 5,473
- 1
- 25
- 36
17
votes
2 answers
Complexity of the coset intersection problem
Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold?
As far as I know, the problem is known as the coset intersection problem. I am wondering what's the complexity? In particular, is…
maomao
- 1,345
- 6
- 17
17
votes
1 answer
Meaning of P=NP? depends on space-time geometry ?
This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008.
http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125
In the author's opinion, the…
Roy Maclean
- 273
- 1
- 7
17
votes
1 answer
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 P}$-complete but have not been able to locate an exact…
SamiD
- 2,309
- 17
- 28
17
votes
1 answer
Oracular separations between poly- and log-depth quantum circuits
The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory.
Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of any quantum algorithm be compressed to…
Juan Bermejo Vega
- 1,405
- 1
- 14
- 30
17
votes
1 answer
Complexity of hex with random turn order.
I've been thinking of a variant of hex, where instead of the two players making moves alternately, each turn a player picked at random makes a move. How hard is it to determine the chances for each player winning? This problem is obviously in…
Itai Bar-Natan
- 537
- 2
- 5
17
votes
5 answers
Open or Interactive Constraint Satisfaction
In the past, I implemented coordination models using SAT and regular constraint satisfaction as the core workhorse in their engines. Continuing in this line of work, I would like to make the models more interactive, and the best way I see of doing…
Dave Clarke
- 16,666
- 3
- 60
- 106
17
votes
3 answers
Formal representation of rings in computations
While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not familiar with computations of algebraic objects, is…
Hsien-Chih Chang 張顯之
- 7,638
- 4
- 44
- 83
17
votes
3 answers
Randomize or Not?
This question is inspired by the Georgia Tech Algorithms and Randomness Center's t-shirt, which asks "Randomize or not?!"
There are many examples where randomizing helps, especially when operating in adversarial environments. There are also some…
Lev Reyzin
- 11,968
- 13
- 63
- 103
17
votes
2 answers
Does this game terminate?
Consider the following card game (known in Italy as "Cavacamicia," which may be translated as "stripshirt"):
Two players randomly split in two decks a standard deck of cards. Each player gets one deck.
The players alternate placing down in a stack…
Manu
- 7,659
- 3
- 37
- 42
17
votes
2 answers
Comparing Two Algorithms for 3SUM problem over Integers
The paper "Subquadratic Algorithms for 3SUM", by Ilya Baran, Erik D. Demaine, Mihai Patrascu has the following complexity for the
3SUM problem: given a list $L$ of $n$ integers if there are $x,y,z \in L$ such that $x+y=z.$
They state, "On a…
kodlu
- 2,070
- 13
- 23
17
votes
1 answer
Fooling arbitrary symmetric functions
A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every function in that class.
It is known that…
Ramprasad
- 2,482
- 18
- 18