4
votes
0answers
16 views

Two papers give contradictory bounds on linear probing. How do I resolve the disparity?

I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, ...
1
vote
0answers
8 views

Optimal boolean function encoding with bounded error

Let $F = \{f:\{0,1\}^n \to \{0,1\}\}$ be the set of all boolean functions on $n$ bits. Any such function can be written as a polynomial $f(x) = a_0 + \sum_i^n a_i x_i + \sum_{i,j}^n a_{i,j} x_i x_j + ...
-2
votes
0answers
55 views

On counting class $\oplus P$

If a counting problem $\Pi$ is $\#P$-complete (call $\Pi_2$) then guessing output modulo $2$ of $\Pi$ is in $\oplus P$. Assume the decision version $\pi$ of $\Pi$ is in $P$. Is there a characteristic ...
-2
votes
0answers
51 views

What are some example problems for integer programming that are *not binary*

I'm interested in NP-hard problems that have a "nice" integer-programming formulation (quadratic or linear, with quadratic or linear constraints) that is not binary. Of course it is always possible ...
-4
votes
0answers
33 views

Is a k-partite graph with k-cliques a perfect graph? [on hold]

Suppose that we are given a k-partite graph that also contains one or more non-overlapping k-cliques. Is this graph a perfect graph?
3
votes
0answers
61 views

Weighted $l_1$ distance

So there are many well known algorithms for approximate nearest neighbor on the $\ell_1$ distance. My question is, what about the weighted version of the problem (where the weights are specified along ...
0
votes
0answers
36 views

What is known about the Newton/Sum of Powers Sketch?

In "Set Reconciliation with Nearly Optimal Communication Complexity" and "Straggler Identification in Round-Trip Data Streams via Newton’s Identities and Invertible Bloom Filters" the authors sketch ...
-3
votes
0answers
25 views

Clustering of a signed graph

A signed graph is a graph in which edges are labeled as positives or negatives. First task is to form $k$ number of clusters of signed graph such as to maximize total number of positive links inside ...
-2
votes
0answers
49 views

Why is factoring a certain number such a breakthrough in quantum computers? [on hold]

I´m doing an investigation about quantum computers, and wondered why in a certain timeline I found it showed: Researchers at the University of Bristol created an all-bulk optics system that ran a ...
7
votes
0answers
107 views

Maximum weight matching and submodular functions

Given a bipartite graph $G = (U \cup V, E)$ with positive weights let $f: 2^U \rightarrow \mathbb{R}$ with $f(S)$ equal to the maximum weight matching in the graph $G[S\cup V]$. Is it true that $f$ ...
0
votes
0answers
83 views

On classes $AWPP$ and $APP$

(1) $PP$ contains problems like 'is perm(M)>k'. So what problems does $AWPP$ and $APP$ contain with respect to permanent? (2) Since it is not known if $NP$ is in $AWPP$ or $APP$ is there a candidate ...
-9
votes
0answers
23 views

How do I solve this? [on hold]

How do I start with this problem:- Q)Design a DFA for set of strings over {a,b} in which there are at least two occurrences of b between any two occurrences of a.
0
votes
1answer
100 views

Evidence of containment of $PH$

We know that $PH$ is in $P^{PP}$ or in $P^{\#P}$ and we do not know if $PH$ is in $PP$. We know $AWPP$ and $APP$ are weakening of $PP$ where $AWPP$ is in $APP$ is in $PP$. (1) Is it possible if $PH$ ...
8
votes
0answers
52 views

Consequences of bipartite perfect matching not in NL?

Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$? I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be ...
0
votes
0answers
24 views

Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$ [migrated]

In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$. When would one use a norm other than $L^2$ in a $k$-$d$ tree?
-4
votes
0answers
49 views

How many subsets of even cardinality does an n-element set have? [on hold]

How many subsets of even cardinality does an n-element set have ?
1
vote
1answer
72 views

Minmax vs Maxmin

I'm reading this paper about building a combat simulator for 8 unit vs 8 unit mini combats in StarCraft: Brood War. The basic idea is to build a search tree simulating these small combats in order to ...
-4
votes
1answer
56 views

How to check if a the language represented by a DFA is finite [on hold]

I am studying regular languages and D FA. I have implemented D FA in Java. I have to write a function which tells if the language represented by a D FA is finite or not. I need a method or algorithm ...
0
votes
0answers
4 views

Where Can I Find DFA Practice? [migrated]

Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so ...
1
vote
0answers
43 views

Maximal Clique partition of vertices with smallest number of cut edges

I am given a simple undirected graph $G(V, E)$. I want to partition $V$ into $b$ Maximal cliques: $\{C_1, C_2, ..., C_b\}$ such that the number of edges that cut across two cliques is the minimum. $b$ ...
0
votes
0answers
33 views

Bipartite matching with constraint: match at least one node of each subgroup

This problem is derived from "How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?" by adding an additional constraint: each vertex belongs to ...
1
vote
0answers
29 views

Quicksort optimal partition

Has the question been studied, how to find the shortest sequence of partition choices so that a quick-sort algorithm can sort a set? To be clear, I'm not interested in quick sort per se, but in ...
4
votes
0answers
145 views

Subtyping rules for extension of System $F_\omega$ with subtyping and kind-level variance tracking

I need an extension of System $F_\omega$ with subtyping, and where the variance of type constructors is reflected in their kind. Unfortunately, System $F^\omega_{<:}$, as defined in chapter 31 of ...
-4
votes
0answers
26 views

Oracle database [closed]

In an Oracle database with standard configuration, if transaction T1 is reading a row of data, and transaction T2 wants to read the entire table (the table that includes the row T1 is reading), T2 ...
3
votes
0answers
98 views

Non-Linear Programming with \min operator in the constraint

Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1. \begin{align} \text{maximize } &\sum_{i,j=1}^{m,n} ...
-2
votes
0answers
47 views

The importance of objective function min and max values in multi-objective optimization by sorting non-dominated fronts

Assume you want to optimize according to some functions. When the relative value of the fitness functions is unknown, multi-objective optimization can be done sorting a list of potential solutions ...
-3
votes
0answers
63 views

What machine learning book should every one read? [closed]

Need recommendation for good machine learning books for TCS community. Machine learning is becoming more and more important. It has profound theoretical problems and many practical applications.
9
votes
1answer
142 views

Is a quadratic nondeterminism speed-up of deterministic computation plausible?

This is a follow up to nondeterministic speed-up of deterministic computation. Is it plausible that nondeterminism (or more generally alternation) would allow a general quadratic speed-up of ...
3
votes
0answers
52 views

Streaming algorithms for sum

First of all, I am not sure whether this is a research level question. Please let me know if it is not. The question is about streaming algorithms for the sum of the given data stream. From ...
-4
votes
0answers
18 views

K means algorithm - computing the centroid using Jaccard distance [closed]

How do I compute the centriod of a cluster using the Jaccard distance? Assume I have two sets: A={a,b} and B={b,c}, what is their centroid? JaccardDistance(A,B) = 1- JaccardIndex(A,B) = 1- 1/3 = 2/3 ...
6
votes
1answer
177 views

Problem of graph bi-partition (related to graph isomorphism)

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to ...
0
votes
0answers
79 views

Heyting algebra in simply typed lambda calculus

The Emil Jeřábek's comment in Can boolean algebra be expressed in simply typed lambda caclulus? give rise to the following question: Can some non-trivial Heyting algebra be expressed in simply typed ...
3
votes
1answer
113 views

maximizing inner product

Given two lists $L,L'\subseteq\mathbb{R}^d$ of $n$ vectors each, how fast can we compute for all $p\in L$ the vector of $L'$ that maximizes the inner product with $p$, i.e., $\arg\max_{p'\in L'} ...
5
votes
0answers
53 views

Finding of dimension of algebraic varieties

I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf). Are ...
4
votes
1answer
74 views

What is a canonical term of $\text{Id}_A(x,y)$ if $x$ is not jugdmentally identical to $y$?

In the context of constructive type theory, a term inhabiting some type is said to be in canonical form if it is explicitly built up using the constructors of that type. Particularly, the only ...
13
votes
3answers
329 views

Nondeterministic speed-up of deterministic computation

Can nondeterminism speed-up deterministic computation? If yes, how much? By speeding-up deterministic computation by nondeterminism I mean results of the form: $\mathsf{DTime}(f(n)) \subseteq ...
2
votes
1answer
151 views

Is there any efficient algorithm for computing all semigroups of order n? [closed]

Is there any efficient algorithm for computing all semigroups of order n? I found the following paper which solves a bit different problem. Veronique Froidure and Jean-Eric Pin, "Algorithms for ...
5
votes
2answers
121 views

Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

Let $\Sigma$ be a finite alphabet. A trivial finite automaton can accept the language $L_1 = \{w\;|\;w\in \Sigma^*\}$. A simple pushdown automaton can accept the language $L_2 = \{ww^R\;|;w\in ...
0
votes
0answers
53 views

How often can a linear speed sort succeed? [migrated]

Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$. What kind of bounds can we place ...
6
votes
1answer
97 views

Lower bound on prefix code lengths

For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits: $$ f(n)=\max_{|k|\le n}\left|C(k)\right|. $$ (Note that by taking ...
-2
votes
0answers
24 views

How does the receiver in cognitive radio networks know exactly what channels to listen in on? [closed]

I understand the basic idea of cognitive radio networks. But all of the literature I read about mitigating jamming attacks, focuses on channel hopping using a randomized strategy, based on some ...
-4
votes
0answers
40 views

non-Hamiltonian graphs [closed]

What is the relation between the set of non-Hamiltonian graphs, all of whose members are presumably not known, and the dynamic linear programming and factorial solutions to the TSP in general graphs? ...
8
votes
1answer
90 views

Sorted dictionary structure supporting efficient merges?

Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the ...
6
votes
2answers
330 views

Is it known whether $BPP\cap NP\subseteq RP$?

The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?
0
votes
1answer
70 views

Max-sum graph-partition for maximizing intra-edge weights?

I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results. Input: A graph G with negative or ...
-2
votes
0answers
51 views

References to an integer vector sum minimization problem?

Given a length $n$ query vector (integer entries), and a set of length $n$ base vectors with integer entries, the optmization problem is to minimize the sum of coefficients in a nonnegative integer ...
7
votes
1answer
229 views

Parity P and AM

What is known about non-trivial inclusions of $\oplus\mathsf{P}$ in other classes? In particular, is it known whether $\oplus\mathsf{P}$ is contained in $\mathsf{AM}$? The same questions apply to the ...
30
votes
9answers
12k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
-8
votes
1answer
61 views

In what way are these two context free grammar equal? [closed]

Consider the grammar G1: A->Aα|β G2: A->βX X->αX|ϵ Its was said that these two grammars are equal. Should something like left recursion be removed? In what sense are these equal? Am really ...
3
votes
1answer
143 views

Variant of Subset Sum Problem with Changing Bound

Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that $$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$ ...

15 30 50 per page