All Questions

6
votes
0answers
136 views

Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
9
votes
1answer
390 views

Proof techniques for showing that dependent type checking is decidable

I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and ...
1
vote
1answer
55 views

Sample complexity for learning Boltzmann Distribution parameters

I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision. Suppose that there are N possible states ...
0
votes
0answers
44 views

Efficient topological sorting of the cartesian product of DAGs

Let us consider n directed acyclic graphs $(G_i)_{1\leq i \leq n}$ and G their cartesian product (with the induced edges) : G is still a DAG. Let us suppose that each vertex has a value, defined as ...
1
vote
0answers
168 views

Automated theorem proving PhD

I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas? Thank you!
0
votes
0answers
40 views

Function that maps non-linear distribution to normal distribution while maintaining distance

I have a collection $X$ of 10 million $(x,y,z)$ 3-tuples, where $x$, $y$, and $z$ are all numbers between 0 and 1. The distribution of $x$, $y$, and $z$ values are complex, and the distributions of $...
5
votes
1answer
177 views

Boolean circuits which correspond to L/poly

Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$. Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
1
vote
1answer
67 views

Color shifting in a bipartite graph

Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
7
votes
0answers
170 views

How many different proofs are there of parity is not in AC0?

The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
2
votes
0answers
25 views

Heuristics for exact #3COLORING close to the 3-colorability threshold

What are some fast heuristics for exactly counting 3-colorings of graphs close to or at the 3-colorability threshold? Is there literature on the average-case performance for any of these methods?
8
votes
0answers
221 views

L/quasipoly vs NL/poly

Savitch's theorem shows that NSPACE($S(n)$) $\subseteq$ SPACE($S(n)^2$), which means that nondeterminism can be replaced by more spaces in this situation. Is it known whether nondeterminism can be ...
0
votes
0answers
34 views

How should a reduction to the Cardinality Constrained Quadratic Knapsack Problem work?

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
6
votes
2answers
249 views

Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
2
votes
1answer
99 views

Circuit complexity of group actions

Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{...
8
votes
1answer
145 views

What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus?

This is a reference confusion. Sometimes I see people use the term "Moggi's computational metalanguage" to refer to the calculus presented by Moggi, and sometimes to "Moggi's computational lambda ...
7
votes
1answer
195 views

TIME(n) versus TIME(nlogn)

The time hierarchy theorem implies TIME($n$) is strictly contained in TIME($n\log^{1+ε}n$) for all ε>0. Is the relationship between TIME($n$) and TIME($nlogn$) known?
6
votes
0answers
92 views

Efficient quantum algorithm for CLASSICAL FFT

Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples. I need to find the amplitude and phase of the K dominating ...
3
votes
1answer
97 views

Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?

Does there exist an algorithm, about which a non-constructive $\omega$-consistent theory $A$ can prove that it has time complexity $O(f(n))$ where $n$ is some univariate function of the input, but ...
2
votes
0answers
82 views

Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

What is known about the complexity of solving (or approximately solving) the following problem? INPUT: Graph $G=(V,E)$ and constants $L$ and $K$. OUTPUT: The maximum size of any set $S$ of simple ...
2
votes
3answers
175 views

Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself?

Usually, in Pure Type Systems, the type of a λ/∀-bound variable is only accessible on its body. That is, on λ (X : A) -> B, <...
1
vote
0answers
50 views

Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

I am wondering if this is a topic that has had research done... If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
2
votes
0answers
98 views

Complexity of solving a polynomial equation

Given a polynomial equation of degree n with m variables, that is guaranteed to have at least one solution, what is would be the ...
3
votes
2answers
171 views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
7
votes
0answers
52 views

Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem: Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
0
votes
0answers
61 views

Proving that a problem is coNP-complete [duplicate]

Let $\le^{p}_{T}$ be the Turing or the Cook reduction and $\le_{m}^{p}$ the Karp-Levin reduction. I know that to prove a problem $P_1$ is coNP-complete I just need to show that $P_1 \in coNP$ and ...
3
votes
0answers
45 views

Hardness of ancilla free quantum circuit extraction from circuit with ancillas

Is there any known result regarding the hardness of the following problem: Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that ...
5
votes
0answers
80 views

Parsimonious Reduction from Unique-3SAT to NAE-3SAT

Using the result by Valiant and Vazirani, we know that Unique-3SAT (3SAT with a unique solution) is hard unless NP=RP. Also it is widely believed that the "Unique" version of any NP-complete problem ...
0
votes
0answers
34 views

(Conditional) Lower Bounds for Space-Bounded Data Structures

I have a data structure problem which is solvable in $\tilde{O}(n^3)$ space with $\tilde{O}(1)$ query time, and I suspect that it's not solvable in $\tilde{O}(n^2)$ space with $\tilde{O}(1)$ query ...
1
vote
0answers
15 views

On-policy/Off-policy Offline/Online Evaluation: Which would be an example of Online Off-Policy Evaluation?

In the context of the following question: off-policy and offline policy reinforcement learning , it can be concluded that off-policy/on-policy learning can be orthogonal to an online/offline sampling ...
2
votes
0answers
44 views

Is topological conventional computation possible?

A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if $$(f\times\mathrm{Id}_{X})\circ(\mathrm{Id}_{X}\times f)\circ(f\times \mathrm{Id}_{X})=(\mathrm{Id}_{X}\times f)\...
2
votes
1answer
111 views

About a pre-processing step for primal–dual weighted set cover problem

I was reading the paper titled "Primal-dual RNC approximation algorithms.." by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1. They present a dual fitting based algorithm ...
4
votes
1answer
147 views

What is the etiquette of naming concepts after people?

There is a concept introduced by other researchers that I use in my work, and IMO it is appropriate to rename it to honor the inventors. Is it considered normal to just go ahead and name it like that ...
3
votes
0answers
71 views

How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?

A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if $$(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})=(\textrm{Id}_{X}\times f)\...
8
votes
1answer
314 views

Is it a bad idea to critique someone's paper in my first publication?

I am currently facing a situation that I am not sure how to handle. Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in ...
2
votes
1answer
155 views

Is there a difference between incompleteness and unknowable? [closed]

Godel proved that there are statements that are true but not provable. Unproven conjectures such "Twin Primes" might fall into such a class, as I understand. If so, does it mean that we will never ...
0
votes
0answers
74 views

Partitioning directed graph

I'm a newbie in the mathematical field of graph theory (started to dive into it only few days ago) but I'm a very fast learner and have deep mathematical background. I'm trying to find/develop an ...
1
vote
1answer
39 views

Soft Truth Values in the PSL model

This might sound like a trivial question. But since am starting out with my research in an area that is entirely new to me, I would really appreciate it if someone could kindly elucidate what Soft ...
3
votes
1answer
103 views

Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

I'm considering integer programming on an variation of Steiner Forest Problem: Given a graph $G=(V,E)$, a cost function: $c:E \rightarrow R^{+}$, a terminal set $T \subseteq V$, and a positive ...
1
vote
0answers
38 views

How to efficiently verify if a semantic symmetry of a CNF formula is valid?

It is easy to verify that a syntactic symmetry of a CNF formula is correct. Is it also possible to check in polynomial time that a semantic symmetry which is not a syntactic symmetry of a formula is ...
0
votes
0answers
28 views

How to obtain a resolution derivation of a symmetric image of a clause from its resolution derivation

Suppose we have a CNF formula $F$ and a syntactic symmetry $\sigma$ of $F$. If we have a resolution derivation $( c_1, c_2, \cdots, c_n=c)$ of a clause $c$, then a resolution derivation of the clause $...
10
votes
0answers
115 views

Do Banach spaces and linear contraction maps form a model of ILL with an exponential?

Recently, I read on the nLab that the category of Banach spaces and linear contractions is small complete, small cocomplete, and monoidal closed. This means that Banach spaces and short linear maps ...
4
votes
2answers
149 views

What does the category of RDF models look like in Institution Theory?

The Question in short Here is the question in its pure form. Details of my reasoning can be found below. The RDF1.1 spec semantics defines a model to consist of a set IR of objects and IP of ...
9
votes
1answer
144 views

How small can be a layered boolean circuit for a function with circuit complexity $s$?

Consider a function $f$ computed by a boolean circuit $C$ with $n$ inputs of size $s(n) = \mathsf{poly}(n)$ over the basis $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ (with indegree 2 for the $\...
5
votes
1answer
138 views

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that: 1) It is hard ...
8
votes
2answers
252 views

Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
6
votes
3answers
192 views

Why/when do we ever need transfinite loop variants?

I do not understand why one would ever need a transfinite loop variant. Why do natural-number-valued variants not suffice? My simple (but perhaps too naive) argument is: if a loop $L$ terminates ...
4
votes
1answer
94 views

Is the church-style affine calculus of constructions with unrestricted recursion consistent?

Suppose we take the church-style calculus of constructions, except with affine functions (variables must occur at most once) and mutual recursive definitions. For example: ...
13
votes
1answer
251 views

Function that is guaranteed to be one-way if one-way functions exist?

There is an old trick for writing down an algorithm that, if P = NP, solves SAT in polynomial time. Essentially, one lists all polynomial time machines and multi-tasks over them. Is there an ...
3
votes
0answers
44 views

Do there exists reversible gate sets of intermediate growth?

Suppose that $f_{1},...,f_{k}:\{0,1\}^{r}\rightarrow\{0,1\}^{r}$ are bijective functions. For all $n\geq r$, let $G_{f_{1},...,f_{k};r}=\subseteq S(\{0,1\}^{n})$ be the subgroup generated by i. the ...
5
votes
0answers
93 views

When do cellular automata on non-abelian groups not offer a computational speed up?

Suppose that $G$ is a finitely generated group and $A$ is a finite set. Then we shall give $A$ the discrete topology and $A^{G}$ the product topology; in particular $A^{G}$ is compact and totally ...

15 30 50 per page