# All Questions

10,590 questions
Filter by
Sorted by
Tagged with
14 views

### Weaker halting problem

It is well known that no TM can solve the Halting Problem, i.e. there is no program H(P, s) that when given as inputs any program P and any string s, will always terminate and correctly tells if P ...
11 views

### Difference (dynamic b-)matching and streaming

I try to find good paper on dynamic b-matching and wonder if there are similar words for the same problem. I understand that there is a difference between online b-matching and online b-matching, but ...
18 views

### Learning axis-parralel squares

My problem consists of giving an algorithm for a binary classification problem in $\mathbb{R}^2$ by using axis-parallel squares and to find its sample complexity. In this context we assume ...
12 views

### ML classification with missing inputs using joint probability distribution

I am self-studying the deep learning book by Goodfellow, Bengio and Courville(https://www.deeplearningbook.org/contents/ml.html). On page 100, it has a brief introduction to classification with ...
14 views

### Examples of inverse of trapdoor functions non-learnable with black-box query access?

The (informal) definition of trapdoor function is a one-way function with a trapdoor $t$ such that given $f$, it is easy to compute $f(x)$ for any $x$, but hard to compute $f^{-1}(y)$ efficiently ...
30 views

### Complexity of finite difference method

if I have a function $f:\mathbb R^N\to \mathbb R$ and i would like to compute all the partial derivatives of $f$ w.r.t. the $N$ input, which is the computational complexity using the (ones sided) ...
70 views

### What podcast should everybody listen?

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'...
34 views

### A 10-approximation algorithm for k-dominating set in unit disk graphs

Consider an undirected graph G = (V, E) whose vertices are laid on a coordinate plane and there is an edge between any two vertices if the Euclidean distance between them is less than or equal to 1 ...
28 views

### Dividing digraph to acyclic subgraphs NP completeness

Let G = (V, E) be a directed graph. Consider the problem of dividing V into two disjoint parts A and B such that there does not exist directed cycles in A or B. Prove that this problem is NP-complete ...
16 views

### How can we check the inequality of max on a finite family of the set? [closed]

Let $X \subset \mathbb{R}$ be finite non-empty set and $P = \wp(X) - \{\emptyset\}$ and let $max(X)$ the function which returns the highest value of $X$, e.g., $max(\{0.1, 0.3, 0.22\}) = 0.3$. Now ...
61 views

### Jobs in theoretical computing [closed]

I just realized that I have a strong preference for everything in computer science that is based on pure theoretical concepts, such as: relational databases (algebra), parsing, Boolean algebra, graph ...
23 views

### Geodetic graph which is not block graph

I am looking for a graph which is geodetic (between every pair of nodes there is a unique shortest path) and it is not block graph or complete graph. Anyone an idea of such an example?
56 views

### What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that: To the best of our knowledge, ...