All Questions

Filter by
Sorted by
Tagged with
-1
votes
1answer
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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) ...
0
votes
2answers
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'...
-2
votes
0answers
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 ...
-4
votes
0answers
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 ...
-1
votes
0answers
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 ...
-3
votes
0answers
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 ...
-1
votes
0answers
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?
3
votes
1answer
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, ...
0
votes
0answers
54 views

Why non-uniform learnability does not imply PAC learnability?

PAC guarantees provide us a a learning algorithm $A_n(\cdot)$ and sample complexity bound $n_{\mathcal{F}}(\epsilon,\sigma)$ that ensures $ P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\...
-3
votes
1answer
42 views

Finding a non-negative solution to an integer system of linear equations

Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
3
votes
1answer
79 views

What is the complexity of this weighted b-edge matching problem?

I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem: Input: An undirected multigraph $G = (V, E)$ without loops, an edge partition $(E_1,...
-2
votes
0answers
53 views

3SAT to 3,{3,4} SAT

I'm trying to review Sevenster's research regarding the NP-Completeness of the decision version of the Battleships problem. It proves there that any instance of 3,{3,4}SAT (a subset of 3-SAT) can be ...
1
vote
1answer
117 views

Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
-2
votes
0answers
43 views

Is Safe AI undecideable? [closed]

Is Safe AI undecideable? Here's my proof attempt: Define a "safe" Turing machine to always produce output that is "safe". Suppose Turing machine A decides ...
-1
votes
1answer
83 views

Time complexity for multiplying two lower triangular matrices

I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices? $$ \begin{bmatrix} ...
-2
votes
0answers
21 views

Why exactly can real valued time sequences be replaced with rational valued timed sequences?

for my bachelor's thesis I'm looking into timed automata, so I started with A theory of timed automata. On page 16 of the pdf the following proof is provided to show that rationals can be used in time ...
-5
votes
0answers
32 views

What is the efficiency of this javascript algorithm?

I wrote a really cool code sample which I will include at the end of this question. It completes in O(N) time in the javascript engine according to my debugging tools, but solves the boolean ...
-4
votes
0answers
38 views

I need solution for assignment which I've to submit today [closed]

I need solutions i don't have time to learn all this in few hours pls help me. All problem is from book peter linz! Peter linz questions
4
votes
0answers
88 views

Rules between UIP with function extensionality and univalence

I am wondering if there are any interesting rules/judgemental equalities, denoted $A$, which satisfy the following properties: $iMLTTfe+UA \implies \neg A$ $iMLTTfe+UIP \implies \neg A$, or more ...
4
votes
0answers
73 views

Optimal point placement on integer lattice

What is known about the following point placement problem? For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute \begin{eqnarray*} \mu_1(N,n)\triangleq\min_{\mathcal{P}\...
-4
votes
0answers
20 views

If an array requires x bytes to be created, and the free memory of a computer is >x, will the array always be created? [closed]

This might be an annoying question to some of you because I am a novice in computer science, and also because this might not be the perfect place to post this, so I understand that this might get ...
2
votes
0answers
29 views

What is the minimal class of subshifts for which conjugacy is known to be undecidable?

The question of whether two finite one directional shifts are conjugates is known to be decidable. The same question for sofic shifts is famously open. I have seen that some works manage to prove ...
1
vote
1answer
65 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
0answers
47 views

What can cstheory tell about Reprogramming viruses and Programming mechanisms of viruses? [closed]

Is there a natural computational model that helps understand Reprogramming viruses and Programming mechanisms of viruses?
7
votes
0answers
109 views

Subgraph isomorphism on graph sequences

I'm looking for a subgraph isomorphism algorithm that takes advantage of properties of graph sequences. Say $\{G_i\}_{i=1}^k$ is a sequence of graphs on vertex set $\{1 ... n\}$, and two consecutive ...
0
votes
1answer
61 views

Notation of sequences in rate distortion theory

I have been reading whatever sources I could get my hands on today, regarding this problem. Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas ...
-3
votes
0answers
42 views

Time complexity of binary search tree construction [closed]

"Every comparison-based algorithm to sort n elements must take Ω(nlogn) comparisons in the worst case. With this fact, what would be the complexity of constructing a n-node binary search tree and why?"...
-3
votes
0answers
39 views

Channel Coding theorem (Code Symmetry)

I am studying the book "elements of information theory"- THOMAS M. COVER JOY A. THOMAS, and when it proves the channel coding theorem, one of the things it states is that all codes "C", are symmetric (...
2
votes
0answers
42 views

Relation between automorphism group of a linear code and its dual code

Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc. In ...
9
votes
1answer
182 views

The theoretical complexity of Go - The state of the art

What are the latest advances in theoretical complexity of Go? I know some early works about the complexity of Go: "Go is polynomial-space hard" proved that Go is PSPACE-hard. "Ladders are PSPACE-...
2
votes
0answers
102 views

Proof systems induced by NP-complete problems

Satisfiability is the fundamental NP-complete problem. Cook-Reckhow theorem states that the existence of a propositional proof system that admits polynomial size proofs for all tautologies implies ...
11
votes
3answers
379 views

Applications of sunflower lemma in theoretical computer science

In one lecture by Kewen Wu who is one of the authors of paper Improved bounds for the sunflower lemma, it is said that the sunflower lemma can be applied to many fields like circuit lower bounds ...
0
votes
0answers
26 views

Best known bounds on feedback arcset in high-girth directed graphs?

I asked this question over at MathOverflow, but thinking about it a little more I think it is a more natural fit here. Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every ...
-4
votes
0answers
65 views

What is the evidence that the worst-case runtime of CDCL is exponential in the length of CNF?

Current SAT solvers have worst-case runtime exponential in the number of variables, leading many computer scientists to speculate that P does not equal to NP. However, the P vs NP problem cares only ...
-1
votes
0answers
23 views

Evolving expression trees to approximate an unknown function

I started a small toy project[0], that given a black box function: $\mathbb{R}^n \to \mathbb{R}$ tries to find a good approximation (if not exact solution) by evolving expression trees. These ...
-2
votes
0answers
52 views

Describing graphs in terms of subgraphs

I want to create a graph description language that's based on defining and using parameterized subgraphs as "building blocks", specifying exactly how these blocks connect. My use case is describing ...
3
votes
1answer
136 views

Areas of research and open problems in functional programming [closed]

What are the major areas of functional programming that require more research and development? For example, I know a lot of people are asking for dependent types in Haskell, and someone at my uni is ...
2
votes
0answers
63 views

Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? // Quantum automata

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...
-4
votes
1answer
33 views

Distinguish Graph from Tree using Adjacency Matrix

Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle). For example, given the adjacency matrix: ...
2
votes
0answers
85 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. ...
4
votes
1answer
405 views

Church-style CoC with axiom for induction over Church-encoded unit, is it consistent?

If we start with the Calculus of Constructions, and then use the following definitions for the Church-encoded Unit: ...
-2
votes
0answers
39 views

performance vs complexity given an optimization problem

Newbie here. I want to read a few papers on the theory of the performance of an algorithm vs its complexity for a given problem. I will give an example shortly but my aim is to find papers, books, ...
6
votes
0answers
80 views

Programmatic higher inductive/inductive-inductive types with equalities between equalities

I can think of practical HITs in verified software that capture some form of alpha equivalence, context equivalence or the example which defines well-typed syntax of type theory from Signatures and ...
7
votes
1answer
311 views

Technical lemma about curves used in original proof of PCP theorem

I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn'...
1
vote
0answers
64 views

Explicit binary codes with block length n, distance n / log n, rate 1 - o(1)?

What are the best (i.e., highest-rate) explicit binary codes with block length $n$ and minimum distance $d$, in the regime $d = n^{1 - o(1)}$? The "redundancy" of a code is the difference between the ...

15 30 50 per page
1
2 3 4 5
212