All Questions

Filter by
Sorted by
Tagged with
-2
votes
1answer
15 views

Confusion over how to merge for Huffman Coding Algorithim [closed]

I don't understand why the node formed at the circled step $"2"$ wasn't merged with the node coded with $"1011"$.
-2
votes
1answer
359 views

Can I show algebraically that this regular expression accepts all binary strings?

The task is to prove that (0+1)* and 0*(1.0*)* are equivalent. 1. http://rubular.com/r/K9Hp9tU6px 2. http://rubular.com/r/N8VpoEcch4 EDIT: Forgot that + was ambiguous here! I want to prove that the ...
4
votes
1answer
854 views

Knapsack with dependent profits (pairs of items)

I'm working on a problem which MAY be reduced to the following version of Knapsack: Suppose two items $e_i$ and $e_j$ have profit $p_i$ and $p_j$ respectively. However, if both items are present in ...
1
vote
1answer
93 views

Reference request: Depth- (or Breadth-) first search with hints?

Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it. Would it be possible to pre-process the graph and ...
4
votes
3answers
293 views

What podcast should everybody listen to?

This list was inspired by the lists: What are the popular science books that inspire TCS? What Books Should Everyone Read? What papers should everyone read? What videos should everybody watch? I don'...
25
votes
1answer
520 views

Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that ...
1
vote
0answers
33 views

Efficient algorithm for finding segregators in a directed acyclic graph

Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
3
votes
0answers
123 views

Weakest model of computation that can typecheck?

What's the weakest (known) model of computation (or smallest language class) that can decide whether a simply-typed lambda calculus program type checks? What about an (explicitly typed) CoC program?
2
votes
1answer
57 views

Approximation Ratio of Local search for $k-$center problem

In the $k-$center problem, you're given $V$ points in Eucledian space, and you're asked to get a subset $C\subset V, |C|=k$ such that $\max _{v\in V}d(v, Closest-Center(C,v))$ is minimized. Now I am ...
6
votes
2answers
137 views

2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

How can I convert a 2DFA to a normal DFA. Is there an algorithm/elegant way to do that ? I've been researching this for a few days but I coundn't find anything. Actually I want to implement that in ...
2
votes
1answer
83 views

About estimating escape time of gradient Langevin dynamics

I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly ...
21
votes
2answers
8k views

How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
6
votes
0answers
140 views

An optimal subspace projection problem

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\...
4
votes
0answers
75 views

Can we make Tensor Sketch any faster?

For all constants $\epsilon,\delta>0$, let $k=\epsilon^{-2}\log1/\delta$. We know there exists a linear transformation $M : \mathbb R^{k^2}\to \mathbb R^{\tilde O(k)}$, such that for all $x\in\...
-3
votes
1answer
36 views

Show that membership in L is undecidable [closed]

Let L ⸦ {0, 1}* be the language {(M, x) | Turing Machine M on input x enters every state of M at least once}. How can I show that membership in L is undecidable?
3
votes
1answer
212 views

Busy Beaver Equivalent for the Untyped Lambda Calculus

In the same way that the Busy Beaver function is defined for Turing Machines, we could define a similar function for the untyped lambda calculus: Over all terms in the ULC composed of ...
5
votes
1answer
127 views

Kolmogorov Complexity of a Decidable Language

The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable ...
1
vote
0answers
28 views

Non Turing-Complete Models, Conditional-Complete function?

I know well the distinction between the class of Partial Recursive Functions, and $\mu$-Recursive, i.e. the latter is Turing Complete and the former is equivalent to the LOOP-Program model of ...
0
votes
0answers
16 views

Smallest/largest number of clauses, of the formula containing them being exact kCNF&there're r(or just r=1) satisfying assignment(s) with n variables?

When I try analysing the property of kCNF. I meet a seemingly inessential problem that is more likely to be a combinatorial math problem. What is the smallest/largest number of clauses where the ...
3
votes
1answer
106 views

What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)

According to Immerman's Descriptive Complexity diagram, there is a logic called $\mathsf{FO(REGULAR)}$ which captures $\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. ...
7
votes
1answer
207 views

Kleene Algebra for star-free regular expressions

TLDR: Is there a notion of Kleene Algebra for star-free regular expressions? Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent ...
3
votes
1answer
122 views

Zero Knowledge proofs of knowledge

Is there Zero Knowledge Proof of Knowledge protocol for Hash function? (If h(v)=w) without revealing v to the anyone can we prove that we know 'v')
-1
votes
1answer
58 views
3
votes
1answer
69 views

Interval partitioning with restrictions: NP-complete or efficiently solvable?

The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. ...
2
votes
2answers
207 views

Is the maximum independent set in cubic planar graphs NP-complete?

In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
5
votes
1answer
153 views

Is there any equation-based method for transforming Büchi-automata to omega-regular language?

I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows. First we construct a set of equations ...
2
votes
1answer
85 views

NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the ...
0
votes
0answers
41 views

What is the meaning of an Oracle in data clustering?

I am not sure whether this is the best place to ask this question. I am in the process of researching the area in data clustering as well as the algorithms that are associated with it and the term ...
9
votes
2answers
4k views

Restriction of Exact Cover by 3-sets

Exact cover by 3-sets problem is defined as: Instance: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \} $ of 3-elements subsets of $X$ (triples); Question: Is ...
2
votes
0answers
33 views

Parigot encoding for F-Algebras

In this answer it is shown we can encode inductive types in System F-omega using the church encoding: $Fix F = \forall T : \mathsf{Type} \,.\, (F T \to T) \to T$ for some type constructor $F$. It ...
0
votes
1answer
74 views

Examples for derandomization via small sample spaces [closed]

I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises. I'm trying the technique of "Derandomization" ...
0
votes
2answers
818 views

Password checking algorithm

Usually to check password validity we used to create over given password it hash value and compare it with stored one. So password protection relies on strength of hashing function. Could it be used ...
6
votes
3answers
401 views

Reference Request: Computational Learning Theory

Pretty soon I will be finishing up Understanding Machine Learning by Shai Ben-David and Shai Shalev-Shwartz. I absolutely love the subject and want to learn more, the only issue is I'm having trouble ...
7
votes
2answers
172 views

Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids. To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of ...
24
votes
2answers
615 views

Formally Verified Complexity Theory

Is there any ongoing project to formally verify the theorems and proofs of complexity theory using a proof assistant like Coq? Are there any boundaries to doing this?
0
votes
0answers
23 views

Is this a proof that diophantine equation solutions can't be bounded by power towers?

From this 2017 paper on upper bounds for solutions to diophantine equations: Conjecture 1. If a system of equations S ⊆ Bn has exactly one solution in positive integers x1, . . . , xn , then x1, ....
1
vote
0answers
41 views

Is there a notion of Probably Approximately Correctness in Unsupervised Learning? [closed]

I've been learning a little bit about computational learning theory, but most of what I've seen so far is related to supervised learning. Perhaps dimensionality reduction will be touched on, but not ...
1
vote
0answers
18 views

Are the intermediary sets in maximum cardinality search optimal in some way?

The maximum cardinality search (MCS) algorithm works as follows. Given a weighted graph $G = (V, E)$ where $w(u, v)$ denotes the weight of the edge $\{u, v\}$, we select a start node $a \in V$ and do ...
3
votes
2answers
143 views

What are those deterministic algorithms for k-SAT that are not derandomization of random algorithms like PPSZ and Schöning's local search?

I am doing a survey on k-SAT where time complexity is in terms of n, i.e. the number of variables in a formula. As for the fast algorithms for k-SAT, we see biased-PPSZ, PPSZ, Schöning's local search,...
2
votes
1answer
94 views

NP-completeness: sum of “some” paths in a spanning tree

I suspect this problem is NP-complete but I couldn't prove it, if anyone can help I'll be very grateful: Instance: undirected, unweighted, connected graph $G=(V,E)$, positive integer $K \in \mathbb{Z}...
3
votes
0answers
62 views

Uniformly sampling or counting connected graph partitions with any number of blocks

Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard? To clarify: By a ...
5
votes
1answer
239 views

Name for a special family of languages?

I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$: $\mathcal{F}$ consists ...
6
votes
2answers
108 views

Multimodal logic with quantification over modal operators

I take a multimodal logic to be a logic with multiple (potentially infinitely many) primitive modal operators. I am curious if anyone has studied a logic that allows one to quantify over the modal ...
25
votes
1answer
625 views

Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?

Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, ...
5
votes
1answer
71 views

Decidability of rank-k polymorphism vs. System F

There's a paper by Kfoury from 1992, "Type Reconstruction in Finite Rank Fragments of the Second-Order $\lambda$-Calculus", that proves that type inference for Curry-style rank-$k$ polymorphic lambda ...
45
votes
9answers
7k views

Best Upper Bounds on SAT

In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT." I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
2
votes
0answers
110 views

Types as abstract interpretations

In Types as Abstract Interpretations, Cousot seems to propose a method to derive various type systems by succesive abstract interpretation of the denotational semantics of an untyped lambda-calculus. ...
20
votes
4answers
5k views

Is there any connection between the diamond norm and the distance of the associated states?

In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such ...
0
votes
1answer
80 views

Finding the size $k$ subset in a metric space that maximizes the min distance between elements

I have a metric space $(X,d)$ and I'd like to find a subset of size k of far away elements. We can cast this as the following optimization problem $\max_{S \subseteq X, |S| = k} ( \min_{i \not = j, ...
2
votes
0answers
314 views

Complexity of solving a polynomial equation

Given a polynomial equation of degree n with m variables, that is guaranteed to have at least one solution, what is would be the ...

15 30 50 per page