# All Questions

12,801 questions
Filter by
Sorted by
Tagged with
471 views

### multi-party Communication complexity of "Set Partition problem"

In an application I'm considering, I need to know the communication complexity of the following problem: Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each ...
• 763
890 views

### Heuristics for the minimum-weight $k$-clique problem

Hello Does someone have an idea for heuristics for the problem: Given undirected weighted(weights on edges) complete graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of ...
• 189
10k views

### How to get a job

I'm new to the site. On mathoverflow this would be community wiki, but I don't see how to set that here. Not a research question, but hopefully of interest to professional theoretical computer ...
5k views

### Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?

There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's ...
• 1,520
459 views

### Bit complexity of integer factorization?

Integer Factorization problem: Given integers $N, M$, find an integer $d< M < N$ that divides $N$. Is it easier to find the value of a single bit? This problem is at least as hard as integer ...
401 views

### Efficiently getting bits of N! ?

Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$? i.e....
• 2,796
552 views

### Analysis of the synergy of two algorithms in comparison to their simulation in parallel

Consider the following two algorithms for searching in a sorted array of $n$ elements: A) interpolation search and binary search simulated in parallel, and B) search through alternating ...
• 2,766
392 views

### Semantic distance between excerpts of text.

I'm wondering how far along the natural language processing is in determining the semantic distance between two excerpts of text. For instance, consider the following phrases Early this morning I ...
3k views

### Sorting algorithm with a complexity smaller than $n \log n$?

If we consider literature, sorting algorithms are based only on number of comparisons needed to sort a list of size n, considering that n is the size of the input. But if we want to encode input, we ...
• 1,743
225 views

### Solution Clusters and Monotone-2SAT

It is known that generic k-SAT formulas may exhibit the presence of exponentially many solution clusters. Question: Is it true also for Monotone-2SAT formulas? For the definition of cluster, see ...
• 6,842
2k views

### Pruning a strongly connected digraph

Given a strongly connected digraph G with weighted edges, I would like to identify edges that are provably not part of any minimal strongly connected subgraph (MSCS) of G. One method for finding such ...
• 285
469 views

### Tool for translating PDAs to CFGs

We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
• 385
649 views

### Chernoff-type inequality for random variable with 3 outcomes

Suppose we have a random variable which takes non-numeric values a,b,c and want to quantify how empirical distribution of $n$ samples of this variable deviates from true distribution. The following ...
• 4,701
442 views

### Agnostic learning over arbitrary distributions

Let $D$ be a distribution over bitstring/label pairs $\{0,1\}^d\times \{0,1\}$ and let $C$ be a collection of boolean valued functions $f:\{0,1\}^d\rightarrow\{0,1\}$. For each function $f \in C$, let:...
• 9,850
2k views

### How many instances of 3-SAT are satisfiable?

Consider the 3-SAT problem on n variables. The number of possible distinct clauses is: $$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$$ The number of problem instances is the ...
500 views

### Are there families of formal languages known to be truly PAC learnable?

I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n. I am asking about "...
• 10.5k
1k views

### Interdisciplinary topics between control theory and theoretical computer science

I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, ...
• 251
574 views

### Creating HMAC keys using a fixed prefix and a random string

In a system that uses HMAC for a number of different applications, it is important to use different keys for different applications. Suppose: there is just a single random string available (50 bytes ...
• 173
556 views

### 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 ...
• 2,482
233 views

### Statistical tests between L and LogCFL

Statistical tests are used to check whether a source of randomness is "good". Blum and Goldreich (1992) mentioned two types of statistical tests : (1) deterministic polynomial time statistical tests ...
• 10.6k
2k views

### Consequences of existence of a strongly polynomial algorithm for linear programming?

One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and ...
• 2,727
783 views

### Intermediate/Coding representation for Levenshtein Distance

The phrases: The quick brown fox jumps over the lazy dog [A] and The uick brown fox jumps oower the lazy dog [B] can be compared using Levenshtein Distance algorithm to determine similarity ...
• 179
569 views

### UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?

Background: In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary ...
• 6,001
1k views

### Alternate proofs of Immerman-Szelepcsenyi theorem

Immerman and Szelepcsenyi independently proved that $NL=coNL$. Using their technique of inductive counting, Borodin et al proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to ...
• 10.6k
477 views

### Compactly representing the solution set of a SAT instance

This question has risen in my mind after reading András Salamon's and Colin McQuillan's contributions to my previous question Counting solutions of Monotone-2CNF formulas. EDIT 30th Mar 2011 Added ...
• 6,842
3k views

On MathOverflow, Timothy Gowers asked a question titled "Demonstrating that rigour is important". Most of the discussion there was about cases showing the importance of proof, which people on ...
202 views

### Has ping based failure detector 'strong completeness' and 'weak accuracy'?

I was reading 'Unreliable Failure Detectors for Reliable Distributed Systems' (PDF) and I was wondering if ping (with increasing timeouts in case of failure) is in class S of failure detectors: ...
• 696
1k views

### Is #P contained in PSPACE?

It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE? It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and ...
• 1,089
8k views

### Split or merge Binary Search Trees in O(log n)

We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following. The element with the largest value in $S_1$ is smaller than the ...
2k views

### Diameter of a graph with O(|V|) edges

What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?
• 696
883 views

### Non-rooted MST of directed graph

I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the ...
• 285
1k views

### Finding short and fat paths

Motivation: In standard augmenting path maxflow algorithms, the inner loop requires finding paths from source to sink in a directed, weighted graph. Theoretically, it is well-known that in order for ...
• 681
548 views

### VC-dimension of Cylinders within a Cylinder

I wish to know the VC-dimension of a range space $(X,\mathcal{R})$ constructed as follows: $X$ is the cylinder $\{(x,y,z)\in\mathbb{R}^3|x^2+y^2\leq 1\}$ The ranges in $\mathcal{R}$ are formed by ...
1k views

### Where's the Flaw in Blum-Feldman-Micali's Method

Blum, Micali, and Feldman (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some ...
• 16.5k
4k views

### What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

Background The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
• 21.6k
1k views

### Counting solutions of Monotone-2CNF formulas

A Monotone-2CNF formula is a CNF formula where each clause is composed by exactly 2 positive literals. Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I ...
• 6,842
490 views

### Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

minimize/maximize $\displaystyle \sum_{i=0}^{f(n)} G(x,n)$ s.t. $n \ge 1$ and $x$ in some feasible region The decision variables are $x$ (a vector) and $n$ (a scalar). How is this type of ...
• 51
659 views

### Approximating non-trivial graph automorphism?

Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set $E$. Formally, It is a permutation $f$ of nodes such $(u,v)\in E$ iff $(f(u),f(v))\in E$ Define an ...
1k views

### Techniques for proving bounds on integrality gap in LP(SDP)

A reference to techniques for proving that the size of an integrality gap is bounded by some expression for a particular LP(or SDP, but less important) is needed. Also it would be nice to have a ...
• 1,468
3k views

Let $C$ be a CCC. Let $(\times)$ be a product bifunctor on $C$. As Cat is CCC, we can curry $(\times)$: $curry (\times) : C \rightarrow(C \Rightarrow C)$ $curry (\times) A = \lambda B. A \times B$ ...
• 557
315 views

### Algebraic data type - rewrite system

Let's define the integer ADT. It has, as generators, the constant 0 (a generator) and the succ operation. Moreover, it also contains the add operation defined by the (usual) axioms add (0, x) = x (...
285 views

### Why may the right hand sides in Chomsky Hierachy type 1 be larger?

I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|. Why? I would have said, ...
3k views

### Proving the set of powers of 2 over ternary alphabet to be non regular.

It's simple to see that the powers of 2 over alphabet {0,1} is regular because $10^*$ is a regular expression for it. But the powers of 2 represented in ternary appears to be non regular. Pumping ...
14k views

### How to check if a number is a perfect power in polynomial time

The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in ...
• 428
659 views

### Bounded-input bijections of infinite sequences

Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution. It is possible to define a bijection $3^\mathbb{N} \cong 5^\mathbb{N}$ ...
• 3,546
4k views

### Physics results in TCS?

It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are Quantum computation ...
• 13.6k
533 views

### Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?

Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S. Instance: A permutation p in P. Question: Does there exist a graph g in ...
4k views

### Difference between NP-Hard and NP-Complete [closed]

Can someone please summarize the exact difference between NP-Complete and NP-Hard problems in simple language? Wiki and my standard books aren't exactly helping.
2k views

### How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...