All Questions

Filter by
Sorted by
Tagged with
2
votes
0answers
27 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}\...
1
vote
0answers
21 views

Axioms between UIP with function extensionality and univalence

I am wondering if there are any interesting axioms, denoted $A$, which satisfy the following properties: $iMLTT+UA \implies \neg A$ $iMLTT+UIP+FunExt \implies \neg A$, or more specifically ...
-4
votes
0answers
24 views

I need solution for assignment which I've to submit today

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
1
vote
1answer
185 views

Quantum Computing: project ideas

I'm an undergraduate computer science student and I'm currently taking a course in the field of quantum computing requiring projects. I've read already a huge number of articles but still cannot come ...
9
votes
3answers
293 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 ...
-4
votes
0answers
18 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?

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
18 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
52 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 ...
5
votes
1answer
137 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 $...
-4
votes
0answers
44 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?
4
votes
0answers
63 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
80 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
34 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
149 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
40 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
34 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
36 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
331 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
96 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
5answers
514 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
44 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
128 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
50 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
22 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
50 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
268 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
61 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
301 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
366 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, ...
6
votes
0answers
77 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
107 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?
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
127 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
114 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
74 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 ...
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
397 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 ...

15 30 50 per page
1
2 3 4 5
212