texts: Computing 'Robustness of Magic' of $n$-bit W states

texts:
Question

What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$?

Background

$W$ states are entangled states where exactly one qubit is ON and every qubit has an equal chance of being ON if measured. For example, $W_3 = \frac{1}{\sqrt{3}} \left( |100\rangle + |010\rangle + |001\rangle \right)$.

In the paper "Application of a resource theory for magic states to fault-tolerant quantum computing", Howard and Campbell associate a quantum state $\rho$ with a cost $R(\rho)$ called "robustness of magic" and defined as:

$$R(\rho) = \min_x \sum_i |x_i|; \rho = \sum_i x_i \sigma_i $$

Where each $\sigma_i$ is a state that can be prepared by a stabilizer circuit (i.e. using only H, S, CNOT, and measurement gates). In other words, you try to find a weighted combination of stabilizer states that produce your desired state, and the cost you minimize while doing so is the sum of the weights' magnitudes. The minimum such cost is the robustness of magic of the state.

What I've Tried

The best-scoring decomposition I've found, for the $n$-qubit $W$ state, is:

$$s_{j,k} = X_j \cdot \text{CNOT}_{j\rightarrow k} \cdot H_j \cdot |0\rangle$$

$$S_{j,k} = s_{j,k} \cdot s_{j,k}^\dagger$$

$$W_n = \left(\sum_{j=0}^{n-1} \sum_{k=j+1}^{n-1} \frac{1}{n} S_{j,k} \right) + \left(\sum_{j=0}^{n-1} \frac{2-n}{n}|j\rangle \langle j| \right)$$

Which achieves a cost of $\frac{1}{n} \cdot \frac{n(n-1)}{2} + \frac{n-2}{n}\cdot n = \frac{3}{2}n-\frac{5}{2}$.

The best circuit construction I know for producing a large W state has a T-count that also scales like $\Theta(n)$. For example, here is an example construction that shows how to create a $W_n$ state using $2n-4$ T gates if $n$ is a power of 2:

Note that, if you want to compare the $2n-4$ T-count to the $\frac{3}{2}n - \frac{5}{2}$ potential-robustness-of-magic of the best-I-found decomposition, you must account for the fact that a $|T\rangle$ state's robustness-of-magic is $\sqrt{2}$ (not $1$).

Now, obviously, trying to find better and better decompositions is a reasonable way to upper-bound the robustness of magic... but this strategy will never create a lower-bound. What kinds of strategies do work for making lower bounds on this kind of problem?


texts: Complexity of a variant of partition problem

texts:
Motivated by this post, Strongly NP-complete variants of subset sum or partition problem, I am interested in this variant of partition:

Given a solution to balanced partition problem (both parts have same cardinality), find another solution that have maximum cardinality discrepancy (i.e. $||P_1|-|P_2||$ is maximum).

  Is there an efficient algorithm to find such unbalanced partition or is it NP-hard?

I am interested in pseudo-polynomial time algorithms or proving the problem to be strongly NP-hard.

P.S. Here is an example (as requested by @domotorp) $p1=\{2,2,3,4,5, 6\}$ and $p2= \{1, 1,3, 4, 5, 8\}$. The second solution is $p1=\{1,2,3,4,4, 8\}$ and $p2= \{ 1,2,3,5,5,6\}$ (the second solution is not optimal as p1 and p2 have equal number of elements).


texts: Time complexity of counting triangles in planar graphs

texts:
Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward procedure shows that it can be done in $O(n\log{n})$ time. My question is two-fold:

What is a reference for this procedure?
Can the time be made linear?

From the algorithmic proof of Lipton-Tarjan's planar separator theorem we can, in time linear in the size of the graph, find a partition of vertices of the graph into three sets $A,B,S$ such that there are no edges with one endpoint in $A$ and the other in $B$, $S$ has size bounded by $O(\sqrt{n})$ and both $A,B$ have sizes upper bounded by $\frac{2}{3}$ of the number of vertices. Notice that any triangle in the graph either lies entirely inside $A$ or entirely inside $B$ or uses at least one vertex of $S$ with the other two vertices from $A \cup S$ or both from $B \cup S$. Thus it suffices to count the number of triangles in the graph on $S$ and the neighbours of $S$ in $A$ (and similarly for $B$). Notice that $S$ and its $A$-neighbours induce a $k$-outer planar graph (the said graph is a subgraph of a planar graph of diameter $4$). Thus counting the number of triangles in such a graph can be done directly by dynamic programming or by an application of Courcelle's theorem (I know for sure that such a counting version exists in the Logspace world by Elberfeld et al and am guessing that it also exists in the linear time world) since forming an undirected triangle is an $\mathsf{MSO}_1$ property and since a bounded width tree decomposition is easy to obtain from an embedded $k$-outer planar graph.

Thus we have reduced the problem to a pair of problems which are each a constant fraction smaller at the expense of a linear time procedure.

Notice that the procedure can be extended to find the count of the number of instances of any fixed connected graph inside an input graph in $O(n\log{n})$ time.


texts: Algebra oriented branch of theoretical computer science

texts:
I have a very strong base in algebra, namely

commutative algebra,
homological algebra,
field theory,
category theory,

and I am currently learning algebraic geometry.

I am a math major with an inclination to switch to theoretical computer science. Keeping the above mentioned fields in mind, which field would be the most appropriate field in theoretical computer science to which to switch? That is, in which field can the theory and mathematical maturity obtained by pursuing the above fields be used to one's advantage?


texts: Are there any open problems left about DFAs?

texts:
After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don't mean generalisations of DFAs but the original unmodified DFAs we study in undergrad.

This is a vague question but I hope you get the idea. I want to understand if it is fair to say that we completely understand DFAs. So I really mean questions that are inherently about DFAs, not problems artificially made to look like a problem about DFAs. Let me give an example of such a problem. Let L be the empty language if P=NP and some fixed non-regular language if P is not NP. Can L be accepted by a DFA? This question is about DFAs, but it isn't about them in spirit. I hope my point is clear and I don't get pedantic non-answers from people.

In short is it fair to say

  We essentially completely understand DFAs.

I am sorry if it turns out that this is a huge area of research that I was not aware of and I have just insulted an entire community of people.


texts: What bounds can be put on counting reachable nodes in a dag?

texts:
Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is there reason to believe the lower bound can be improved (related: what exactly is known about lower bounds for transitive closure)?

Motivation: I had to do this a couple of times while representing fol formulas as dags.

Edit: Please note that simply doing $c_x=1+\sum_{x\to y}c_y$ counts paths, not reachable nodes. (I added this because apparently many people thought this simple solution would work by the votes I saw on a now-deleted answer.) In fact, this problem appears precisely when you want to do something interesting with 'shared' parts, nodes reachable by more than one path. Also, I say dag, because if they are solved, then solving digraphs is easy.


texts: Clauses structure as quenched random matrix for random $k$-SAT problems

texts:
In the Section III of Statistical mechanics of the random K-SAT model, the clauses structure of random $k$-SAT problems are expressed as $M \times N$ quenched random matrix where the numbers of variables and clauses are $N$ and $M$ respectively.
I would like to know when a random matrix becomes quenched. I would also like to know the implication of a random matrix not being quenched on the structure of the $k$-SAT problem.


texts: A few questions about Object-Oriented Languages in general

texts:
I was not a big fan of Object-Oriented Languages (OOL), but recently started to learn a bit more about their pros and cons in a general setting instead of diving into one such language.  I have a few questions here:

Do methods in an OOL contain free variables?  If they do, are they statically-scoped?
Do method names live in a different name space than variables?

For both questions, I have kinda guess answers but am not quite sure.  However, I would like to know more about the reasons behind and consequences of OOLs' specific answers to these questions.


texts: Underlying codes in Niederreiter cryptosystems

texts:
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.

The minimum distance $d$ is given by

$d= min\lbrace k \text{ such that there are $k$ linearly dependant columns in $H$}\rbrace$

Encryption in this case is done by encoding messages $m$ of weight less than $d/2$.

Now keeping Niederreiter systems in mind, my question is, since $m$ is over $\mathbb{F}_2$, it makes sense to consider linearly dependence over $\mathbb{F}_2$ rather than $\mathbb{F}_{2^n}$. In other words, is it okay to consider code as a code over $F_{2}$ with alphabet extension or do we  have to consider it as codes over $\mathbb{F}_{2^n}$.


texts: How to define the _regret_ in multiagent systems? Any good definition please?

texts:
I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent received up until time $t$ and the average per-period reward the agent would have received up until time $t$ had he played pure strategy $s$ instead, i.e., $\mathrm{Regret}=\alpha^t-\alpha^t(s)$.

I do not get this definition of regret. For me it looks the other way around, i.e., $\mathrm{Regret}=\alpha^t(s)-\alpha^t$. I also looked for definitions in the internet and I am really lost now.

Can you please explain to me what I am missing here? Could the authors be wrong in the definition (since it is uncorrected manuscript)?


texts: Consequences of a distillation algorithm for PSPACE

texts:
The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels".

  Let a language $L$ be given.  A distillation algorithm for $L$ takes a given
  list of input strings $\{ x_i \}_{i \in [t]}$ and computes an output string
  $y$ such that:

  (1) $y \in L$ if and only if there exists $i \in [t]$ such that $x_i \in L$

  (2) $\vert y \vert \leq p(Max_{i\in[t]} \vert x_i \vert)$ for some polynomial $p$

  (3) The algorithm computes $y$ in at most $q(\sum_{i\in[t]}\vert x_i \vert)$ time for some polynomial $q$

It has been shown that if there exists a distillation algorithm for an $NP$-complete problem, then $coNP \subseteq NP/poly$.  Moreover, $PH = \Sigma_3$.

  See details and discussion in:

  "Infeasibility of Instance Compression and Succinct PCPs for NP"
  "On Problems Without Polynomial Kernels"
  "Lower bounds on kernelization"

Questions:

Could there exist a distillation algorithm for a $PSPACE$-complete
problem?
If such an algorithm existed, what complexity consequences would we
get?


texts: Is Witten's new method of quantization useful for geometric complexity theory?

texts:
The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used to compute equivariant cohomologies might be useful to Mulmuley et al's geometric complexity theory. Edward Witten is the wellspring of these ideas and his latest paper (arXiv:1009.6032) continues to develop them. My main concern is that they might not carry across to the objects of interest to complexity theory (e.g. the "class varieties" of arXiv:cs/0612134). But the power of the quantum techniques, and the diversity of approaches possible within GCT, leads me to keep looking...

Cross-posted to Math Overflow.

Edit: I have added some details at MO. What I need next is a much better understanding of the specific unproven propositions of algebraic geometry which GCT has already flagged as important. For example, I don't yet get the relationship between, on the one hand, nonstandard quantum groups and the "plethysm problem", and on the other hand, the Valiant-inspired approach which looks at the orbit closure of permanents and determinants.


texts: Easy decision problem, hard search problem

texts:
Deciding whether a Nash equilibrium exists is easy (it always does); however, actually finding one is believed to be difficult (it is PPAD-Complete).

What are some other examples of problems where the decision version is easy but the search version is relatively difficult (compared the the decision version)?

I would be particularly interested in problems where the decision version is non-trival (unlike the case with Nash equilibrium).


texts: Lower bounds on 2-query locally decodable codes

texts: Does any one knows if there is a non-quantum proof of the fact that non-linear 2-query LDC must have exponential size?


texts: Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph

texts:
In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.

Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's sake let's say they are.  In either case, they can't move through diagonal "holes")

The problem (for this question at least) is to place up to K additional walls to maximize the path the enemies have to take, without completely blocking start from the finish.  For example, for K=14

I've determined that this is the same as the "k most vital nodes" problem:

  Given an undirected graph G = (V,E) and two nodes s,t ∈ V, the k-most-vital-nodes are the k nodes whose removal maximizes the shortest path from s to t.

Khachiyan et al1 showed that, even if the graph is unweighted and bipartite, even approximating the length of the max-shortest-path within a factor of 2 is NP-Hard (given k,s,t).

All is not lost, however:  later, L. Cai et al2 showed that, for "bipartite permutation graphs" this problem can be solved in pseudo-polynomial time using the "intersection model."

I haven't been able to find anything on unweighted grid-graphs specifically, and I can't figure how "bipartite permutation graphs" are related, if at all.  Has there been any research published relating to my problem - maybe I am looking in the completely wrong place?  Even a decent pseudo-polynomial approximation algorithm would work well.  Thanks!

1 L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf and J. Zhao "On Short Path Interdiction Problems: Total and Node-Wise Limited Interdiction," Theory of Computer Systems 43 (2008), 2004-233.  link.
2 L. Cai and J. Mark Keil, "Finding the k most vital nodes in an interval graph."  link.

Note: this question is a follow-up to my stackoverflow question found here.


texts: Is there good open source project that apply semantic web, modal logics, and similar technologies

texts:
Recently such themes as semantic web, modal logics, business rules have seen increased interest as research topics in computer science (alhough many of then have more than 80 years of history), but are there any open source projects (even better if they are actively used in commercial applications as well) that use these technologies and where one can participate and get new challenges for research?

I have found a lot of research projects (e.g. satisfiability solvers, logic programming environments) but at present I don't know many succesfull applied applications. There have been few reports on some of them in the jornal of "Theory and Practice of Logic Programming" - mostly about solving scheduling problems with logic programming methods. But maybe there is some open source projects as well?

Sometimes it seems to me that modal logics (semantic web is part of them) and logic programming gives false impression about their power and their generality has few applications, e.g. the concrete algorithms of integer programming or scheduling are more powerfull and ready for applications than general methods suggested by the former ones.


texts: (Cryptographic) problems solvable in a polynomial number of arithmetic steps

texts:
In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of arithmetic steps. This fact was restated, and thus came to my attention, in the recent paper of Borwein and Hobart [2] in the context of straight line programs (SLP).

Since I was rather surprised to read this, I have the following question: Are there any other cryptographic problems or maybe also other relevant problems, that can be solved in a polynomial number of steps with a SLP and that are currently not known to be solvable efficiently on a "normal" classical computer?

[1] Adi Shamir, Factoring Numbers in $O(\log n)$ arithmetic steps. Information Processing Letters 8 (1979) S. 28–31

[2] Peter Borwein, Joe Hobart, The Extraordinary Power of Division in Straight Line Programs,
The American Mathematical Monthly Vol. 119, No. 7 (August‒September 2012), pp. 584-592


texts:
A distribution $D$ on $\{0,1\}^n$ is $k$-wise independent if any $k$ of the underlying $n$ random variables are independent and each is uniformly distributed.
To me this looks similar in spirit to $D$ having $\textit{min-entropy}$ $k$.

Is there any formal relation between $k$-wise independence of a distribution and its min-entropy?


texts:
I'm looking forward to know about applications of Christol theorem mentioned in Jefrrey Shallit's Number theory and formal languages. One of them is purely algebraic: if $f, g \in \mathbb{F}_q[[z]]$ are algberaic then their Hadamard product $f \odot g$ is also algebraic.

Can you name other applications?


texts: What is the reason for using a "Lines-Oracle" in the PCP Theorem?

texts: I'm trying to understand the proof of the PCP Theorem in "Complexity and Approximation" by  G. Ausiello et al. and came across the low degree test which is used to check if a function $f$ given as oracle (or "auxiliary proof") is close to some degree $d$ polynomial. The test uses another "Lines-Oracle" for retrieving $d+1$ coefficients for univariate polynomials defined on lines. Then the test simply compares the univariate polynomial with respect to a random line on a random point with $f$. Why is this "Lines-Oracle" necessary? I mean one could just interpolate $f$ on a random line (with the same amount of queries) and do the same check. Is this just for convenience?


texts: Survey of transformations related to the use of SAT solvers

texts:
I am starting to investigate the possibility of relying on a SAT solver to tackle an optimisation problem I'm interested in, and am currently looking for a survey that would feature examples of "clever" transformations to variants of SAT (i.e., transformations that result in a problem of reasonable size, since I'm not interested in proving hardness results but in actually solving the problem), approximately in the spirit of what can be found in the survey on cubic graphs by Greenlaw and Petreschi, if any comparison can be made between the two.

Has such a survey eluded me because it does not exist, or because I just missed it?


texts: Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$

texts:
I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$.

Given $p$, I am looking for a good asymptotic upperbound on $\mid U\times V\mid$, the cardinality of the products, for all possible choices of $U$ and $V$.

To make it hopefully more precise :
$$\max \{\operatorname{Card} \ (U\times V) \mid \ U, V\subset \{0, 1\}^p\mbox{ such that  }\forall uv\in U\times V, D(u,v) \geq 2\}.$$


texts: Is Magic: the Gathering Turing complete?

texts:
A very specific question, I'm aware, and I doubt it will be answered by anyone that isn't already familiar with the rules of Magic. Cross-posted to Draw3Cards. Here are the comprehensive rules for the game Magic: the Gathering. See this question for a list of all Magic Cards. My question is - is the game Turing Complete?

For more details, please see the post at Draw3Cards.


texts:
Is there a complete theory T over a logical language L such that bounded computation may be encoded in it? Computational questions can be framed as arithmetical ones by interpreting them over natural numbers. Let $\phi$ be a first order statement which states that $P \neq NP$ in the language of arithmetic. Then either $\phi$ belongs to Th(N) or its negation does (i.e.) it contains the answer to the P vs NP problem.

However, since Th(N) is not RE, I would like to know if computation (in particular, bounded computation) can be interpreted over some alternate structure with nicer properties (i.e. whose theory is decidable). Note that if a theory is complete, then it cannot be RE-complete (i.e.) deciding whether any $\phi$ belongs to the theory is not RE-complete, it is either recursive or RE-hard.

The context is Razborov's paper on "Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic" in which he shows that the bounded arithmetic theory $S_2^2(\alpha)$ cannot prove polynomial circuit lower bounds for SAT assuming Strong Pseudo Random Generators (SPRGs) exist. Here the statement "SAT does not have poly size circuits" can be written as a bounded sentence when interpreted over the naturals.

I want to understand if the presence of a total order is required for the interpretation of computation inside a structure. Suppose I take graphs with the minor ordering (which is a WQO), is it possible to interpret computation inside this? My only point of reference is the undecidability of First order satisfiability by reduction from the Halting Problem. In this case, we do not seem to require a successor function, just the idea of a "future" configuration with certain properties. I understand that this setting is different from interpretation inside a structure. I want to understand this difference.


texts: Can a two counters machine decide $n^2$?

texts:
Can a standard two counters ($c_1,c_2$) machine with the following instructions:

1) ADD 1 to c_i, GOTO label_j
2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k
3) GOTO label_j
4) HALT and ACCEPT|REJECT

decide the following language:

$$L = \{ n^2 \mid n \geq 1 \}$$

(the input is initially loaded in the counter $c_1$)?.

Is it still an open problem? (cf. Rich Schroeppel, "A Two counter Machine Cannot Calculate $2^N$" [1972])


texts: Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

texts:
I'm following course material from the course Advanced Data Structures.

The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which cites the original paper "Making data structures persistent")

  Any pointer-machine data structure with O(1) pointers to any node can be made partially persistent with O(1) ammortized multiplicative overhead and O(1) space per change

I understand the argument for why reads are O(1). The key idea is that during a write to n when a new node n' is created due to mod table overflow, we guarantee existence of a mod entry pointing to n' in any node x which has a field pointing to n.

During a read, you can look at appropriate mod entry in x which will point to either n or n' depending on the version, so you only have to look at O(mod table size) entries at every read.

So in summary, the backpointer update guarantees efficient reads.

However, in my program I start out with a pointer to the head of the linked list in a variable. With backpointer updates, it'll always point to the latest version. Which means that if I have to look up an older version of the list, I'll have to go through all mod tables of the first node of the linked list till I arrive at the correct version, making it O(n) in number of versions and not O(1). Is that correct?


texts:
What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing?

For example: In the draft version of Arora & Barak's book, it is mentioned that:
Frontier 2.1: Exhibit a language in NEXP that is not in ACC0 (6)
This was solved by Williams soon after that.


texts: Is statistical query learning equivalent to correlational statistical query learning given a fixed distribution?

texts: As title, I saw some paper mentioned they are equivalent, but I'd wonder how to prove they are? is it something to do with PAC as SQ is a restricted version of PAC?


texts: Maximum Independent Set using Maximal MIS

texts:
I want to use multiple runs of maximal independent set (Luby's algorithm) to find a lower bound on the size of maximum independent set.

Are there any bounds on the number of times the maximal algorithm has to be run to find the true maximum with a high probability ?

The graphs don't possess any special properties.


texts: Complexity of equivalence testing of arithmetic circuits

texts:
I have a very specific problem that appears to be close to equivalence testing for arithmetic circuits (checking whether the computed functions are the same).

Since I'm completely new to the field, I'm asking for some references, hopefully as close as possible to my concrete problem.

I want to find out the complexity of comparing two arithmetic circuits (directed graphs with addition and multiplication nodes). My concrete problem has the following particularities.

There is only one input variable. Thus the circuits encode a function $\mathbb{N} \to \mathbb{N}$. Are there any results about a constant number of input variables?
There might appear leafs of the form $c^n$ with $n$ being the input variable and $c \in \mathbb{N}$ some constant.

I'm happy with both surveys or original works about such equivalence problems. Books are also ok, but I prefer material that's downloadable.


texts: Is Combinatory Logic (CL) still relevant for programming language theory?

texts:
I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of combinators and followed up with some Curry. "After" reading Hindley I can say that I "get" CL to some extent (and perhaps is the reason for this question).

However, CL seems to be presented in the language of $\lambda$-calculus. This seems to have been a general progression AFAIK where $\lambda$ superseded CL and the latter seems to have fallen off to the wayside.

My understanding is that although one can "define" a combinator like so in CL, the only way to "implement" it is via $\lambda$? Is this a valid inference? A satisfactory mathematical definition of a combinator may not be possible and thus it's described in the language of $\lambda$ and thus it's not relevant by itself per se.

The "concept" of combinators may still be useful (although I can't yet say how/where) for gaining some insight owing to it being "variable free" but for the most part it seems irrelevant as of today (2019-20). Almost everything in CL can be translated to $\lambda$ and vice versa. So is there any "insight" to be gained by studying CL? Is it now just a "simpler alternative" than $\lambda$ when trying to understand something that could get messy when analyzing with $\lambda$? Or is there more to it than meets the eye?

Is my understanding/assumption correct? What are the other reasons for it to not be "mainstream PLT" (or is that just my POV)?


texts: Is there an alternate proof or an exposition of: Exponential lower bound for $\Sigma\Pi\Sigma$ circuits [Grigoriev-Karpinski(1998)]?

texts:
Is there an alternate proof or an exposition of the result of Grigoriev and Karpinski (STOC 1998, doi:10.1145/276698.276872) on the exponential lower bounds for Depth 3 arithmetic circuits computing $\mathsf{DET}_{n\times n}$ over a fixed finite field?

I could not understand section 2 of the paper. What is the intuition behind considering the F-linear operator $T_g$?


texts: List of complexity classes closed under complement

texts: Is there a list of 'natural' complexity classes closed under complement? Some that I could think of are P, ZPP, BPP, NP $\cap$ co-NP, PH, PP and PSPACE but surely there are others. Wikipedia and the Complexity-Zoo don't have such a list as far as I can tell but perhaps there are other resources?


texts: Applications of Barendregt–Geuvers–Klop conjecture

texts:
I was learning about type systems from Benjamin C. Pierce's Types and Programming Languages and came across the Lambda cube in the chapter on Higher-Order Polymorphism. After reading up more about it on Wikipedia I learnt about its generalization, Pure type system where it is mentioned that

  It is a major open problem in the field whether this is always the case, i.e. whether a (weakly) normalizing PTS always has the strong normalization property.This is known as the Barendregt–Geuvers–Klop conjecture.

However, I am unable to think of practical applications of a proof (or disproof) of the above conjecture (perhaps due to my limited knowledge of type theory).

Question: What are the practical applications of a proof (or disproof) of the Barendregt–Geuvers–Klop conjecture?

Update
I found a paper that proves that Weak normalization implies strong normalization in a class
of non-dependent pure type systems, however it says nothing about applications


texts: Is that edge orientation optimization problem NP-hard?

texts:
Is the following optimization problem NP-hard?

Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{out}(u) \right)^2$, where $d_{out}$ is the number of out-neighbors.

Motivation: The problem is related to listing triangles in graphs. A motivation can be found here where the optimization problem is similar, but where the edge orientation needs to induce a DAG.
One can observe that the DAG constraint is not necessary: the actual constraint in order to have a correct algorithm (i.e. an algorithm that will list all triangles) is that the edge orientation should not induce a cycle of length 3.
I think that the constraint "no induced cycle of length 3" is too complicated and decided to formulate the above problem as a stepping stone.
Another formulation: The problem can be written as the following Integer Quadratic Programming.
\begin{align}
 \text{Minimize} &\qquad \sum_{u\in V} (y_u)^2 &\qquad  (IQP)\\
 \text{s.t.} &\qquad \forall u \in V, \forall v \in N_u, x_{u,v}  \in \{0,1\}  \\
 &\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &\qquad \forall u \in V, y_u=\sum_{v \in N_u} x_{u,v}\\
\end{align}
with $N_u$ the set of neighbors of node $u$ in the input undirected graph.
Is (IQP) NP-hard?
It can be relaxed into the following Quadratic Programming:
\begin{align}
 \text{Minimize} &\qquad \sum_{u\in V} (y_u)^2 &\qquad  (QP)\\
 \text{s.t.} &\qquad \forall u \in V, \forall v \in N_u, x_{u,v}  \in [0,1]  \\
 &\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &\qquad \forall u \in V, y_u=\sum_{v \in N_u} x_{u,v}\\
\end{align}
for which an optimal solution can be obtained in polynomial time using a quadratic programming solver as the objective is convex. Can an exact or approximate solution to (IQP) be obtained out of the (QP) solution? Using randomized rounding maybe?
The greedy algorithm is not optimal: The algorithm "fix some orientation then repeatedly flip the orientation of an edge that decrease the score" is not optimal. The following is a counter example found by alt-tab.


texts: Formal definition of Turing Completeness

texts:
Wikipedia states:

  In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine

However, my question is about the formal definition of Turing completeness. I've searched around, but never really found any good definitions of what is a _"a system of data manipulatio rules", or even "simulation".

I suspect that one way to define such notions is to use dynamical systems (maybe creating an equivalence relation on the state-space for representing the states of a Turing machine or equivalent system). On the other side, I know that logic has connections to the theory of automatas. Can logic be viewed as a dynamical system? Does that make sense? For which mathematical structures does it make sense to ask about turing completeness or even computability? Does it have to be a dynamical system?

Anyway, given those considerations, my question is "what is the formal definition of Turing completeness?"


texts: Winning strategy in the game of triplets

texts:
The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements.
Two players take turns picking elements from $X$ until all elements are taken. Then, the score of each player is the number of triplets from $T$ in which he has at least 2 elements.

A standard strategy-stealing argument shows that the first player can always score at least $|T|/2$. Suppose by contradiction that it is false. Then the second player can score more than $|T|/2$. But then the first player, copying the second player's winning strategy, can score more than $|T|/2$ too. This is a contradiction since the sum of scores is $|T|$.

  QUESTION: what is an explicit strategy for the first player to get a score of at least $|T|/2$?

EDIT: Here is an explicit strategy for the first player to get at least $3|T|/8$. To each triplet in $T$, assign a potential $P(a,b)$ based on the number of its elements taken by the (first,second) player:

\begin{matrix}
\bf a \downarrow b \rightarrow & \bf 0 & \bf 1 & \bf 2 & \bf 3 \\
\bf 0    &3/8&0& 0 & 0 \\
\bf 1    &3/4&1/2& 0 &   \\
\bf 2    & 1 & 1 &   &   \\
\bf 3    & 1 &   &   &   \\
\end{matrix}
Initially, every triplet has potential $3/8$, so the potential-sum is $3|T|/8$.

Player 1's strategy is: pick an element that maximizes the potential-sum.
Suppose that element is $x$ and the element picked next by player 2 is $y$. I claim that the potential-sum after these two moves weakly increases:

The potential of a triplet that contains neither $x$ nor $y$ does not change.
The potential of a triplet that contains both $x$ and $y$ changes from $P(a,b)$ to $P(a+1,b+1)$, which is always at least as large.
The potential of a triplet that contains $x$ and not $y$ increases by $P(a+1,b)-P(a,b)$;
The potential of a triplet that contains $y$ and not $x$ decreases by $P(a,b)-P(a,b+1)$; it is easy to check in the table that $P(a,b)-P(a,b+1)\leq P(a+1,b)-P(a,b)$ (the decrease when going right is at most the increase when going down).

All in all, the potential-sum increases by the sum of $P(a+1,b)-P(a,b)$ over all triplets that contain $x$, and decreases by (at most) the sum of $P(a+1,b)-P(a,b)$ over all triplets that contain $y$. By the choice of $x$, the first sum is weakly larger. So the potential-sum weakly increases.

So the final potential-sum is at least $3|T|/8$. At the end, a triplet has potential $1$ ($0$) iff it is won by player 1 (2), so the final potential-sum equals player 1's score.


texts: Minimum spanning tree over all vertex matchings

texts:
I ran into this matching problem for which I am unable to write down a polynomial time algorithm.

Let $P, Q$ be complete weighted graphs with vertex sets $P_V$ and $Q_V$, respectively, where $|P_V| = |Q_V|=n$. Also, let $w_P$ and $w_Q$ be the weight functions on the edges of $P$ and $Q$, respectively.

For a bijection $f: P_V \to Q_V$ we modify $Q$ in the following fashion: If $f(p) = q$ and $f(p^\prime) = q^\prime$ with $w_P(p, p^\prime) > w_Q(q, q^\prime)$ then set $w_Q(q, q^\prime) = w_P(p, p^\prime)$. Denote this modified graph by $Q_f$ and let $W(Q_f)$ be the sum of weights of the minimum spanning tree of $Q_f$.

Problem: Minimize $W(Q_f)$ over all bijections $f: P_V \to Q_V$.

How hard is this problem? If "hard": what about approximation algorithms?


texts: Why is Proof Checker required in Proof Carrying Code

texts:
In the classical PLDI'98 paper by Necula, "The design and implementation of a certifying compiler", the high-level verifier uses:

VCGen to generate verification conditions (safety predicates)
First-order logic theorem prover to prove the conditions
LF proof checker to check the proof from step (2)

I am a bit confused by step (3). Why is it required at all? Will just (1) and (2) not suffice? Why don't we just trust the proof generated by a theorem prover?


texts: Lower bound for finding repeated elements in sorted array

texts:
This is inspired by [1] (which still needs answers).

  What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, how to determine whether there exists some element which occurs more than $\lfloor n/k \rfloor$ times?

Note 1: The original problem [1] focuses on $k=2$, i.e., the "majority detection" problem. There is a simple $\Theta(\log n)$ algorithm for it: Only the median, called $m$, can be the majority. We can learn the length of the $m$ contiguous block using binary search.

  However, is $\Omega(\log n)$ a lower bound for $k = 2$?

Note 2: For unsorted array, [2] gives an optimal $O(n \log k)$ algorithm. The lower bound is proved using the decision-tree technique (section 5). I failed to extend it to the sorted case.

[1] Lower bound of finding majority element in an ordered array. @ cs.exchange

[2] Finding Repeated Elements by J. Misra and David Gries, TR, 1982.


texts: Type inference for imperative statements other than assignment

texts:
In my search for research papers about type systems for imperative languages, I only find solutions for a language with mutable references but without genuine imperative control structures such as compound operators, loops or conditionals.

So it's not clear how an imperative language with partial type inference such as http://rust-lang.org can be implemented.

The papers don't mention parametrized types such as List of a because parametrized types are a trivial extension of Hindley-Milner type system - only the unification algorithm should be extended, and the rest of inference works as is. However, assignments cannot be trivially added because paradoxes arise, so special techniques such as ML value restriction must be applied.

Can you recommend any papers or books describing a type system for a language with imperative loops, conditionals, IO and compound statements?


texts: How does one extend local checkability to quantum complexity classes?

texts: How does one extend local checkability to quantum complexity classes like BQP? Or are quantum algortihms inherently holistic?


texts: Select two numbers that sum to $p$, using sub-linear query time

texts:
Here is a nearest neighbor problem.

Given reals $a_1, \ldots, a_n$ (very large $n$!), plus target real $p$, find $a_i$ and $a_j$ whose SUM is closest to $p$. We allow reasonable pre-processing/indexing of $a_1, \ldots, a_n$ (up to $O(n \log n)$), but at query time (given $p$), the result should be returned very fast (e.g., $O(\log n)$ time).

(Simpler example: if we only wanted the SINGLE $a_i$ that is closest to $p$, we would sort $a_1, \ldots, a_n$ offline, $O(n \log n)$, then do binary search at query time, $O(\log n)$).

Solutions that don't work:

1) Sort $a_1, \ldots, a_n$ offline, then at query time, start from both ends & move two pointers inward (http://bit.ly/1eKHHDy). Not good, because of $O(n)$ query time.

2) Sort $a_1, \ldots, a_n$ offline, then at query time, take each $a_i$ and perform binary search for a "buddy" that helps it sum to something close to $p$. Not good, because of $O(n \log n)$ query time.

3) Sort all pairs $(a_{1}, \ldots, a_{n})$ offline, then do binary search. Not good, because of $O(n^2)$ pre-processing.

Thanks!

ps. Further generalizations needed for practice: (1) $a_1, \ldots, a_n$ and $p$ to be 50-dimensional vectors, (2) "close" to be vector cosine distance, and (3) $k$-best closest pairs-that-sum, not just 1-best.


texts:
Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$?

At least one $\frac n2\times\frac n2$ minor non-vanish implies rank $\geq\frac n2$. However does all $\frac n2\times\frac n2$ minor non-vanish have a short certificate? I think it might be the case and perhaps there is a convex way to detect this.


texts: Bounding the number of edges between star graphs such that graph is planar

texts:
I have a graph $G$ which consists only of star graphs. A star graph consists of one central node having edges to every other node in it. Let $H_1, H_2, \ldots, H_n$ be different star graphs of different sizes which are present in $G$. We call the set of all nodes which are centres in any star graph $R$.

Now suppose these star graphs are building edges to other star graphs such that no edge is incident between any nodes in $R$. Then, how many edges exist at maximum between the nodes in $R$ and the nodes which are not in $R$, if the graph should remain planar?

I want the upper bound on the number of such edges. One upper bound that I have in mind is: consider them as bipartite planar graph where $R$ is one set of vertices and rest of the vertices form another set $A$. We are interested in edges between these sets ($R$ and $A$). Since it is planar bipartite, the number of such edges is bounded by twice the number of nodes in $G$.

What I feel is that is there a better bound, maybe twice the nodes in $A$ plus the number of nodes in $R$.

In case you can disprove my intuition, then that would also be good. Hopefully some of you can come up with a good bound along with some relevant arguments.


texts: Term that can distinguish beta-equivalent normal forms in the untyped lambda calculus

texts:
I'm trying to work through two (non-assessed) class-work questions and am stuck on a question that seems similar to one I could do.

The first question was to prove that there does not exist a $\lambda$-term $f$ that, given two $\lambda$-terms $m$ and $n$, can determine whether or not they are $\beta$-equivalent — i.e. there is no $f$ such that $\lambda\beta \vdash f \ m \ n = \textbf{t}$ if $m \ =_\beta \ n$ and $\lambda\beta \vdash f \ m \ n = \textbf{f}$ if $m \ \neq_\beta \ n$. I think I have done this relatively easily by appealing to the Scott-Curry theorem.

I'm now stuck on proving the same but for $m, n$ being in normal form. If I try to use the Scott-Curry theorem, showing that the set $A = \{ x = m \mid x \mbox{ in normal form} \}$ is inseparable, so that no $g \equiv f \ m$ can exist, then I cannot show that $A$ is closed under $\beta$-equality, which we require to apply the Scott-Curry theorem. So I don't think this is the correct approach.

Could anyone give me some help on how to formally prove this? I've played around with contexts, Böhm's theorem, etc. I feel like the fact $m, n$ are not required to be closed is important?


texts: Why is it necessary to maintain a collection of forests in the dynamic graph data structure?

texts:
In their paper "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity", Holm, de Lichtenberg, and Thorup describe a data structure for maintaining dynamic connectivity in undirected graphs. Their data structure maintains a collection of forests $F_0, F_1, F_2, ..., F_{\log_2 n}$ made of forests of edges of different levels. In the paper, the authors say that the forests should be represented by having an Euler tour tree data structure for each level. Each tree is augmented with information about the number of edges in the tree, the number of edges of each level in the tree, which subtrees contain nodes adjacent to edges of the given level, and which subtrees contain edges of the given level.

It seems like it should be possible to maintain all this information in a single Euler tour tree by augmenting each node in the tree with $\log_2 n$ copies of the above information, one for each level. This would simplify the presentation of the data structure without requiring redundant copies of each edge.

Does this modification work correctly? Or is there a reason to maintain a separate copy of the forests at each level?

Thanks!


texts:
The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth.
The $\textrm{NC}$-hierarchy is the union of those classes.

Is there any study of the linear-size variant of this hierarchy? That is circuits families of bounded fan-in, polylog depth and linear size?

I know their exists some work with linear-$\textrm{AC}^0$ but nothing else. Remark that at least linear-$\textrm{NC}^1$ is nontrivial since it contains regular languages (and thus some $\textrm{NC}^1$-complete languages).


texts: Proving greedy algorithm is optimal for a scheduling problem

texts:
First, the problem discription:

For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of length $0$ such that in the end all the tasks are put in the queues and both queues has length $2n$. Let $cost$ be 0 at first. For each task $a_i$ that has value $1$, we add its index in the queue to the $cost$.
The objective is to minimize the $cost$.

Example, the sequence of tasks is $10101010$, and we put the $1$th task in queue $1$, the $2$th task in queue $1$, the $3$th task in queue $2$, the $4$th task in queue $1$, the $5$th task in queue $2$, the $6$th task in queue $1$, $7$th task in queue $2$, the $8$th task in queue $2$, then queue $1$ will has task sequence $1000$ and queue $2$ will has task sequence $1110$, so the $cost$ is $(1)+(1+2+3)=7$.

Then we describe the greedy algorithm with parameter $0\le k\le 2n$：

It first puts the first $k$ tasks sequentially to the end of queue $1$. Then for $i=k+1,\dots$, if $a_i=1$ it puts the $i$th task into a queue with smaller length, else it puts the $i$th task into a queue with bigger length until one of the queues is full(it has length $2n$). Finally it puts the rest of tasks sequentially to the end of the non-full queue.

The question is proving the best greedy algorithm(over choices of $k$) gives the optimal cost for any $4n$ length sequence. I have many simulation results that support this statement and haven't found a proof yet.


texts: Why is label pruning possible with hub labeling?

texts:
Hub labeling (HL) computes superlabels using the vertices visited by the forward and reverse Contraction Hierarchies (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict labels.

I don't understand how there can be labels that can be pruned. From my understanding the shortcuts added by CH should make sure that in both forward and reverse searches we will either

reach a node via a shortest path or
not reach a node at all.

How is it possible that we reach some nodes via a path that is longer than the shortest path? Could anyone provide a minimal example?


texts: Trying understand a move in Cohen's proof of the independence of the continuum hypothesis

texts:
I've read a few different presentations of Cohen's proof. All of them (that I've seen) eventually make a move where a Cartesian product (call it CP) between the (M-form of) $\aleph_2$ and $\aleph_0$ into {1, 0} is imagined. From what I gather, whether $CP \in M$ is what determines whether $\neg$CH holds in M or not such that if $CP \in M$ then $\neg$CH.

Anyway, my question is: Why does this product, CP, play this role? How does it show us that $\aleph_2 \in M$ (the 'relativized' form of $\aleph_2$, not the $\aleph_2 \in V$)? Could not some other set-theoretical object play the same role?


texts: Mildly dependently-typed metalanguage for mildly context-sensitive object languages

texts:
This is almost certainly not a new idea, but I haven't seen it elaborated or discussed elsewhere. A very natural way to represent the abstract syntax of an object language in a typeful metalanguage is to define:

A metalanguage equality type for every nonterminal in the object language's grammar.
A metalanguage constructor for every production rule in the object language's grammar.

There is a direct and obvious correspondence between the expressive power of the metalanguage's type system and the classes of syntactic structures that can be represented accurately in it. For example:

Algebraic data types (possibly recursive finite sums of finite products, as in ML, but without function types or reference cells) represent exactly the class of context-free grammars.
Inductive type families can represent unrestricted grammars.

In formal language theory, there exist several classes strictly between context-free and unrestricted grammars. For example, in increasing order of expressive power:

Tree-adjoining grammars
Linear context-free rewriting systems
Indexed grammars

So my questions are:

For every one of these classes, what kind of type system allows us to describe exactly the grammars that belong to it, and no others? For indexed grammars, I suspect the answer is something like “GADTs parameterized by SML-like eqtypes promoted to GHC-like DataKinds”, but what about the others?
In computational linguistics, there has been research on “mildly context-sensitive grammars”, which (in theory) describe the context-sensitivity of natural languages, without running into the tractability issues of general context-sensitive (never mind unrestricted) grammars. In type theory, would it be equally viable to study “mildly dependently typed languages”, with the goal to describe the invariants that appear in real-world programs, without running into the usability issues of full-blown dependently typed languages? To what extent can we reuse the results already obtained by the formal languages and automata theory communities, in the design of type checkers for mildly dependently typed languages?


texts:
Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I mean not relying on the probabilistic method like Valiant 84 did or on sorting networks; preferably providing an explicit, straightforward construction of the circuit):

$f$ can be computed by a family of circuits of $O(\log(n))$ depth, poly(n) size, where the gates consists of NOT gates, 2-input OR gates, and 2-input AND gates.


texts: On partitioning a collection into equivalence classes

texts:
Suppose I have a collection $A$ that I want to partition into equivalence classes, according to some equivalence predicate $E$.

The naive algorithm for doing this is essentially recursive.  It consists of picking an arbitrary item $x$ of $A$, using it to "seed" its equivalence class $[x]$, and filling $[x]$ out by iterating over the remaining items $y$ of $A$, adding $y$ to $[x]$ iff $E(x, y)$ is true.  Then this base procedure is repeated recursively on the subcollection $A^\prime$ of $A$ consisting of all the items of $A$ that were not assigned to $[x]$.

I would like to know

the technical name for this generic problem; and
whether it is possible to do better performance-wise than the naive algorithm described above.


texts: Approximation algorithms used in exact algorithms

texts:
Approximation algorithms might give output up to some constant factor. This is a bit less satisfying than exact algorithms.

However, constant factors are ignored in time complexity.

So I wonder if the following trick is possible or was used, to solve some problem $B \circ A$:

Use an approximation algorithm solving problem $A$ to get solution $S$ within constant factor;
Use an exact algorithm, solving problem $B$, whose runtime depends on weight of $S$ but works as long as $S$ is a correct solution.

This way the approximation is a "subprocedure" of an exact algorithm, and the constant factor lost in step 1 is swallowed in step 2.


texts: Standard reference for efficient computation of non-intersecting Eulerian circuit

texts:
A plane graph $G$ defines a cyclic ordering $O(v) = \langle v_1, v_2, \dotsc, n_{\deg(v)}\rangle$ on the neighborhood $N(v)$ of each vertex $v \in V(G)$. A non-intersecting Eulerian circuit $C$ is an Eulerian circuit such that for every vertex $v \in V(G)$ and every choice of four edges $\{a,v\}, \{b,v\}, \{c,v\}, \{d,v\} \in E(G)$ containing $v$, if the cyclic ordering $O(v)$ restricted to $\{a,b,c,d\}$ is $\langle a,b,c,d \rangle$ and $\{a,c\} \in C$, then $\{b,d\} \not\in C$.

I have found several references that claim or prove that every plane Eulerian graph contains a non-intersecting Eulerian circuit and at least one reference that shows how to find one in polynomial time.

  Is there a standard reference (preferably a book on graph theory) that shows how to compute a non-intersecting Eulerian circuit in a plane Eulerian graph in polynomial time?


texts:
I've read snippets here and there that inside intuitionistic logic, uncountable can be a subset of the naturals ?

What is the correct intuition to think about this? Andrej Bauer replied above, saying that:

Given any sequence alleged enumeration e : Integer -> (Integer -> Bool), e will miss the sequence contra i = not (e i i). Hence, we cannot enumerate the type in Haskell.

I understand this argument, and yet, I am uncomfortable with it. I'm not sure when to think "inside the model" versus "outside the model". This seems to imply that things inside the model can believe as absurd facts as they want, perhaps something even like powerset(X) = X? How should one think about the difference between what happens 'inside' and 'outside'?

I have been picking up fragmentary references to the weirdness of intuitionistic logic (relative to, say, ZFC) here and there. I'm unaware of a textbook that lays out these results in an orderly fashion. Can I please have a textbook recommendation?


texts: What is the status of Vladimir Romanov's proof that P=NP?

texts:
A couple of months ago there was a minor hubbub about a paper published on ArXiV by V. F. Romanov titled Non-Orthodox Combinatorial Models Based on Discordant Structures which claimed to give a polynomial-time algorithm for 3-SAT, thus proving that $P=NP$. He even went as far as posting a reference implementation of the algorithm publicly.

However, as is usually the case with these things, the public attention didn't last long enough for me to hear of any resolution to this claim. I assume this means it wasn't successful, obviously, so does anybody know what the problem with this paper ended up being?


texts: What's the definition of join on iso-recursive types?

texts:
In languages with subtyping, there is often a "join" operation defined to compute the least upper bound of two types. It's used in type-checking, for example to find the smallest type that covers both the "then" and "else" branches of an if-statement.

What should the definition of join be for iso-recursive types such as $\mu X.\tau$? I started to write it myself, but realized it gets a little tricky if the recursion in each type is unrolled to a different depth.

If there's a standard reference for this, even better. Benjamin Pierce's "Types and Programming Languages" lists the necessary subtype rules near the end of chapter 21, but doesn't define the join rules.


texts: Analysis of the synergy of two algorithms in comparison to their simulation in parallel

texts:
Consider the following two algorithms for searching in a sorted array of $n$ elements:

A) interpolation search and binary search simulated in parallel, and

B) search through alternating interpolation steps and binary steps.

Both algorithms are of worst case complexity $2\lg n+1$ (and average complexity $2\lg\lg n$ for a reasonable distribution). Is there a complexity model which permits to separate those two algorithm (expressing when one is better than the other)? In particular, is there an example where the simulation in parallel is outperforming the mixed search algorithm?

---Some Basic Background---

1) Interpolation for element $x$ in a sorted array $T$ between position $i$ and $j$ makes a comparison at position $g=i+(j-i)/(T[j]-T[i])*(x-T[i])$, and reduces the search interval to $[i,g]$ or $]g,j]$ according to the result (as opposed to binary search, which compares $x$ to the element at position $(i+j)/2$.)

2) The worst case complexity of the search algorithm simulating in parallel binary search and interpolation search is $2\lg n+1$: Given two algorithms $A$ and $B$ of worst case complexities $f(n)$ and $g(n)$, the worst case of the parallel simulation of $A$ and $B$, stopping as soon as one terminates, has complexity $2\min\{f(n),g(n)\}\in O(\min{f(n),g(n)})$. The complexity of the search alternating steps from binary search and interpolation search is $2\lg n+1$ as well, because the search interval is at least reduced by two every two comparison.


texts:
I recently read that the following problem is NP-Complete:

Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?

The reference provide was to the textbook “Computers and Intractability: A Guide to the Theory of NP-Completeness”, which I don’t own. I was wondering what is the best known algorithm for this problem, and if there are any families of forests which have polynomial algorithms. (Polynomial in terms of the number of nodes in $T$) It is known that if $F$ is a tree, there is a polynomial algorithm.

Obviously, if the family has a bounded number of components, at most $C$, then there exists a polynomial solution, as there are then there are polynomially many ways we can remove $C-1$ edges from $T$, then for each component $t$ of $T$ we tabulate which components of $F$ are subtrees of $t$, and then we can check for a list coloring of a complete graph where $L(t)$ is the subtrees of $t$ in $F$. (since we can list color a complete graph in polynomial time)

Meanwhile, if $F$ is a forest whose components must all be a copies of some fixed tree $t$, then we can reduce the problem to fitting the most copies of $t$ into rooted trees of depth $diam(t)$. (with some extra complication concerning the remaining component containing the root) I believe when $t$ is a path graph, this is not too difficult to handle.

However, when my attention to the components of $F$ being arbitrary path graphs, I feel quite stumped. Is there a clever solution to this one?

Edit 1: on second thought, one should be able to make a reduction to 3-partitioning for this family of forests, so I guess it’s strongly NP-Complete.


texts: Faster pseudo-polynomial time algorithm for subset-sum?

texts:
Let $S(X) = \{\sum_{i\in Y} i  | Y\subset X \}$, the set of subset sums of $X$. $S_n(X) = S(X)\cap \{1,\ldots,n\}$. Consider the following variant of subset sum.

  ALL-SUBSET-SUMS
  INPUT: positive integer $n$ and set $X\subset \{1,\ldots,n\}$.
  OUTPUT: $S_n(X)$

There is the common dynamic programming algorithm taught in algorithm classes, which takes $O(n |X|)$ time. It takes $O(n^2)$ time for large input sets. It's not hard to devise and output sensitive version that takes $O(|X||S_n(X)|+n)$ time.

It's possible to solve it in $O((n \log n)^\frac{3}{2})$ time by decompose the problem to $\sqrt{n\log n}$ ALL-SUBSET-SUMS with small output size, and we can combine the solutions through FFT.

How fast can we solve this problem? There are subset sum algorithms using analytical number theory[1], but they have many technical conditions on the input. It can't be applied directly on ALL-SUBSET-SUMS.

Reference:

[1] M. Chaimovich , G. Freiman , Z. Galil, Solving dense subset-sum problems by using analytical number theory, Journal of Complexity, v.5 n.3, p.271-282, Sept. 1989


texts: Binary matrix column subset selection complexity

texts:
Given an $m \times n$ matrix ($m$ rows) containing only $0$'s and $1$'s, what is the complexity of finding an $m \times k$ submatrix (of $k$ columns) such that within the chosen submatrix there is no row containing only zeroes, in other words, every row contains at least one $1$?

For example, given the $4 \times 3$ matrix

$\begin{bmatrix} 1 & 0 & 0 & 1 \\
                 0 & 1 & 1 & 0 \\
                 0 & 0 & 0 & 1 \\
                 1 & 1 & 0 & 1 \end{bmatrix}$

a subset of $k=3$ columns that fails to fulfill this condition is that of the first columns, as the third row has all zeros within this submatrix, but the column set $\{1, 3, 4\}$ would be a solution.

I suspect this is a hard problem, but I haven't been able to find a direct reference. I'm interested in this problem because of its applications in cryptography.


texts: Normally model checking with specifications written in CTL*/CTL  is done over Kripke structures, however there are ways of doing it over somehow simpler Labelled Transition Systems, for instance ACTL. Does anyone has any pointer on similar logics/techniques?


texts:
I'm looking for references (books, papers, lecture notes etc) on generalization bounds and their proofs. Specifically, I'm looking to fully understand the technique of defining a hypothesis class (or distribution) and using a concentration inequality to obtain a generalization bound.

What are the standard references for such techniques?


texts: Persistent data structures in RAM computational model

texts: Always when I read about any efficient persistent data structures they use pointer computational model. I'm wondering if you know any efficient implementation which uses power of RAM model?


texts:
Where I can find reference and documents on the work made for proving whether DLBA are equal NLBA nr not?
What is the underlying problem? Why it is still an open question in TCS?


texts: Information theory and convex optimization

texts:
I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full machinery of relaxation theory, duality, etc. This is understandable since you don't want to require a full semester of convex optimization in order to teach this stuff. But as someone fairly well-versed in optimization, I feel like I'm missing out on a lot of elegance and intuition when these links aren't explored more. I often notice proofs that would be way shorter if you had utilized convex analysis as well.

Are there books that cover information theory more from this perspective? We're mostly using lecture notes from Stefan Moser, Y. Polyanskiy and Y. Wu, as well as Network Information Theory by El Gamal.


texts: Is there an online algorithm for solving any P-complete problem?

texts:
We can think of the class $NC$ as the class of problems that can be solved in parallel, whereas a $P$-complete problem probably has no parallel solution.  My question is: where do online algorithms fit in this spectrum?

My intuition says that online problems are more difficult than parallel problems.  This would be more-or-less confirmed by the existence of an online algorithm for a $P$-complete problem.  So do any exist?

Alternatively, we could define a complexity class for online problems $O$ such that:
$$
NC \subseteq O \subseteq P
$$
Then we would have to define $O$-complete problems and convince ourselves that they cannot be parallelized.

Any advice on what I should read to think about this some more?


texts:
My apologies if the question is a tad vague—I did try to search the literature for more, but didn't find anything (the similarity between the keywords "Takens" and "taken" on Google may be partly to blame).

If I understood correctly the Wikipedia page on Takens' theorem, and some discussions I had with people in applied (physics-related) fields that mentioned it to me, Taken's theorem essentially states that

  if one has a system parameterized by a state (time-dependent) $x(t)\in\mathbb{R}^d$, then under some natural assumptions on $x$ (in particular, smooth enough) there exists $k$—related to the underlying dimension of the manifold on which $x$ "lives— and some "lag" $\tau$ such that
  $$
y(t) \stackrel{\rm def}{=} (x_1(t), x_1(t+\tau),\dots,x_1(t+(k-1) \tau)\in\mathbb{R}^k
$$
  is information-theoretically equivalent to the original parameterization $x$; and moreover, this new parameterization, now living in a "shadow manifold," preserves the topology of the original manifold.

(All imprecisions above definitely mine, I cannot claim I fully understand the theorem.)

This does strike me as a very useful tool, similar in spirit to some type of dimension reduction:

bringing in domain-specific knowledge (to figure out $\tau$ and $k$, although apparently there have been recently methods designed to find these in a more automated way)
allowing easy measuring (no need to perform a computationally heavy mapping for the change of parameters: instead, focusing in a single lagged coordinate of the data is enough)

My question is: has this theorem, or some version of it, been applied or explored in the context of computational learning? If so, where can I find references of it? If not, is there a reason why—e.g., "it does not apply in the usual settings we consider because [...]"?


texts: Fast algorithm to find pair of triangles with a common edge in a complete graph

texts:
Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value $energy$ that is the multiplication of its edge weights. The question is to first find pair of triangles that have a common edge, and then draw the energy-energy scatter plot for these pairs.

For example, take this adjacency matrix:
$$ \begin{bmatrix} 0 & 1 & 2 & 3 \\ 1 & 0 & 4 & 5 \\ 2 & 4 & 0 & 6 \\ 3 & 5 & 6 & 0 \\\end{bmatrix}$$
For this graph we have 6 pair of triangles with a common edge:

$1: (1,2,3) \space with \space (1,2,4) $, (with $(1-2)$ as the common edge)

$2: (1,2,3) \space with \space (1,3,4) $, (with $(1-3)$ as the common edge)

$3: (1,2,4) \space with \space (1,3,4) $, (with $(1-4)$ as the common edge)

$4: (1,2,3) \space with \space (2,3,4) $, (with $(2-3)$ as the common edge)

$5: (1,3,4) \space with \space (2,3,4) $, (with $(2-4)$ as the common edge)

$6: (1,2,4) \space with \space (2,4,3) $, (with $(3-4)$ as the common edge)

Now it's quite easy to draw the energy-energy plot for these pairs. For each pair from 1 to 6, on the x axes we take the energy value of the first triangle in the pair, and on the y axes we put the energy value of the second triangle in the pair. So we will have a plot with 6 points, for each point $ (x,y) $,  $x $ is the energy value of the first triangle in the pair, and $y$ is the energy value of the second triangle in the pair.

I'm fine with solving this problem when the number of nodes is quite small. But I need to run this algorithm on a graph with 116 nodes. So I need to find an efficient algorithm. I'm using MatLab and I appreciate any optimize algorithm for this problem.

Thank you so much!


texts: Defining a calculation-reversing function in the lambda calculus

texts:
Obviously, lambda calculus functions are not in general invertible. That is, there is no lambda function $V$ (for inVerse) such that
$$
(V\; A)\; (A\; B) \to B
$$
for every $A$ and $B$ such that $(A\; B)$ can be reduced to normal form. (The arrow means that when the left- and right-hand expressions are reduced to normal form, they are $\alpha$-equivalent.)

However, I'm interested in defining a function $R$ (for Reverse) such that
$$
(R\; A\; B)\; (A\; B) \to B. \tag{1}
$$
Intuitively, $R$ is a function that reverses the application of $A$ to $B$; unlike the inverse function, $R$ is told what $B$ is, and just has to return it. By itself this is trivial of course; $(\lambda x.(\lambda y.(\lambda z.y)))$ does the job.

However, I would also like $R$ to have another property. It follows from $(1)$ that
$$
R\; (R\; A\; B)\; (A\; B)\; B \to (A\; B).
$$
I would like to strengthen this to
$$
R\; (R\; A\; B)\; (A\; B) \to A. \tag{2}
$$
That is, I want the reverse of a reverse calculation to be the original function $A$, rather than just something that gives the same result when applied to $B$.

Is there a function $R$ that has both properties $(1)$ and $(2)$, whenever the reduction to normal form of $(A\;B)$ is possible? If so, what is it - and if not, how can this be shown?


texts: Nuts and Bolts problem: Simpler $o(n^2)$ algorithm

texts:
In this paper, the authors mention that it is possible to get an $o(n^2)$-time algorithm for the nuts and bolts problem by choosing samples based on a projective plane. They also mention that a non-constructive $O(n^{1.5}\log n)$-time algorithm can be obtained (pages 2-3). They omit the details.

I am interested in understanding these approaches, although they are not optimal. Could someone please provide the details of how this is done?


texts: Does mathematical model for conccurent computations exist?

texts:
Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time?

If yes, how are the concurrent computations represented and is it possible to convert them into turing machine?

And do they mathematically describe things like race condition and deadlocks?


texts: How to represent boolean tree + algorithm as a mathematical formula

texts:
In programming say you have a boolean tree like this:

a(
  b(c(), d(),
    e(h(), i(j(), k(l()))),
    f(m(), n(p(), q()), o()),
    g()
  ),
  r(),
  s(t(), u(), v(w(), x(y(z()))))
)

Each function is different, they all can accept arbitrary number of arguments, and they return $\rightarrow \{1,0\}$ a boolean value.

Then there is an algorithm that gets all the leaf nodes, so mathematically we can say:

$$
l = N \rightarrow L'
$$

where $l$ is a "leaf" function mapping all the nodes $N$ to a subset of nodes $L \subset N$.

Finally, there is a "calculate the final boolean value for the tree" function that starts at the leaf nodes and works its way up to the top.

What I'm wondering is how to define that last part mathematically.

How to define the tree that can take into account arbitrary tree structures with arbitrary number of children at each node.
That iterates through the nodes starting from the leaf nodes, then to the parent nodes, then to the parents, until it gets back to the top.

This is as far as I've gotten but don't think it's right.

$$
t = n + (t_0,\dotsc,t_i)?
$$

where $t$ is a tree and $n$ is a node, and $?$ means it's optional. Trying to capture the recursive nature of it.

Procedure:

$$
Start\ at\ leaf\ nodes\ l : N \rightarrow L
$$
$$
Calculate\ value\ v \in \{0,1\}
$$
$$
  Collect\ all\ the\ children\ to\ sum\ their\ value\ V
$$
$$
Repeat\ for\ the\ next\ parent
$$
$$
Finish\ when\ at\ top.
$$

I am new to algorithms and writing them mathematically, so this is probably a beginner question.


texts: Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings

texts:
We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $n$ negative $n$-bit strings. We say that a circuit $C$ separates $(P,N)$ if $C$ accepts all strings in $P$ and rejects all strings in $N$.
I'm looking for any non-trivial lower bound for the size of circuits/formulas separating $n$-pairs.

Question: Is it the case that every $n$-pair $(P,N)$ can be separated by a circuit/formula with $O(n)$ gates?

Note that each such pair can be trivially separated by a circuit/formula with $O(n^2)$ gates: given an input $w\in \{0,1\}^n$, the circuit/formula simply runs through each string $u$ in $P$ and tests whether $w$ is equal to $u$. It accepts if and only if it finds a $u$ that is equal to $w$.
On the other hand, I could not find an argument that implies that a super-linear number of gates is necessary.
Since this type of question seems to be well studied in by the machine learning community I was wondering if anyone could point me to some reference about lower bounds for separation problems as above?


texts: Is combinatory strong reduction equivalent to lambda beta-eta reduction?

texts:
I'm familiar with the correspondence between combinatory logic and $\lambda$-calculus at equality level, ie $=_{\beta\eta}$ corresponds to $=_s$ (the equivalence relation generated by strong reduction) and that there is also a combinatory equality $=_{C\beta}$ corresponding to $=_\beta$ in $\lambda$.

However, I'm having trouble understanding what happens at reduction level. In particular, is it true that Curry's strong reduction corresponds to $\rightarrow_{\beta\eta}$? For instance, could we use strong reduction to "evaluate" (up to $\beta\eta$) $\lambda$-terms? Also, if I understand correctly, is it even harder to come up with a combinatory reduction equivalent to $\rightarrow_\beta$?


texts: A counting subset sum problem with fixed subset size and bounded weights

texts:
I am interested in the following variant of the subset sum problem:

Given a set of positive integer weights $w_1,..., w_n$, such that each $w_i$ is polynomial in $n$, and given integers $s$ and $k$, count the number of subsets of weights of cardinality exactly $s$ such that the sum of the weights in each subset is at most $k$.

I expect that there is a polynomial-time dynamic programming algorithm for this problem but don't have a reference. Can anyone please point me to the relevant reference?


texts: Complexity of finding 2 vertex-disjoint $(|V|/2)$-cycles in cubic graphs?

texts:
I posted this on mathoverflow but with no luck:

Finding a connected 2-factor is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding two vertex-disjoint $(|V|/2)$-cycles in cubic graphs.

I suspect that it is $NP$-complete but I'm not able to find a reference. Also, What is the complexity of finding two vertex-disjoint $(|V|/2)$-cycles with equal cardinality in planar cubic bipartite graphs? Is it $NP$-complete?

Providing references is highly appreciated. $NP$-completeness refers to the decision version of the problem.


texts: On the realisation of monoids as syntactic monoids of languages

texts:
Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as
$$
 u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L
$$
and the quotient monoid $X^{\ast} / \sim_L$ is called the syntactic monoid of $L$.

  Now what monoids arise as syntactic monoids of languages? I found languages for symmetric groups and for the set of all mappings on some underlying finite set. But what about other, are there finite monoids that could not be written as the syntactic monoid of some language?

For a given automaton, by considering the monoid generated by the mappings induced by the letters on the states (the so called transformation monoid) when function composition is read from left to right, it holds that the transformation monoid of the minimal automaton is precisely the syntactic monoid. This observation helped me in constructing the above mentioned examples.

Let me also not that it is quite simple to realise any finite monoid $M$ as the transformation monoid of some automaton, simply take the elements of $M$ as the states, and consider every generator of $M$ as a letter of the alphabet and the transitions are given by $qx$ for some state $q$ and letter $x$, then the transformation monoid is isomorphic to $M$ itself (this is similar to the Cayley theorem about how groups embed into symmetric groups).


texts: Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$

texts: I would like to know if there exists a relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where ${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$.


texts: Find a pair of nodes with maximum sum of distances in k given trees

texts:
For  k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ denotes the sum of weights of the edges in the path between x and y in $T_i$.

Recently I came across the $k \leq 3$ version of this problem, which can be solved in $O(n\log(n))$. But for general k, is there any way to get a complexity lower than $O(n^2)$ (assuming k is a constant)?


texts:
Consider a directed acyclic graph with $n$ nodes and $m$ edges. Each edge is assigned a positive weight. There is a start node $s$ and an end node $e$. We want to find the path from $s$ to $e$ that has the maximum number of nodes such that

  the total distance is less than some constant $d$, and
  starting from $s$, each node in the path is closer than the previous one to the node $e$. (As in, when you traverse the path you are getting closer to your destination $e$ in terms of the edge weight of the remaining path.)

Does a polynomial time algorithm already exist for this problem? Is there a formal name for this problem?


texts: Oracles which put integer factorization in P

texts:
I'm compiling a list of as many problems (decision or function) as I can find such that, if I had an oracle that could solve the problem in P, then integer factorization would also be in P.

Here is a partial list that I have already compiled. Most of these are fairly straight-forward, I would be interested in some which are a little more obscure. I've also omitted some of the more obvious ones (e.g. an oracle which produces a random prime, or the smallest prime, which divides $n$). In each case $n$ represents the integer to be factored, which is assumed to be a non-square composite, and $i,j$ are positive integers.

There are several related functions depending on what response is returned by the oracle (instead of just 1 or 0) or by swapping less than or below with greater than or above, etc. In general, I am only including one from each case:

Decision Problems on $i$

$f_1(i) = 1$ if $i$ is less than the smallest prime factor of $n$, and $0$ otherwise.
$f_2(i) = 1$ if $i$ is greater than the largest prime factor of $n$, and $0$ otherwise.

Function Problems on $i$

$g_1(i) = $ the sum of the number of factors below $i$.
$g_2(i) = 1$ if the number of factors below $i$ is odd, $0$ otherwise.
$g_3(i) = $ the sum of the factors below $i$.
$g_4(i) = $ the sum of non-factors below $i$.
$g_5(i) = $ the distance from $i$ to the nearest factor of $n$.
$g_6(i) = (i!,n)$ the greatest common divisor between $i!$ and $n$
$g_7(i,j) = $ the power of i in $j!$

Function problems on $n$

$h_1(n) = $ the sum of the factors of n.
$h_2(n) = $ the ratio of $q/p$ where $p$ and $q$ are the innermost factors (closest above and below $\sqrt{n}$).
$h_3(n) = \phi(n)$ Euler's totient function


texts: A succinct version of permanent that is $EXP$-complete

texts:
Succinct version of permanent is $NEXP$-hard (https://eccc.weizmann.ac.il/report/2012/086/) and so unlikely to be $EXP$-complete.

Permanent mod $2$ is in $\oplus L$ and so succinct version is unlikely to be $EXP$-complete.

  Is there a natural problem related to permanent that is $EXP$-complete?


texts:
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$ such that
$$\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},$$
and $f$ is a distribution, i.e., $\sum_{x\in \mathbb{Z}_2^n} f(x) = 1$.

The Shannon entropy of $f$ is defined as follows:
$$H(f) = -\sum _{x \in \mathbb{Z}_2^n} f(x) \log \left( f(x) \right) .$$

Let $\epsilon$ be some constant.
Say we get an $\epsilon$-noisy version of $f(x)$, i.e., we get a function  $\tilde{f}:\mathbb{Z}_2^n \to \mathbb{R}$ such that $|\tilde{f}(x)- f(x) | < \epsilon$ for every $x\in \mathbb{Z}_2^n$. What is the effect of the noise on the entropy? That is, can we bound $H(\tilde{f})$ by a "reasonable" function of $\epsilon$ and $H(f)$, such as:
$$(1-\epsilon)H(f) < H(\tilde{f}) < (1+\epsilon)H(f),$$
or even,
$$(1-\epsilon^c n)^d H(f) < H(\tilde{f}) < (1+\epsilon^c n)^d H(f),$$
for some constants $c,d$.

Edit: Trying to get a feeling for the effect of noise on Shannon's entropy, any
 "reasonable" additive bound on $H(\tilde{f})$ would also be very interesting.


texts: Halting time of non deterministic machine

texts:
Let $K$ be a non deterministic machine. I use Minsky Machine (2 counter automaton) for practical reason in my research, but it could be a turing machine, a register machine, whatever.

The Machine have no input. A configuration of a Minsky Machine is the triplet (a state, value of counter 1, value of counter 2). (There is a similar notion of configuration for every machine).  The initial configuration is (state0, 0, 0)

Its computation is a list of successive configuration, that halts in an halting state. The lenght of the computation $s$ is the size of the list, and is denoted by $|s|$.

Let $H(K)$ be the set of computation of this machine that halts.  Then let $S(K)$ be the set of the length of those computation, that is $S(K)=\{|s|\mid s\in H(K)\}$.  It is similar to the "spectral theory" notion http://en.wikipedia.org/wiki/Spectrum_of_a_theory . That is, we forgot everything from a set apart a number.

Finally, let $\mathcal S$ be the set of $S(K)$ for every machine $K$. $\mathcal S=\{S(K)\mid K\}$.
Is there anything we can say about $\mathcal S$ ? Trivially, I can say that it contains only computable sets. It contains every finite set; but between those information, I'm lost.

In an intuitive sense, I'm interested by finding the most complex set of $\mathcal S$.

I should  emphasize that this problem is very different from the $\#P$ class, since: 1) the machine doesn't have any input. 2) I'm not interested in the number of halting path.


texts:
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?

More generally, what's the best we can do for parallel search with updates ?


texts: Quasi-polynomial time algorithm for permutation group isomorphism

texts:
Is there a known $n^{\alpha \log n+O(1)}$ algorithm for permutation group isomorphism? Here $n$ is the size of the group, and the isomorphism must be a permutational isomorphism.

My hope for such an algorithm comes from reading a blog post on the group isomorphism problem and its comments. Because any group of size $n$ has a generator set of size at most $\log_2 n$, maybe a permutation group will even have a strong generator set of size at most $\log_2 n$ (and hopefully that would already be sufficient for a quasi-polynomial algorithm). The comments mention two papers that relate the complexity of the  problem of permutational isomorphism of permutation groups to the complexity of the problem of isomorphism of semisimple groups, and also mention earlier work on the permutational isomorphism problem.

A comment by Ben Barber on a related question indicates that permutation group isomorphism can be reduced to graph isomorphism, which is not really surprising, but nice to know nevertheless.


texts: NP-hardness of a special case of Number Partitioning

texts:
Consider the following problem,

Given a set of $n = k m$ positive
numbers $\{ a_1, \dots, a_n \}$ in
which $k \ge 3$ is a constant, we
want to partition the set into $m$
subsets  of size $k$ so that the product of the
sum of each subset is maximized.

The problem is quite similar to the well known $m$-way number partitioning except we have a limit on the number of numbers in each partition.
For $k = 2$ the following simple polynomial algorithm can be proposed,

assume the numbers are sorted, i.e.
$a_1<a_2<...<a_n$. Then, for $i≤m$ assign $a_i$
to the subset $i$, for $i>m$, assign it
to the subset $n−i+1$.

It's not hard to see why the algorithm works. Just pick two arbitrary bins. Any swap in the numbers will not increase the amount of the product.

But for larger $k$'s, I'm wondered if the problem can be solved in polynomial time or not? I'd be also thankful if somebody can show it's np-hardness.

Note: I encountered the problem while I was working on a scheduling problem in wireless networks. I found a good heuristic algorithm to solve the problem. But after a while I thought the problem might be theoretically interesting.


texts:
Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an efficient $O(n \lg n)$ algorithm. Has anyone come up with an algorithm?

A quick search gave me this paper that proves that its definitely a hard problem. Apparently, no algorithm is given.

[1] Minimal NFA problems are hard / Tao Jiang and B. Ravikumar

I was reminded of this problem by the following question on the CS.SE site for which a DFA->NFA minimization algorithm would be closely related. This following question seems to me to be research level. I suggested migrating it to TCS and I wrote an answer suggesting a statistical/empirical attack.

[2] What are the conditions for a NFA for its equivalent DFA to be maximal in size?


texts: Deterministic error reduction, state-of-the-art?

texts:
Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are

Independent runs + majority vote: run $A$ independently $T=\Theta(\log(1/\delta)$ times, and take the majority vote of the outputs. This requires $rT =\Theta(r\log(1/\delta))$ bits of randomness, and blows up the running time by a $T=\Theta(\log(1/\delta))$ factor.
Pairwise independent runs + Chebyshev: run $A$ "pairwise-independently" $T=\Theta(1/\delta)$ times, and compare to a threshold This requires $rT =\Theta(r/\delta)$ bits of randomness, and blows up the running time by a $T=\Theta(1/\delta)$ factor.

Karp, Pippenger, and Sipser [1] (apparently; I couldn't get my hands on the paper itself, it's a second-hand account) provided alternative approaches based on strong regular expanders: essentially, see the $2^r$ nodes of the expander as the random seeds. Pick a random node of the expander using the $r$ random bits, and then

do a short random walk of length $T=\Theta(\log(1/\delta))$ from there, and run $A$ on the $T$ seeds corresponding to nodes on the path, before taking a majority vote. This requires $r+T = r+\Theta(\log(1/\delta))$ bits of randomness, and blows up the running time by a $T=\Theta(\log(1/\delta))$ factor.
run $A$ on all neighbors of the current node (or, more generally, all nodes within a distance $c$ of the current node) before taking a majority vote. This requires $r$ bits of randomness, and blows up the running time by a $T=d$ factor, where $d$ is the degree (or $d^c$ for distance-$c$ neighborhood. Setting up the parameters well, this ends up costing $T=\operatorname{poly}(1/\delta)$ here.

  I am interested in the last bullet, which corresponds to deterministic error reduction. Has there been any improvement following [1], reducing the dependence of $T$ on $\delta$? What is the current best achievable -- $1/\delta^\gamma$ for which $\gamma > 1$? $\gamma > 0$? (For $\textsf{BPP}$? For $\textsf{RP}$?)

Note: I'm also (very) interested in $\textsf{RP}$ instead of $\textsf{BPP}$. As introduced in [2], the relevant construction then is no longer expanders, but dispersers (see e.g., these lecture notes by Ta-Shma, esp. Table 3). I couldn't find the corresponding bounds for deterministic (not a single more random bit than the allowed $r$) amplification, however, nor (more importantly) what the state-of-the-art explicit disperser constructions for the relevant range of parameters are.

[1] Karp, R., Pippenger, N. and Sipser, M., 1985. A time-randomness tradeoff. In AMS Conference on Probabilistic Computational Complexity (Vol. 111).

[2] Cohen, A. and Wigderson, A., 1989, October. Dispersers, deterministic amplification, and weak random sources. In 30th Annual Symposium on Foundations of Computer Science (pp. 14-19). IEEE.


texts: How hard is counting the number of vertex covers after a small perturbation?

texts:
Suppose you are given both a graph $G(V,E)$ and the exact number $C$ of vertex covers of $G$. Now suppose that $G$ is subject to a very small perturbation $P$, leading to $G'=P(G)$. More precisely, the perturbation $P$ is restricted to be one of the following:

Addition of $1$ new edge.
Addition of $2$ new distinct edges.
Removal of $1$ existing edge.
Removal of $2$ distinct existing edges.

  Question
  Given $G$, $C$, and $P$, how hard is to determine the number $C'$ of vertex covers of $G'=P(G)$? Is it possible to exploit the knowledge of $C$ and the fact that the perturbation is so tiny in order to efficiently determine $C'$?


texts: Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been studied systematically before?


texts:
I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible.

In my case, the stream contains many duplicate values, and I need to make sure that my sample won't include any duplicate values. It is important to note the the number of distinct values in the stream is huge as well (to big to fit memory).

Standard reservoir sampling algorithms (e.g. Algorithm R) ensure that the probability of any index being sampled is equal or about equal. In my case however, I need to make sure that the probability of any value being sampled is equal, or about equal.

Is there any way to achieve this?


texts: Examples of #P problems which are in FP ?

texts: Is there any case of SAT problems (except the affine ones) whose counting version can be computed in polynomial time ?


texts:
Arora and Barak show that $\mathsf{AM}$ can be expressed as $\mathsf{BP}\cdot \mathsf{NP}$ i.e the set of languages that have randomized reductions to 3SAT. $\mathsf{MA}$ is also a natural randomized generalization of $\mathsf{NP}$ in that you replace the deterministic verifier by a randomized one.

Is there a sense in which one of these is a closer fit in the "P is to BPP as NP is to ?"  relation ?


texts: Has parameterized complexity led to better algorithms?

texts:
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, this is the only example I've seen on Downey, Rodney G. and Michael R. Fellows. "Parameterized Complexity".
Has considering a problem in a parameterized way led to different algorithms that end up to be feasible in practice? Or is the Parameterized Complexity Theory just a tool for evaluating complexity of problems?


texts: Postulating self types in a proof assistant

texts:
Self types introduce two typing new rules (simplified):

$
\frac{\Gamma \; \vdash \; t : [t/x]T}{\Gamma \; \vdash \; t : \iota x. T}$ I-self and
$
\frac{\Gamma \; \vdash \; t : \iota x. T}{\Gamma \; \vdash \; t : [t/x]T}
$ E-self

The are related to Very dependent types, dependent intersection.

Their huge appeal is that they allow to prove induction for lambda encoded terms. They are implemented in Formality for that reason.

Is it possible to "hack" them into Agda (or Coq) so that one can play with them in a familiar environment? By "hack" I mean that it is fine to disable termination-checker, allow type-in-type, postulate stuff etc. (I'd be happy with source code modification too but that is likely beyond my skill set).

My first idea was to model the encoding after isorecursive types with $T$ as a higher order type and postulate constants 'Self', 'self' and 'unself':

$
\frac
{\Gamma, T:\star \rightarrow \star \; \vdash \; t : (T t)}
{\Gamma, T:\star \rightarrow \star \; \vdash \; \text{self}\, t : \text{Self} \, T}$ I-self and
$
\frac
{\Gamma, T:\star \rightarrow \star \; \vdash \; t : \text{Self} \, T}
{\Gamma, T:\star \rightarrow \star \; \vdash \; \text{unself} \, t : T t}
$ E-self

And intended evaluation rule ($\text{unself}\, (\text{self}\, t) \stackrel{\beta}{\rightarrow} t$).

Unfortunately this is not working in Agda for various reasons:

postulate
  Self : (T : Set -> Set) -> Set
  unself : (T : Set -> Set) -> (t : Self T) -> T t
  self : (T : Set -> Set) -> (t : T t) -> Self T

Perhaps the technique described in this mysterious issue in Agda can be of help.

Please advise.


texts:
Let $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$ be a function. We want to estimate the average of $f$; that is: $\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$.

NOTE: In the OP, the range of f was [0,1]. I changed this a bit for technical reasons. (This should simplify the problem; if not, forget it!)

Let $E$ be the (randomized) estimator algorithm. Assume that $E$ has black-box access to $f$. We denote this by $E^f$.

There are two conditions:

1) Estimator's running time: There exists a single polynomial $p(\cdot)$ such that for all $n$ and all $f$, the running time of the $E^f(1^n)$ is bounded by $\frac{p(n)}{\mathbb{E}[f(n)]}$.

2) Estimator's precision with confidence $\delta$: There exists a single polynomial $q(\cdot)$, such that for all $n$ and all $f$, we have ${1 \over {q(n)}} < \frac{E^f(1^n)}{\mathbb{E}[f(n)]} < q(n)$ with probability at least $\delta$.

NOTE: The confidence δ was not in the OP. The parameter δ is in (0,1), and may depend on n. For instance, it may be 1-1/2^n.

  Do such estimators exist?

Background and Motivation

I did not mention my motivation at the beginning since it requires a great deal of background knowledge. Anyway, for the enthusiasts, I describe it briefly: The need for such estimators arise in the context of "Proofs of Ability," as defined in the following article:

Mihir Bellare, Oded Goldreich. Proving Computational Ability, 1992. Unpublished Manuscript.

Specifically, at the bottom of page 5, the authors implicitly assumed the existence of such estimators (There's no mention of precision, and the running time is not precisely defined; yet the context clearly defines everything.)

My first attempt was to read "A Sample of Samplers---A Computational Perspective on Sampling." It pertains to a very similar problem, yet the error probability defined is additive, while ours is multiplicative. (I didn't fully read the paper, maybe it mentions what I need somewhere.)

EDIT (as per Tsuyoshi's request): In fact, the definition of "Proofs of Computational Ability" requires the existence of a "knowledge extractor" whose (expected) running time is $p(n) \over E[f(n)]$. Since we don't know $E[f(n)]$, we want to estimate it; yet this must not change the running time considerably: it should change it up to a polynomial factor. The precision condition tries to capture such requirement.


texts: Comparison between the maximum clique and maximum biclique problem

texts: It seems to be commonly believed that the maximum biclique problem (on a bipartite graph) is more difficult than the original maximum clique problem. Is there a formal proof for this claim? (For example, a reduction of the maximum clique problem to the maximum biclique problem.)


texts:
What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think that these algorithms are more time consuming since the evaluation complexity is not constant (assuming my calculations are correct).

What are some good alternative that are less time consuming? are their any technique swapping nodes for example? Could you suggest a good paper about such algorithms?


texts:
Are there any common approaches for finding a vertex separator in a bipartite graph $G = (V_1, V_2, E)$ where the selected vertices are constrained to come from one partition of the graph?

I have a large bipartite graph with $|V_1|$ = 40M and $|V_2|$ = 150K and want to remove vertices from $V_1$ to disconnect the graph.  Obviously, with a graph this large, I need a fairly efficient algorithm.

Does anyone have suggestions?


texts: Realization of a bipolar orientation by a mixed graph

texts:
Given an undirected graph $G(V,E)$ and a bipolar orientation $s$ over $G$, consider the problem of identifying $s$ by finding the minimum number of edges such that when orienting them in a particular way they give arise only to $s$ as bipolar orientation. An orientation $s$ for a graph $G$ is bipolar if $s$ is acyclic and has a single source and single sink.

That is, find the minimum subset of edges $\hat{E}\subseteq E$ such that if we orient them $\vec{E}$, the only bipolar orientation for the mixed graph $(V,E-\hat{E},\vec{E})$ is $s$. Is this problem known? has been tackled before? Any pointer is appreciated.


texts: Can we count in depth $\frac{\lg n}{\lg \lg n}$?

texts:
Can we compute an $n$-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth $\frac{\lg n}{\lg \lg n}$? Alternatively, can we count the number of 1s in the input bits using these circuits?
Is $\mathsf{TC^0} \subseteq \mathsf{AltTime}(O(\frac{\lg n}{\lg  \lg n}), O(\lg n))$?

Note that $\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$. So the question is essentially asking if we can save a $\lg \lg n$ factor in the depth of circuits when computing threshold gates.

Edit:
As Kristoffer wrote in his answer we can save a $\lg \lg n$ factor. But can we save a little bit more? Can we replace $O(\frac{\lg n}{\lg \lg n})$ with $o(\frac{\lg n}{\lg \lg n})$?
It seems to me that the layered brute-force trick doesn't work for saving even $2 \lg \lg n$ (more generally any function in $\lg \lg n + \omega(1)$).