# All Questions

10,094 questions
105 views

57 views

### How to get started with program synthesis

I am a CS Major, I am a programmer with 10 years of experience. i want to get to know about program synthesis. there are no video tutorials / courses available online. i have researched about Emina ...
38 views

43 views

### Differences in the requirements for different bit architectures [closed]

I've noticed that software that exists as a 32-bit-version and a 64-bit-version often has higher system requirements if you want to install the 64-bit version. One example is Windows 10 The 32-bit ...
82 views

### Robustness to non-uniform randomness vs. one-sidedness

Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly ...
142 views

### Does Hadwiger conjecture imply that NP = coNP?

(Disclaimer: I suspect the answer is no, but I fail to see why) Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture: The point is that if in a given ...
115 views

### Minimum distance of a code

Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am ...
37 views

### Reference on generalization of plane graph duality between bonds and simple cycles

I've also asked this question on Mathoverflow, but it hasn't gotten an answer after several months: https://mathoverflow.net/questions/316132/reference-on-generalization-of-plane-graph-duality-between-...
99 views

### Shortest s-t path when is allowed to ignore k weights

Given an undirected graph $G$ with $n$ vertices and $m$ edges, with non-negative weights on the edges, what's the best algorithm that computes the shortest path from $s$ to $t$, where you are allowed ...
23 views

### Minimum distance of a code [duplicate]

Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am ...
177 views

### Intuition Behind Strict Positivity?

I'm wondering if someone can give me the intuition behind why strict positivity of inductive data types guarantees strong normalization. To be clear, I see how having negative occurrences leads to ...
314 views

130 views

### How small can extension complexity be?

In this article on extension complexity of regular polygons https://arxiv.org/pdf/1505.08031.pdf it is mentioned that extension complexity of $n$ regular polygons should be $\theta(\log n)$. This is ...
160 views

### Are Turing machines still useful as model of computation?

Often when I hear "Turing machine," my mind's eye pictures a quaint infinite ticker-tape with a small little machine writing and erasing $0$'s and $1$'s. But when I'm forced to think about a Turing ...
111 views

### Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$

Given a $\Sigma^p_2$-complete oracle (i.e., $\Sigma_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function ...
76 views

### Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
96 views

260 views

### Naive definition of treewidth

Treewidth has arguably pretty involved definition. Recently I was thinking about a problem and turns out it easy to solve it for graphs with small naive treewidth''. Naive treewidth is defined as ...
177 views

### Extending Hindley-Milner to type mutable references

I have been trying to implement a programming language from scratch, and have gotten reasonably far. It reads just like Python, other than the fact that let is used ...
133 views

Let $G = (V, E)$ be an undirected graph. Let me take an edge $\{x, y\}$ (in blue in the drawing) such that $x$ and $y$ have other incident edges. Among the incident edges we choose one edge $e_x = \{... 0answers 53 views ### Complexity of #PP2DNF where we also count on the number of clauses The #PP2DNF problem is the following: we have variables$X = \{x_1, \ldots, x_n\}$,$Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form$\phi = \...
Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system \$f_1=\dots=f_{m}=...