All Questions

Filter by
Sorted by
Tagged with
5
votes
1answer
122 views

Conservative Approximation of Kleene-Mycroft Iteration for Polymorphic Recursion?

To perform type inference in the presence of polymorphic recursion, one can use a Kleene-Mycroft iteration to compute the principal type of an expression. To type $\mathsf{fix}\ f\ldotp e$, we define $...
-2
votes
0answers
24 views

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

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

Is a DTM with k-tapes not the same thing as a NDTM with k-branches?

In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use. If a language L is ...
-2
votes
0answers
23 views

Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision ...
1
vote
0answers
24 views

MWIS on the 2-section of a specific uniform linear hypergraph

My question concerns the maximum weight independent set (MWIS) problem on a certain (but "nice") graph. In particular, I am puzzled as to why I can seemingly solve the problem via its LP relaxation ...
4
votes
0answers
52 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 ...
2
votes
0answers
70 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. ...
-1
votes
0answers
27 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 ...
7
votes
1answer
126 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-...
-3
votes
0answers
34 views

Time complexity of binary search tree construction

"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?"...
-2
votes
0answers
28 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 (...
1
vote
0answers
33 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 ...
-4
votes
1answer
31 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: ...
7
votes
5answers
319 views

NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
2
votes
0answers
91 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 ...
6
votes
0answers
178 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 sunflower lemma can be applied to many fields like circuit lower bound ...
11
votes
5answers
509 views

Submodular functions: reference request

I would be very much interested in references to the theory of submodular functions (from basics to advanced). In particular, I am studying approximations to hard optimization problems and I want to ...
-2
votes
0answers
43 views

Software for SatSolver [closed]

I have system of binary nonlinear equations. I use CryptoMiniSat of SageMath to solve these equations. It took few hours. Is there any other free software which is faster than minisat?
0
votes
0answers
22 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
64 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 ...
3
votes
1answer
124 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 ...
-4
votes
0answers
42 views

Can images of everything there is (was and will be) be sequentially displayed on a screen? [closed]

I'm a technical architect in the field of software engineering. There is this question I had in my teen years (I'm 45) that kind of resurfaced after watching few episodes of DEVS. I understand that ...
0
votes
0answers
47 views

Does the underlying computational calculus in type theories affect decidability? [closed]

I'm looking for a high-level explanation although if that isn't possible or difficult, I'd prefer references to books/papers. I understand that modern type theory is inspired by Curry-Howard ...
140
votes
38answers
40k views

What videos should everybody watch?

Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...
-1
votes
0answers
21 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
49 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 ...
1
vote
1answer
266 views

Potentially stronger form of non-$ETH$

If we have a $2^{n^a}$ algorithm to $K$-$SAT$ where $a<1$ for all $K>2$ then $ETH$ fails and literature gives consequences. What are the consequences if $a=o(1)$?
14
votes
1answer
2k views

Why do functional programming languages require garbage collection?

What's stopping ghc from translating Haskell into a concatenative programming language such as combinatory logic and then simply using stack allocation for everything? According to Wikipedia, the ...
2
votes
0answers
60 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 ...
7
votes
1answer
297 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'...
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 ...
4
votes
1answer
355 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
37 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, ...
-1
votes
0answers
25 views

Bitcoin/Blockchain Consensus [closed]

Is there a formal proof that consensus will eventually be established in Bitcoin (if every participant in the system has <50% mining power and all honest partipants have >50%), as it is described ...
6
votes
0answers
75 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 ...
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 ...
4
votes
0answers
107 views

Program size versus program running time

Short "naive" question: Is it true that faster algorithms require longer programs ? Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) to ...
-2
votes
0answers
105 views

Impact of coronavirus on CS theory community

How adversely do we expect the coronavirus pandemic to affect the CS theory community? Which conferences have been cancelled, or have been moved? Which ones are likely to be affected in the future?
0
votes
0answers
53 views

Prove Product Partition is NP-complete in the strong sense [closed]

I am trying to understand how to prove that the Product Partition problem is NP-complete in the strong sense. The problem is similar to the normal Partition problem, except in this case the product of ...
2
votes
0answers
94 views

Is $SUBLOG\subset DTIME(n)$?

In the course of trying to give a more natural answer to a previous question of mine involving the complexity classes $$SUBLOG=\{L\mid L \text{ is recognizable by a sublogarithmic-space TM} \}$$ and $...
5
votes
0answers
126 views

What research is being done in classical complexity theory?

As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
2
votes
1answer
152 views

Does having unique normal forms imply weak normalization and confluence?

Consider a term rewriting system $\mathcal{R} = (\Sigma, R)$ over a signature $\Sigma$ with basic rewrite rules $R$. If $\mathcal{R}$ is weakly normalizing and confluent, then we know that each $\...
3
votes
1answer
113 views

Binary search on coin heads probability

Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function. I want to find the smallest $x$ such that $f(x) \ge 1/2$. If I had a way to compute $f(x)$ given $x$, I could simply use ...
0
votes
1answer
73 views

Optimization problems with same optimal value, but different approximation behavior

Context: related to this answer. I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense ...
-4
votes
1answer
44 views

combining graphs [closed]

I need to know the term for the following situation, so that I can find it in the various java graph-manipulating packages: suppose you have a node in a graph that itself can be replaced by another ...
1
vote
1answer
62 views

Running an algorithm for fixed amount of time on RAM model machine

Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "...
3
votes
2answers
396 views

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
13
votes
1answer
253 views

Universal Boolean Formulas

Fix $n\in\mathbb{N}$. Consider a rooted binary tree $T$ in which every non-leaf node contains either AND-gate or OR-gate. Let me say that $T$ is an universal formula if for every $f\colon\{0,1\}^n\to\{...
5
votes
1answer
128 views

When does a set of infixes determine a set of ($\omega$-) words

If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for ...
1
vote
1answer
406 views

Adherence of languages and the Dyck language

Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of ...

15 30 50 per page
1
2 3 4 5
212