All Questions

Filter by
Sorted by
Tagged with
14 votes
2 answers
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 ...
Danu's user avatar
  • 763
2 votes
1 answer
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 ...
YAKOVM's user avatar
  • 189
60 votes
6 answers
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 ...
13 votes
2 answers
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 ...
Magnus Lie Hetland's user avatar
5 votes
2 answers
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 ...
Mohammad Al-Turkistany's user avatar
11 votes
2 answers
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....
user834's user avatar
  • 2,796
8 votes
1 answer
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 ...
J..y B..y's user avatar
  • 2,766
4 votes
3 answers
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 ...
John Berryman's user avatar
6 votes
5 answers
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 ...
Ludovic Patey's user avatar
3 votes
1 answer
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 ...
Giorgio Camerani's user avatar
10 votes
1 answer
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 ...
Nate's user avatar
  • 285
8 votes
1 answer
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 ...
Xodarap's user avatar
  • 385
9 votes
2 answers
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 ...
Yaroslav Bulatov's user avatar
11 votes
1 answer
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:...
Aaron Roth's user avatar
  • 9,850
31 votes
3 answers
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 ...
Antonio Valerio Miceli-Barone's user avatar
9 votes
2 answers
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 "...
Aryeh's user avatar
  • 10.5k
12 votes
8 answers
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, ...
hyperboreean's user avatar
7 votes
3 answers
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 ...
spookylukey's user avatar
17 votes
1 answer
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 ...
Ramprasad's user avatar
  • 2,482
10 votes
0 answers
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 ...
Shiva Kintali's user avatar
32 votes
3 answers
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 ...
Ian's user avatar
  • 2,727
8 votes
4 answers
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 ...
Jason Kleban's user avatar
16 votes
3 answers
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 ...
Daniel Apon's user avatar
  • 6,001
22 votes
1 answer
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 ...
Shiva Kintali's user avatar
10 votes
2 answers
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 ...
Giorgio Camerani's user avatar
44 votes
8 answers
3k views

Rigour leading to insight

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 ...
András Salamon's user avatar
4 votes
1 answer
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: ...
Alexandru's user avatar
  • 696
7 votes
1 answer
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 ...
Evgenij Thorstensen's user avatar
7 votes
3 answers
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 ...
Dimitris Leventeas's user avatar
4 votes
2 answers
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?
Alexandru's user avatar
  • 696
7 votes
3 answers
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 ...
Nate's user avatar
  • 285
10 votes
1 answer
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 ...
dan_x's user avatar
  • 681
8 votes
1 answer
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 ...
Josephine Moeller's user avatar
17 votes
1 answer
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 ...
Sadeq Dousti's user avatar
  • 16.5k
43 votes
3 answers
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 ...
Kaveh's user avatar
  • 21.6k
14 votes
2 answers
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 ...
Giorgio Camerani's user avatar
5 votes
3 answers
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 ...
user1725's user avatar
10 votes
2 answers
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 ...
Mohammad Al-Turkistany's user avatar
9 votes
2 answers
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 ...
Grigory Yaroslavtsev's user avatar
19 votes
3 answers
3k views

Reader, Writer monads

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$ ...
beroal's user avatar
  • 557
6 votes
2 answers
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 (...
user avatar
5 votes
2 answers
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, ...
user avatar
9 votes
4 answers
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 ...
user avatar
24 votes
4 answers
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 ...
yzll's user avatar
  • 428
28 votes
2 answers
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} $ ...
Colin McQuillan's user avatar
47 votes
17 answers
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 ...
Joe Fitzsimons's user avatar
13 votes
1 answer
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 ...
Douglas S. Stones's user avatar
2 votes
1 answer
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.
user avatar
27 votes
6 answers
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 ...
user avatar
2 votes
3 answers
712 views

Template Metaprogramming and Turing Completeness

I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will actually build a Turing machine ? I have read that ...
Prasoon Saurav's user avatar

15 30 50 per page
1
244 245
246
247 248
257