What is the "nearest" problem to the Collatz conjecture that has been successfully resolved? I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ripe for such problems"). It has been proven that a class of "Collatz-like" problems is undecidable. However, problems that are vaguely similar such as Hofstadter's MIU game (resolved, but admittedly more of a toy problem) are indeed decidable or have been solved.
Related questions
Collatz Conjecture & Grammars / Automata

An extended comment:

Collatz-like sequences can be computed by small Turing machines having few symbols and states.  In "Small Turing machines and generalized busy beaver competition" by P. Michel (2004), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs.

There are TMs that compute Collatz-like sequences for which the decidability is still an open problem: $TM(5,2)$, $TM(3,3)$ and $TM(2,4)$ (where $TM(k,l)$ is the set of Turing Machine with $k$ states and $l$ symbols). I don't know if the results have been inproved.

From the comclusion of the paper:

... The present Collatz-like line is already on its lowest possible level, with the possible exception of $TM(4,2)$, but we conjecture that all machines in this set can be proved to be decidable...

See also "The complexity of small universal Turing machines: a survey" by D. Woods and T. Neary (2007).

Another example of Collatz-like problem for which decidability is an open problem is the Post's tag system: $\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$; for a recent analysis see "On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results" by L. De Mol (2009).


Lighting up all elements of a poset by toggling upsets I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. Each move of the game consists of choosing one element $x$ of the poset; then I consider its upset $U_x = \{y \in P \mid x \leq y\}$ and:

If all elements of $U_x$ are off, then I can play an on-move on $x$, which turns all of $U_x$ on, so $S$ becomes $S \cup U_x$ (with the union being disjoint).
If all elements of $U_x$ are on, I can play an off-move on $x$ and turn all of $U_x$ off, so $S$ becomes $S \setminus U_x$ (with $U_x \subseteq S$).
Otherwise I cannot currently play on this $x$.

My goal is to switch on all elements of the poset, i.e., find a sequence of moves that reaches $S = P$, from the initial configuration $S = \emptyset$. However, I impose that for each element $x$, all my plays on $x$ in the sequence are of the same type, i.e., if I play an on-move on $x$ then I am not allowed to play an off-move on $x$ at any point of the sequence -- but I can play other on-moves on $x$ if I want. (If we don't impose this, then it's not too hard to show by induction that we can always win.)

My question is: What are the posets on which there is a way to win the game? In particular, can we always win when $P$ is a join-semilattice, i.e., any nonempty subset of elements has a least upper bound?

For a simple example of the game, consider $P$ with the following Hasse diagram:

I have animated a winning strategy on the picture. Initially all vertices are off (=white). Then we do the following:

first play an on-move on $A$ (and $S$ becomes $\{A, D, E\}$),
then play an off-move on $D$ (and $S$ becomes $\{A\}$),
then play an on-move on $B$ (and $S$ becomes $\{A, B, D, E\}$),
then play an off-move on $D$ again (and $S$ becomes $\{A, B\}$),
last play an on-move on $C$ (and $S$ becomes $P$ and I have won).

For a more complicated example, consider the following:

I have animated the steps on a winning sequence: on-move on $A$, off-move on $D$, on-move on $B$, off-move on $E$, on-move on $G$, off-move on $F$, on-move on $C$. Note that this is a bit tricky to find, e.g., starting a play with $G$ cannot win.

There is a relationship between the game and the Möbius inversion formula on posets. Specifically, if I define $\mu(x) = 1 - \sum_{y < x} \mu(y)$, in particular $\mu(x) = 1$ if $x$ has no ancestors, then the sign and absolute value of $\mu(x)$ tells me which types of move I should play on $x$, and how many. In particular when $\mu(x) = 0$, we should never play on $x$, as with the vertex $H$ in the example above. Another way to see this is about a restricted way to compute the inclusion-exclusion formula with no cancellations.

I already know that we cannot win on every poset, as a computer search by Louis Jachiet turned out the following poset, where there is no winning strategy (checked by exhaustive search). There is no counterexample with less than 9 elements:

For our purposes we are interested in knowing whether the game can always be won on join-semilattices, i.e., every nonempty set of elements has a least upper bound (i.e., a unique descendant which is as high as possible). This is not the case above (consider $A$ and $B$), and this requirement seems to constrain the structure of the graph, but we don't know how to prove the claim (or whether it is true). We have been running a computer search for join-semilattices on which the game cannot be won, but we haven't found a counterexample yet.

As for the motivation of the problem, it was originally about expressing certain kinds of Boolean functions using restricted classes of circuits, with connections to safe queries over probabilistic databases.

Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck).

The main thing we have for now is a partial result on so-called crown-free lattices. To show it, for two elements $x,y$ of the poset $P$, I say that $x$ is covered by $y$ if $x\geq y$, $x \neq y$, and there are no elements in between (i.e., $y$ is just above $x$ in the Hasse diagram of $P$). Let me now show claim (*): we can then assume without loss of generality that $P$ is such that:

there are no elements $x$ of $P$ that cover exactly one element; and
for every minimal element $x$ of $P$, $x$ is covered by at least two elements.

I will show this by taking a poset $P$ such that it has an $x$ satisfying condition 1. or 2., and then considering the poset $P'$ where we have removed $x$, and show that if $P'$ is winnable then so is $P$. Assume first that $x$ satisfies 1., and let $\mathbf{s}$ be a winning sequence for $P'$ (a sequence of moves that goes from $\emptyset$ to $P'$). Then it is easy to see that $\mathbf{s}$ is also a winning sequence for $P$; indeed the state of $x$ (on or off) will always follow the state of its unique child, and we never need to click on $x$ (this can also be explained by checking that $\mu_P(x) = 0$), so all moves are valid. Assume now that $x$ satisfies 2., and again let $\mathbf{s}$ be a winning sequence for $P'$. Let $p$ be the unique parent of $x$ in $P$, and let $a = \mu_P(p)$. It is easy to show that $\mu_{P'}(p) = a+1$ and that $\mu_{P'}(y) = \mu_P(y)$ for all $y \in P'$, $y \neq p$. I then consider two cases:

$a<0$. We can then obtain a winning sequence for $P$ as follows: first, play an on-move on $x$, then play an off-move on $p$ (this is legal since $a<0$), and then play the sequence $\mathbf{s}$. Observe that we have $a+1 \leq 0$, so in the whole sequence we will only play off-moves on $p$, and it is clear that all the moves are valid and that we end up with everything being on, so that this is indeed a winning sequence for $P$.
$a \geq 0$. In this case $a+1>0$, which mean that in $\mathbf{s}$ we will only play on-moves on $p$, and we will play at least one. We then obtain a winning sequence for $P$ as follows: play the sequence $\mathbf{s}$, but the very first time we play an on-move on $p$, play an on-move on $x$ instead. Again, it is easy to see that this is indeed a winning sequence for $P$.

This concludes the proof of claim (*).

If we look at the first example in the question, we can deal with it using claim (*): we can eliminate $E$ because it satisfies condition 1., then we can eliminate $A$, $B$ and $C$ (because they satisfy condition 2.), and we end up with only one node ($D$), and this is clearly a poset that is winnable. However for the second example in the question, we can eliminate $G$ (it satisfies condition 2.), but then there is nothing to eliminate, so here he'd need something else to show that $P'$ is winnable.

Claim (*) implies in particular that join-semilattices that are obtained from dismantable lattices by removing the bottom element are winnable; these are lattices that can be emptied by recursively removing the doubly irreducible elements, see
Kelly, David; Rival, Ivan, Crowns, fences, and dismantlable lattices, Can. J. Math. 26, 1257-1271 (1974). This paper shows in particular that dismantable lattices are exactly the lattices that are crown-free (see the paper for the definition), so if we want to solve our problem for join-semilattices only (instead of for all posets), it becomes equivalent to the following:

Can we win for every join-semilattice that has a crown? (Note that the second example in the question is a join-semilattice that has a crown).

Other than claim (*), we have some code (there) to decide if a given poset is winnable or not, and if yes to visualize the winning strategy. In particular we have generated a lot of join-semilattices and found no counter-example so far.

We are also working on a generalization of this problem: see this note.


List of TCS conferences and workshops I would like to ask for help in compiling a list of as many TCS-related conferences and workshops as possible.  My main motivation for doing this is to plan possible blog coverage of more theory venues -- finding correspondents attending these events who would be willing to write either brief or in-depth blog entries about events they are attending.  Beyond that, I hope a list like this would give everyone a better sense of the lay of the theory land.

I'll seed the question with an answer containing a few "obvious" conferences.  Please feel free to edit my answer and/or post additional answers of your own.

  Standard abbreviation of conference, name of conference, subject matter, any additional notes.

Intended as community wiki.

GENERAL:

STOC, ACM Symposium on the Theory of Computing
FOCS, IEEE Symposium on Foundations of Computer Science
ICALP EATCS International Colloquium on Automata, Languages and Programming
(A: algorithms, complexity, B: logic, semantics, C: networks)
FOSSACS, Foundations of Software Science and Computation Structures
STACS, Symposium on Theoretical Aspects of Computer Science
MFCS, Mathematical Foundations of Computer Science
FSTTCS, Foundations of Software Technology and Theoretical Computer Science
COCOON, Computing and Combinatorics Conference
ITCS, Innovations in Theoretical Computer Science
CSR, Computer Science in Russia
ISAAC, International Symposium on Algorithms and Computation
TAMC, Theory and Applications of Models of Computation
COCOA, Conference on Combinatorial Optimization and Applications
FM, Formal Methods
FCT, Fundamentals of Computation Theory
LATIN, Latin American Symposium on Theoretical Informatics
SOFSEM, Conference on Current Trends in Theory and Practice of Computer Science
TASE, Theoretical Aspects of Software engineering

CC: COMPLEXITY

CCC, IEEE Conference on Computational Complexity
SIROCCO, International Colloquium on Structural Information and Communication Complexity

CG: COMPUTATIONAL GEOMETRY

SOCG, Symposium on Computational Geometry
CCCG, Canadian Conference on Computational Geometry
EuroCG, European Workshop on Computational Geometry

CR: CRYPTOGRAPHY AND SECURITY

CRYPTO, International Cryptology Conference
EUROCRYPT, Conference on the Theory and Applications of Cryptographic Techniques
ASIACRYPT, Conference on the Theory and Application of Cryptology
LATINCRYPT, International Conference on Cryptology and Information Security in Latin America
AFRICACRYPT, International Conference on Cryptology in Africa
PQCRYPTO, International Conference on Post-Quantum Cryptography
TCC, Theory of Cryptography Conference
PKC, International Conference on Practice and Theory in Public Key Cryptography
FSE, Conference on Fast Software Encryption
CHES, Conference on Cryptographic Hardware and Embedded Systems
IEEE S&P, IEEE Symposium on Security and Privacy
CCS,  ACM Conference on Computer and Communication Security
POST, Principles of Security and Trust
CSF, Computer Security Foundations Symposium
ITC, Information Theoretic Cryptography

DB: DATABASE THEORY

SIGMOD/PODS, ACM Symposium on Principles of Database Systems (both accept theory, but SIGMOD has broader scope)
ICDT, The international Conference on Database Theory
VLDB, Very Large Data Bases
AMW, Alberto Mendelzon International Workshop on Foundations of Data Management

DC: DISTRIBUTED, PARALLEL, AND CLUSTER COMPUTING

PODC, ACM Symposium on Principles of Distributed Computing
DISC, International Symposium on Distributed Computing
SPAA, ACM Symposium on Parallelism in Algorithms and Architectures
IPDPS, IEEE International Parallel and Distributed Processing Symposium
ICDCN, International Conference on Distributed Computing and Networking
OPODIS, International Conference on Principles of Distributed Systems
SSS, International Symposium on Stabilization, Safety, and Security of Distributed Systems
Algosensors, International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities

DM: DISCRETE MATHEMATICS AND COMBINATORICS

WG, International Workshop on Graph-Theoretic Concepts in Computer Science
LAGOS, Latin-American Algorithms, Graphs and Optimization Symposium

DS: DATA STRUCTURES AND ALGORITHMS

SODA, ACM-SIAM Symposium on Discrete Algorithms
ESA, European Symposium on Algorithms (track A is theoretical)
WADS, The Algorithms and Data Structures Symposium
SAT, Theory and Applications of Satisfiability Testing
SWAT, Scandinavian Symposium and Workshops on Algorithm Theory
ALENEX, Algorithm Engineering and Experimentation
SOSA, Symposium on Simplicity in Algorithms
IPCO, Integer Programming and Combinatorial Optimization
APPROX/RANDOM, Workshop on Approximation Algorithms for Optimization Problems / Workshop on Randomization and Computation
WAOA, Workshop on Approximation and Online Algorithms
IPEC, International Symposium on Parameterized and Exact Computation
IWOCA, International Workshop on Combinatorial Algorithms
WAW, Workshop on Algorithms and Models for the Web-Graph
CPM, Combinatorial Pattern Matching
CP, Principles and Practice of Constraint Programming

FL: AUTOMATA THEORY AND FORMAL LANGUAGES

DLT, International Conference on Developments in Language Theory
LATA, Language and Automata Theory and Applications
AFL, Automata and Formal Languages
NCMA, Non-Classical Models of Automata and Applications
CIAA, International Conference on Implementation and Application of Automata
DFCS, Descriptional Complexity of Formal Systems

GT: ALGORITHMIC GAME THEORY

EC, Electronic Commerce
SAGT, International Symposium on Algorithmic Game Theory
WINE, Workshop on Internet and Network Economics

LG: LEARNING THEORY

COLT, Conference on Learning Theory
ALT, Algorithmic Learning Theory

LO: LOGIC IN COMPUTER SCIENCE

LICS, IEEE Symposium on Logic in Computer Science
CONCUR, International Conference on Concurrency Theory
CSL, Computer Science Logic
CiE, Computablility in Europe
LCC, An International Workshop on Logic and Computational Complexity
WoLLIC, Workshop on Logic, Language, Information and Computation
Highlights of logic, games and automata

PL: PROGRAMMING LANGUAGES

POPL, Principles of Programming Languages
ICFP, International Conference on Functional Programming
ETAPS, European Joint Conferences on Theory and Practice of Software (includes FOSSACS, ESOP and POST, see separate entries)
ESOP, European Symposium On Programming
MSFP, Mathematically Structured Functional Programming
MFPS, Mathematical Foundations of Programming Semantics

SC: SYMBOLIC COMPUTATION

ISSAC: International Symposium on Symbolic and Algebraic Computation
FPSAC: Formal Power Series and Algebraic Combinatorics
CASC: Computer Algebra in Scientific Computing
SNC: Symbolic Numeric Computation

THEOREM PROVING

CADE, International Conference on Automated Deduction
ITP, Interactive Theorem Proving
CPP, Certified Proofs and Programs

QUANTUM

QIP, Workshop on Quantum Information Processing
QCMC, International Conference on Quantum Communication, Information and Computing
TQC, Theory of Quantum Computation, Communication and Cryptography
AQIS, Asian Quantum Information Science Conference
QCRYPT, Conference on Quantum Cryptography
QEC, International Conference on Quantum Error Correction
CEQIP, Central European Quantum Information Processing Workshop

RO: Robotics

WAFR, Workshop on the Algorithmic Foundation of Robotics.

COMPUTATIONAL BIOLOGY

RECOMB: Research in Computational Molecular Biology
ISMB: Intelligent Systems for Molecular Biology
WABI: Workshop on Algorithms in Bioinformatics

OTHER

CAV, Computer Aided Verification
GD, International Symposium on Graph Drawing
FUN, International Conference on Fun With Algorithms
DNA, DNA Computing and Molecular Programming (DNA computing, Track A is theoretical, track B is experimental)
DCM, Developments in Computational Models
RTA, Rewriting techniques and applications
TLCA, Typed lambda calculi and applications
UCNC, Unconventional Computation & Natural Computation


Reference Request: Submodular Minimization and Monotone Boolean Functions Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions.  If we discard the constraint that a density integrates (sums) to 1, we get an unnormalized graph-structured energy function.

Suppose we have such an energy function, $E$, defined on a graph $G = (\mathcal{V}, \mathcal{E})$.  There is one variable $x$ for each vertex of the graph, and there are real-valued unary and pairwise functions, $\theta_i(x_i) : i \in \mathcal{V}$ and $\theta_{ij}(x_i, x_j) : ij \in \mathcal{E}$, respectively.  The full energy is then

$$E(\mathbf{x}) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{ij \in \mathcal{E}} \theta_{ij}(x_i, x_j)$$

If all $x \in \mathbf{x}$ are binary, we can think of an $x$ as indicating set membership and with just a small abuse of terminology talk about submodularity.  In this case, an energy function is submodular iff $\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$.  We are typically interested in finding the configuration that minimizes the energy, $\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$.

There seems to be a connection between minimizing a submodular energy function and monotone boolean functions: if we lower the energy of some $\theta_i(x_i=1)$ for any $x_i$ (i.e., increase its preference to be "true"), then the optimal assignment of any variable $x_i^* \in \mathbf{x}^*$ can only change from 0 to 1 ("false" to "true").  If all $\theta_i$ are restricted to be either 0 or 1, then we have $|\mathcal{V}|$ monotone boolean functions:

$$f_i(\mathbf{\theta}) = x_i^*$$

where as above, $\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$.

Question: Can we represent all monotone boolean functions using this setup by varying the pairwise terms, $\theta_{ij}$?  What if we allow $E$ to be an arbitrary submodular energy function?  Conversely, can we represent all submodular minimization problems as a set of $|\mathcal{V}|$ monotone boolean functions?

Can you suggest references that will help me towards better understanding these connections?  I'm not a theoretical computer scientist, but I'm trying to understand if there are insights about monotone boolean functions that are not captured by thinking in the submodular minimization terms.

As far as I understand, the submodular minimization case captures all there is to be said about the monotone Boolean case, and binary submodular Boolean functions can express all submodular Boolean functions.  However, if the domain is non-Boolean, then binary submodular functions are not enough to express all submodular functions, even if hidden variables may be introduced.  (Apologies if I have missed a subtlety in your precise problem phrasing.)

The state of the art is discussed in this nice paper which has lots of links to related work, and that also makes the links to computer vision quite explicit:

Stanislav Živný, David A. Cohen, Peter G. Jeavons, The expressive power of binary submodular functions, DAM 157 3347–3358, 2009.  doi: 10.1016/j.dam.2009.07.001 (preprint)

In case your next question is about approximation, this recent paper looks at the approximation version:

Dorit S. Hochbaum, Submodular problems - approximations and algorithms, arXiv: 1010.1945

Edit: fixed link.


Is generalized pigeonhole search known to be no harder than PPP? Consider the TFNP search problem

  Given a positive integer $t$ in unary, positive integers $M$ and $N$ (in binary), and a

  function from $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}M\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}M\hspace{-0.04 in}-\hspace{-0.05 in}1\hspace{-0.02 in}\}$ to $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}N\hspace{-0.05 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}N\hspace{-0.05 in}-\hspace{-0.05 in}1\hspace{-0.02 in}\}$ (as a circuit),

  find $\: \operatorname{min}(t,\hspace{-0.04 in}\lceil M/N\hspace{.02 in}\rceil) \:$ distinct inputs that map to the same output.

.

That problem is clearly hard for the class PPP. $\:$ Is that problem known to be in PPP?

Please see the comments below by Emil Jeřábek, so I am not that sure anymore that the problem is harder.

No, it is not known but it is harder than PPP :)

Here I focus on the $M=2N+1$ case, so $t=3$, that is, we want $3$ inputs that map to the same output. In Papadimitriou's seminal paper "On the Complexity of the Parity Argument" he defined PPA-3 similarly to PPA as the search problems reducible to the argument "If in a bipartite graph a node has degree not a multiple of 3, then there is at least another such node."

Let me define here PPAD-3 in a way similar to PPAD as the search problems reducible to the argument "If in a balanced, directed bipartite graph $(A,B;E)$ there is a node in $A$ whose outdegree is not $2$ or whose indegree is not $1$, then there is at least another such node in $A$ OR there is a node in $B$ whose outdegree is not $1$ or whose indegree is not $2$."

Just like PPAD$\subset$PPP, you can show that PPAD-3 is a subset of the problem you have defined. Unfortunately this is all the evidence I can give you as (as far as I know) PPA-3 has not been investigated much and no oracle separation results are known for it, though I don't think it would be hard to obtain some. Papadimitriou defining it as a separate class should be enough evidence that there is a good chance that they differ.


Fast sparse boolean matrix product with possible preprocessing What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)?

Actually, I have the advantage that when I'm multiplying A by B, the B's are predefined and I can do arbitrarily complex preprocessing on them. I also know that the results of products are always as sparse as the original matrices.

The "rather naive" algorithm (scan A by rows; for each 1 bit of the A-row, OR the result with the corresponding row of B) turns out very efficient and requires only a couple thousand of CPU instructions to compute a single product, so it won't be easy to surpass it, and it's only surpassable by a constant factor (because there are hundreds of one bits in the result). But I'm not losing hope and asking the community for help :)

I was reluctant to answer this, because the only theoretical result I know of along these lines has my name on the paper...

Theoretically, it is possible to preprocess a dense $n \times n$ Boolean matrix $A$ so that sparse matrix-vector multiplications with $A$ (over the semiring of OR and AND) can be done faster than the naive running time. Probably a significant amount of hacking would be needed to implement it in practice, but I do think it would fare well in practice for large enough $n$ and the right implementation.

(Note: this algorithm is only really useful for the case where one matrix is dense and the other is sparse. This case comes up a lot though, e.g., when computing transitive closure of a sparse graph, the transitive closure matrix will eventually get dense compared to the original adjacency matrix.)

The paper is

  Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: A New Combinatorial Approach for Sparse Graph Problems. ICALP (1) 2008: 108-120

and the relevant result from the paper is that for every $\varepsilon > 0$, there is an $O(n^{2+\varepsilon})$ time algorithm that, given any $n \times n$ 0-1 matrix $A$, the following operations are supported:

-- For any vector $v$ with only $t$ nonzeroes, $A v$ can be computed in $O(n(t/k + n/\ell)/\log n)$ time, where $\ell$, $k$ are free parameters satisfying ${\ell \choose k} \leq n^{\varepsilon}$. (One nice setting is $\ell=\log^c n$ and $k=\varepsilon(\log n)/\log \log n$, so that the running time is about $nt/\log n + n^2/\log^c n$ for any desired constant $c$.

-- Row and column updates to $A$ can be computed in $O(n^{1+\varepsilon})$ time.

We used this data structure to give faster theoretical algorithms for APSP in sparse unweighted graphs.


Complexity class corresponding to sorting Two parts of TCS are algorithms and complexity. I'll simplistically say that algorithms is the study of upper bounds, showing that you can do something (with given restricted resources), and complexity is about showing that you cannot do it without some minimal resources.

So often an algorithmic problem is stated in a decision model in order to place it in a complexity class.

But something that's always bothered me is that some elementary algorithms are never mentioned outright as belonging to a particular class. One example is (comparison) sorting. Try as I might, a relevant class just seems too deficient (really, is it just checking in logspace that the result is sorted? That just seems too weak, or I'm not getting the decision version right).

What is the best/most appropriate/most useful complexity class that comparison sorting lies in?

The sorting problem is actually complete for $\mathsf{TC}^0$ (under $\mathsf{AC}^0$-reduction). A standard source for this is Section 1.4.3 of Vollmer's book.

Note that $\mathsf{TC}^0$ is the class of decision problems, but we usually think of sorting as a function problem, i.e., we want to output the numbers, say, in nondecreasing order. However, we can also define sorting as a decision problem as follows:

  Given a sequence of numbers $a_1,\ldots,a_n$ and two numbers $k,p\in [n]$, we want to decide if $a_k$ is at position $p$ in the sequence we get by sorting $a_1,\ldots,a_n$ in nondecreasing order. Note that to avoid ambiguity, when $a_i=a_j$, we want $a_i$ to precede $a_j$ if $i<j$.


Are variables in RHS of Chomsky Normal Form productions distinct? I'm wondering if it is permitted for production rules in a context-free grammar (CFG) in Chomsky Normal Form (CNF) to have multiple occurences of the same variable in the right-hand side of the productions.

e.g. is this permitted:

$A \to BB$

or must one do something like

$A \to B_1 B_2$

$B_1 \to B$

$B_2 \to B$

The only definitions of CNF I have found define production rules of the form $A \to B C$ , but none ever state that $B \neq C$

Yes. The production rules of the form $A \rightarrow BB$ are allowed. One of the motivations behind CNF is to make the parse tree a binary tree so that we can have a unified way of talking about the relationship between the depth of the parse tree and the length of its yield. So having rules of the form $A \rightarrow BB$ does not disrupt this goal. However, replacing $A \rightarrow BB$ by $A \rightarrow B_1B_2$, $B_1 \rightarrow B$ and $B_2 \rightarrow B$ might create problems in analyzing the depth of parse tree especially when you have rules like $B \rightarrow XY$. This will create intermediate nodes in the parse tree with outdegree one, while the goal of CNF is to "push" such nodes to the leaves.


"Refined" list of open problems in TCS In the conference on learning theory (COLT), a list of open problems is published every year, for example, the list of 2019.
The open problems are being submitted and peer reviewed, which makes this list reliable (in the sense that the problems are well-defined, motivated and "accessible").
In the area of sublinear algorithms and property testing, there is this wiki page, which similarity includes a list of open problems.
My question is: are there similar lists for other areas in TCS (e.g. complexity, cryptography etc.)? I didn't find such a list in common conferences, and I wonder if there are blogs/websites with a list of known open problems (which are accessible in some sense, i.e. not just "p,np" and problems at that level)

There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.


Is there an NP-complete language that contains precisely half of the n-bit instances? Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$
$$|L\cap \{0,1\}^n|=2^{n-1}$$
holds? In other words, $L$ contains precisely half of all $n$-bit instances.

I asked this question a few years ago and Boaz Barak positively answered it.

The statement is equivalent to the existence of an NP-complete language $L$ where $|L_n|$ is polynomial-time computable.

Consider Boolean formulas and SAT.
Using padding and slightly modifying the encoding of formulas
we can make sure that
$\varphi$ and $\lnot \varphi$ have the same length.

Let $\langle\ \rangle$ be an encoding that

for all formulas $\varphi$ and
for all truth assignment $\tau \in \{0,1\}^{|\varphi|}$,
$|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$.
$|\langle\varphi\rangle| \mapsto |\varphi|$ is polynomial-time computable.
the number of formulas with encoded length $n$ is polynomial-time computable.

Consider
$$L := \{\langle\varphi\rangle \mid \varphi \in \mathsf{SAT} \} \cup
\{\langle \varphi, \tau \rangle \mid \tau \vDash \varphi \text{ and }
\exists \sigma<\tau\ \sigma\vDash\varphi \}$$

It is easy to see that $L$ is NP-complete.

If $\varphi \in \mathsf{SAT}$,
the number of truth assignments satisfying
$$\tau \vDash \varphi \text{ and }
\exists \sigma<\tau\ \sigma\vDash\varphi$$
is equal to the number of satisfying truth assignments $- 1$.
Adding $\varphi$ itself it adds up to
the number of satisfying truth assignments for $\varphi$.

There are $2^{|\varphi|}$ truth assignments.
Each $\tau$ either satisfies $\varphi$ or $\lnot \varphi$ (and not both).
For every formula $\varphi$,
consider the $2(2^{|\varphi|}+1)$ strings $\langle\varphi\rangle$,
$\langle\lnot \varphi\rangle$,
$\langle\varphi, \tau\rangle$, and
$\langle \lnot\varphi, \tau\rangle$
for $\tau \in \{0,1\}^{|\varphi|}$.
Exactly $2^{|\varphi|}$ of these $2^{|\varphi|+1}+2$ strings are in $L$.
This means that the number of strings of length $n$ in $L$ is
the number of formulas $\varphi$ of encoded length $n$ multiplied by $2^{|\varphi|}$ which polynomial-time computable.


Where does the "intuitive" understanding of Kolmogorov complexity fails Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.

So to give this more formal meaning, define
$$
 K'(x) := |f| + |a_1| + \ldots |a_k|
$$
where $f(s_1, s_2,\ldots, s_k)$ is some function with $k$ arguments in some specific programming language (like C++ for example).

How does this definition relates to Kolmogorov complexity? I mean this could not be the same, as with this definition we have
$$
 K'(xy) \le K'(x) + K'(y) + C
$$
with some constant $C$. For if $f(a_1, \ldots, a_k) = x$ and $g(b_1,\ldots, b_l) = y$ are functions to compute $x$ and $y$, then

  h() {
   return concat(f(a1, ..., ak), g(b1,...,bl));
  }

would be a function to compute $xy$ of complexity $|f| + |a1| + \ldots + |ak| + |g| + |b1| + \ldots |bl| + C$, where $C$ represents the bits needed to declare $h$, the parentheses, the return statement and to call concat (string concatentation function).

Hence $K'(xy) \le K'(x) + K'(y) + C$.

But as is well-know for the usual Kolmogorov complexity we do not have such an subadditivity?

EDIT: This will also work if we just allow functions with a single parameter.

The issue in play here is whether you use a self-terminating encoding (like your C example) or not. If you use a self-terminating encoding, then the subadditivity property does hold. If you don't (as in the common definition), then you need to expend bits on delimiting encodings.

Self-terminating encodings have other advantages, and even though real programming languages are always self-terminating, the pioneers of Kolmogorov complexity (Solomonoff, Kolmogorov and Chaitin) defined their notion of complexity with respect to non-self-terminating encodings. The classic monograph of Li and Vitanyi treats both variants.


How hard is it to reduce termination to partial correctness? If you are familiar with program verification you are likely to prefer reading the Question before the Background. If you are not familiar with program verification then you may still be able to answer this question, but you are likely to prefer reading the Background first.

Background

It is often stated that checking partial correctness is undecidable. For the sake of discussion, let's pick one very particular way of making this statement precise, in the style of Floyd--Hoare. A flowgraph is a digraph with a distinguished initial node from which all nodes are reachable. A program is a flowgraph whose nodes are commands. There are three types of commands (1) assumptions assume q, (2) assertions assert q, and (3) assignments v:=e. Here q is a fol (first-order logic) formula, e is a fol term, and v is a variable.

We say that a program is partially correct when there is a way to annotate each node x with a precondition a(x) and a postcondition b(x) such that (1) the precondition of the initial node is valid, (2) {a(x)} x {b(x)} holds for all commands x, and (3) (b(x) implies a(y)) is valid for all edges from x to y. Here the Hoare triples are defined as follows:

{p} assert q {r} means that (p implies (q and r)) is valid
{p} assume q {r} means that ((p and q) implies r) is valid
{p} v:=e {r} means that ((p with e substituted for v) implies r) is valid

Here's a hand-wavy argument of why checking this partial correctness is undecidable: Once you fill in some a(x) and some b(x) you need to check if some fol formulas are valid, and that is undecidable.

A typical way to encode termination in partial correctness is to add some special assertions that essentially say "since last time I was executed, there was progress towards termination." These progress assertions must be placed such that all infinite walks on the flowgraph (that start at the initial node) contain infinitely many progress assertions. To be more specific, let's say that progress assertions always have the form assert u < v, where u and v are positive integers, are preceded by the assignment u:=f, and are followed by the assignment v:=u. Here f is a variant function, u is its current value, and v is its former value. Now, since we talk about "positive integers" and we compare them, we need to ensure that a bit more than fol is available: Let's say Peano arithmetic is available. (I don't feel strongly about this choice. Feel free to disregard if convenient.) Of course, f may use any other functions and constants that are mentioned in the program. (Note that adding assumptions at the beginning of the program is equivalent to introducing non-logical axioms.)

Now, if the program with progress assertions is still partially correct, then we know that the original program terminates.

Question

Given a terminating program, it feels that coming up with variant functions for progress assertions is hard. But how hard? (I know that even with the huge background above, I still left this question sort of open-ended, or ill-defined, depending on how you want to look at it.)

To put it differently: I'm looking for a reference that formalizes the problem of reducing termination to partial correctness and then says something about its complexity. An answer that does all this would of course be welcome.

One way to answer this is to consider the computational complexity of the decision problems for the classes of partial correctness and termination queries that are known to be decidable.  Abstract interpretation using the polyhedral domain can infer the partial correctness annotations you mention in cases where the required annotations are conjunctions of linear inequalities.  Computing the abstract post-condition is exponential in the number of variables.  Then there is the overhead of finding the fixed point.  See Cousot's early papers for more on this and the Apron library if you want to play with it directly.

Finding variant functions is decidable when the variant functions are linear.  I couldn't find a complete characterization of the complexity of this, but "Termination of Linear Programs" by Tiwari has a section that discusses complexity.  See also "A Complete Method for the Synthesis of Linear Ranking Functions" by Podelski and Rybalchenko.  Also, Byron Cook has done work on leveraging abstract interpretation to help construct termination arguments.  See, for example, "Ranking Abstractions" and "Variance Analyses from Invariance Analyses".  These may give further insight into the relationship between partial correctness and termination.

Links:

http://www.csl.sri.com/users/tiwari/html/cav04.html
http://www7.in.tum.de/~rybal/papers/vmcai04-linear-ranking.pdf
http://www.dcs.qmul.ac.uk/~hyang/paper/esop08.pdf
http://research.microsoft.com/terminator/popl07a.pdf


Checking properties of matrices Given a sparse matrix $A$ in $\mathbb{Z}^{n\times n}$, how easily could one check whether a coefficient $\alpha_k$ of the characteristic polynomial $P_A$ of $A$ is equal to $0$ (without the need to compute $P_A$)? Are there any known deterministic/randomized algorithms for this task?

The Faddeev-Leverrier algorithm seems to be a good start to answer your question, since it reduces the computation of $\alpha_k$ to matrix multiplications and traces. It runs in polynomial time (even in NC) and I guess any efficient treatment of sparse matrix operation carries to this algorithm.

Oddly enough the wikipedia page about that exists only in French and German:

https://fr.wikipedia.org/wiki/Algorithme_de_Faddeev-Leverrier

I found this article in english explaining the method:

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1085-14.pdf


enumerating all connected induced subgraphs What is the complexity of enumerating all connected induced subgraphs from an undirected graph.

Also, Is the complexity of enumerating all maximal connected induced subgraphs the same?

It's not difficult to show that this is polynomial per subgraph, for the connected induced subgraphs. I don't know what you mean by a maximal connected induced subgraph; isn't that just a connected component? I also don't know what has been published on this problem.

One way to solve the problem is to define a tree structure on these subgraphs as follows: choose an arbitrary assignment of distinct weights to the edges of the input graph. Define the parent of a connected induced subgraph to be the graph formed by finding its minimum spanning tree, removing the leaf edge of maximum weight, and forming the induced subgraph of the remaining vertices. For a subgraph with only one vertex, define its parent to be the empty graph (which forms the root of the tree structure)

Reverse search (essentially, DFS of this tree) will then find each connected induced subgraph in time polynomial per subgraph. You can find the children of any node in the tree by trying all ways of adding one vertex and checking which of them would form the heaviest leaf of the MST of the augmented subgraph; finding all the children of a single node takes polynomial time, which is all that's required to make this work.

The family of connected subsets of vertices of a graph, with two subsets considered adjacent to each other if they differ in the addition or removal of a single vertex, forms a partial cube structure (see the first example in my book Media Theory) and similar reverse search ideas can be used to list all states in any such structure (detailed later in the book).


Type-theoretic interpretation of Skolemization What is the type-theoretic interpretation / equivalent of Skolemization?

Skolemization converts some formula into Skolem normal form. The two formulae are equisatisfiable with each other.

Or, to say it in type-theoretic terms: There is a program having some type iff there is a program having this type in Skolem normal form.

How do these programs relate to each other?

Skolemization corresponds to the so-called type theoretic axiom of choice, which is briefly discussed in section 1.6 of the HoTT book.

This provides an equivalence along which we can swap $\Sigma$ and $\Pi$ types. Assuming $A : U$, $B : A \to U$ and $C : \prod_{a : A} B\,a \to U$, we have an equivalence:

$$ac : \Big(\prod_{a : A}\sum_{b : B\,a}\,C\,a\,b\Big) \simeq \Big(\sum_{(b : \prod_{a : A} B\,a)} \prod_{a : A} C\,a\,(b\, a)\Big)$$

The proof of this very simple, e.g. in Agda we have the following (proving isomorphism instead of equivalence for simplicity now):

open import Data.Product
open import Function
open import Relation.Binary.PropositionalEquality

iso : Set → Set → Set
iso A B =
  ∃₂ λ (f : A → B)(g : B → A) → (∀ x → f (g x) ≡ x) × (∀ x → g (f x) ≡ x)

ac : ∀ {A : Set}{B : A → Set}{C : ∀ a → B a → Set}
     → iso ((a : A) → Σ (B a) λ b → C a b)
           (Σ ((a : A) → B a) λ b → (a : A) → C a (b a))
ac = (λ f → proj₁ ∘ f , proj₂ ∘ f)
   , (λ {(b , c) a → b a , c a})
   , (λ _ → refl)
   , (λ _ → refl)

Going from left to right along the equivalence, we convert an existential variable into a function abstracting over the universal variable in scope. We can also use this iteratively, to move all $\Sigma$-s from a mixed-quantifier type to a prefix.

From a more operational perspective, this corresponds to lambda lifting, a program transformation used in compilers, which lifts definitions into an outer scope by adding extra function parameters for bound variables.


Algorithm for inverting a bijective function. Does there exist a generalized algorithm for finding the inverse function of an arbitrary bijective function?

In order for this algorithm to be
useful, it must eventually halt once
the correct answer is found.
Beyond the requirement that it must find the solution eventually, there is no time constraints on the time it takes to find or run the inverse function (with that in mind, something better than bruteforce guess-and-check, would be more interesting).

For example, if such a generalized algorithm existed it could solve for a decompression algorithm for a lossless compression algorithm.

EDIT:

I really liked Evgenij Thorstensen assumptions as they summed up my question fairly well.

Assumptions

Computable bijective functions over a fixed alphabet (say {0, 1})
Represented by a deterministic Turing machine (DTM) that computes it
The proposed algorithm would be able to solve for a DTM that would invert the original bijective function output.

Another shot at explaining it:

Given: Bijective function F that maps X from domain A onto Y from domain B.

Proposed algorithm should be able to solve for a Bijective function G that maps Y from domain B onto X from domain A, such that G(F(X))=X and F * G = I where I is the identity function.

There have been papers on automatically converting algorithms for bijective functions into algorithms for the inverse function; my own first conference paper was one such. But the class of algorithms that can be inverted in this way is severely limited, as the other answers already suggest.


Deciding if a wildcard string is completely matched by another wildcard string in a set Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the same length. These are standard UNIX wildcards; 10??1 matches 10011, 10111, etc -- a ? matches a 1 or a 0 in that position. If $v$ and $w$ are wildcard strings, then we write $v \leq w$ if every string matched by $v$ is also matched by $w$.

The problems: given a set $S$ of wildcard strings, and a query $v$ (also a wildcard string), does there exist a $w \in S$ such that $v \leq w$? And if not, can we add $v$ to $S$ efficiently?

Here's the obvious $O(\frac{k}{m}n)$ solution (where $k$ is the size of the strings, $m$ is the word size of RAM (usually 32 or 64)): go through each element of the list and test the condition (which can be done in 2 or 3 operations using bit-twiddling). Also test if $v \geq w$ holds for any item $w$ while we're scanning. If $v$ fails our test, then add $v$ to the set, and remove the $w$'s we marked.

But that's not fast enough. It'd be really cool if there was a $O(\log n)$ solution, or, in a perfect world, complexity similar to a radix tree ($O(k)$). It's also OK for the queries to be approximately correct: that is, if $v \leq w$, then return yes or no; but if the condition doesn't hold definitely return no.

Although this doesn't help the worst case complexity, you can assume that all elements in $S$ are bounded by a wildcard string; that is, there exists some $v$ such that for all $w \in S$, $v \geq w$.

Ideas I've tried

Wildcard strings form a join-semilattice. We could have an n-ary tree that holds wildcard strings; the leaves would be wildcard strings, and the branches would represent the join of all of the children. If the query and the join are incomparable, then we don't have to waste time trying to compare with all of the children of that branch. Furthermore, if we make an update, and the update happens to be greater than a join, we can simply delete the whole branch. Unfortunately, this is still $O(n)$ in the worst case, and we don't always find the "best" joins to make when scanning through the tree to add elements.
One could form a radix trie of $S$. We know that $S$ is bounded by some wildcard string; assume that it is ?0?0. Then all of the branches of the trie only have to be on the 1st and 3rd bits of the strings. If the current bit we are branching on of the query is a 1, we have to check the ? and the 1 branches; if it is 0, we check the ? and the 0 branches; if it is ?, we only check the ? branch. Because we have to potentially take multiple branches, this doesn't seem very good (it is hard to update the trie for the same reason). Since matching is a very very quick operation, it hurts in comparison to the naive strategy to do a lot of traversing in a tree (following a bunch of pointers is much more expensive than doing some ORs and ANDs).

Related work

In the networking community, this problem manifests as "packet classification", here is a good survey of the algorithms and data structures known. Unfortunately, the assumption is almost always made that the wildcard strings only match prefixes, and the query is a tuple of such strings. Of course, we can always convert a general wildcard string to meet these criteria: 1?00?1?? is (1, ?, 0, 0, ?, 1, ?, ?). This would not be efficient, though. The other assumption made is that these tuples are associated with a "color", and querying should return the color (not just that it matched). This makes the problem much harder, because we have to order the tuples (or else it is ambiguous which of (0, ?) and (?, 1) matches (0, 1)).
In the algorithms community I've found a lot of results related to finding substrings that match with "don't cares". This is a considerably harder problem, and I can't really make use of any of the techniques.

In conclusion

Thanks for any help!

How about using a finite-state automaton? The language $S$ is finite and therefore regular. Even after the transformations below it will still be regular. So after the usual steps to convert the regular expression into a deterministic finite-state automaton, you will have a recognizer for what you want that operates in $O(k)$ time. Hopefully this idea will still be workable if there are bugs in what is proposed below.

The wrinkle is how to deal with the wildcard operator: ?. A wildcard in a wildcard string matches a 0 or 1 in a test string. But since we're trying to recognize wildcard strings, a wildcard in a wildcard string matches 0, 1, or ? in another wildcard string. This set is still regular, so we transform every occurrence of ? to the regular expression (0|1|?) where the vertical bar is the usual alternation operator. So if your whole set $S$ is {10??1, 0?1?0}, the resulting regular expression will be (10(0|1|?)(0|1|?)1 | 0(0|1|?)1(0|1|?)0)

As for adding strings to the machine, there's some recent work on changing a finite-state automaton incrementally. See this paper by Daciuk et al: "Incremental Construction of Minimal Acyclic Finite-State Automata".

Does this help?


Is infinitary logic a logic in the sense of Gurevich? Gurevich provides an exact definition of what Logic capturing PTIME is.

An abstract logic $L$ consists of

a set of $L[\tau]$-sentences for each vocabulary $\tau$,
and a mapping that maps a property $\mathcal{P}_\varphi$ to each $L[\tau]$-sentence $\varphi$.

An abstract logic $L$ captures polynomial time on $\mathcal{C}$ if

for every $\tau$, $L[\tau]$ is decidable,
for every property $\mathcal{P}$ of $\tau$-structures that is decidable in polynomial time, there is a $\varphi \in L[\tau]$ which defines $\mathcal{P}$ on $\mathcal{C}$,
for every vocabulary $\tau$, we can compute an algorithm which decides $\mathcal{P}_\varphi$ for every $\varphi \in L[\tau]$.

  Infinitary logic $\mathcal{L}_{\infty \omega}$ is an extension of
  First-Order Logic s.t. if $X$ is set then  both

  $$ \bigvee_{\phi \in X} \phi \textrm{ and } \bigwedge_{\phi \in X} \phi$$

  are formulars. $\mathcal{L}^k_{\infty \omega}$ is infinitary logic
  with only $k$ distinct variables.

Apart from the question for which classes $\mathcal{C}$ of finite(!) structures, $\mathcal{L}_{\infty \omega}^k$ describes all polynomial time decidable properties, I want to know if $\mathcal{L}_{\infty \omega}^k$ is a logic in that sense.

First Question: Is $\mathcal{L}_{\infty \omega}^k[\tau]$ decidable for each $\tau$? We need an encoding for each $\varphi \in \mathcal{L}_{\infty \omega}^k[\tau]$ and a Turing Machine to decide whether $X$ is a set. Is it possible to provide a finite encoding for each $\varphi$?

Problem: If we want to define a Turing Machine which decides whether $\varphi \in \mathcal{L}_{\infty \omega}^k[\tau]$ we need a finite representation of $\varphi$. Approach: Let $\mathsf{FO}[\tau]$ be the set of all first order sentences over $\tau$. It is not possible to define a finite code for each $X \subset \mathsf{FO}[\tau]$ over a finite alphabet like $\{0,1\}$. $X$ is countable. However, $|\mathcal{P}(\mathsf{FO}[\tau])| > |\{0,1\}^*|$. Hence, there can be no bijective mapping from $\mathcal{P}(\mathsf{FO}[\tau])$ to $\{0,1\}^*$ (or any code with finite alphabet).

Second Question: The other thing is a model checking algorithm. Is there a model checking algorithm for $\mathcal{L}_{\infty \omega}^k[\tau]$ on each finite $\tau$ for classes $\mathcal{C}$ of finite structures? Can we make assertions regarding the run time? The basic ideas that on a finite structure it is sufficient to model check a finite $X' \subset X$ to decide.

Any ideas? Any references?

First question: A set $M$ is decidable if there is a Turing Machine which halts on all inputs and accepts all inputs $x$ with $x \in M$.

We try to encode $\bigwedge_{\phi \in X} \phi$ for arbitrary sets of $\mathsf{FO}[\tau]$-formulars $X$. Since, $\mathcal{P}(X)$ is uncountable there can be no code with finite alphabet. Hence, there can be no Turing Machine recognizing $\mathcal{L}_{\infty\omega}[\tau]$ for each $\tau$ (even for empty $\tau$). Hence, the syntax is undecidable.

Second question: Given a code which translates a Deterministic Turing Machine (DTM) $T$ into a $\tau$-Structure $\mathcal{T}$. We can write a $\mathsf{FO}$-formular $\varphi_k$ with

$$ \mathcal{T} \models \varphi_k \Leftrightarrow \textrm{ The DTM $T$ holds after $k$ steps on $\varepsilon$.}$$

If we reassign variables (forgot the previous states of the Turing Machine) we can modell this $\varphi_k$ with constant, finite number $m$ of variables which does not depend on $k$.

Hence,

$$ T \in H_\varepsilon \Leftrightarrow \mathcal{T} \models \bigvee_{k \in \omega} \varphi_k \in \mathcal{L}_{\infty \omega}^m.$$

Where $H_\varepsilon$ is the special Halting Problem. Consequently, the Model Checking Problem for $\mathcal{L}_{\infty \omega}^m$ is undecidable for sufficiently large $m$.


Decomposing a submodular function Given a submodular function $f$ on $\Omega=X_1\cup X_2$ where $X_1$ and $X_2$ are disjoint and $f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$. Here $f_1$ and $f_2$ are submodular on $X_1$ and $X_2$ respectively.

Here $X_1,X_2,f_1,f_2$ are unknown and only a value query access to $f$ is given. Then is there a polytime algorithm which finds $X_1$. If there are multiple choices for $X_1$ any of them should be fine.

Some thoughts. If we can find any two elements $t_1,t_2$ such that both either belong to $X_1$ or belong to $X_2$ then we can merge them and proceed recursively. But it is not clear how to implement such a step.

Take an arbitrary element $e \in \Omega$. If $f(e) = f_{\Omega-e}(e)$ then $e$ is not affected by the rest of the elements so we can choose $X_1 = \{e\}$ and $X_2 = \Omega-\{e\}$. Otherwise let $X$ be an inclusion-wise minimal subset of $\Omega-e$ such that $f(e) > f_X(e)$. Then $X \cup \{e\}$ should be in the same partition. If $X \cup \{e\} = \Omega$ we conclude that there is no desired partition, otherwise we shrink this set into a single element and recurse.


Locating a point inside a union of simple polygons I have a set of polygons (convex, concave – non-convex, not self-intersecting) in a plane. There may be intersections between polygons.

Polygon is defined by points (cartesian coordinate system).

Please see the example image:

There is 2 polygons: the first is { A, B, C, D } and the second is { E, F, G }.

Question

How can I detect bounding "face" by the given point?

Solution for point 1 is { A, B, the intersection between |BD| and |EF|, F, the intersection between |FG| and |DC|, C, A }.

My idea

I tried some alghoritmus for boolean operations on polygons, but I think that this is not the right approach.
I can insert intersection points into original polygons and subdivided the original edge. After that, there is no intersection between polygon's edges.
Can I use some graph theory algorithm or algorithm for space partitioning?

You can consider every polygon one by one. You should update the answer after adding each polygon. For every polygon, first consider whether the polygon enclose the point. If yes, consider the every edge. Finding the edges going into the current minimum polygon (your current answer) and going outside. Then you can find all intersection and edges which generates your new answer. Iterate this procedure you can finally get the final answer


Perfectly matchable edges in a bipartite graph Consider the following problem:

Given a bipartite graph $G = (V, E)$, an unmatched edge is one that does not appear in any perfect matching. Design an algorithm to find all unmatched edges. (assume |V| = n and |E| = m)

There is an $O(m + T(m, n))$ algorithm to solve this problem [1, Web exercise 36]. Where $T(m, n)$ is the time complexity of the best algorithm for finding perfect matching in a bipartite graph $G$. I want to get a reference to the research paper/work where the algorithm was proposed, for citation.

[1] http://algs4.cs.princeton.edu/42directed/

It's a consequence of Dulmage-Mendelsohn decompositions.


algorithm to find a point among n points in plane to minimize the sum of distances I have an algorithm problem here. It is different from the normal Fermat Point problem or Geometric Median problem.

Given a set of $n$ points in the plane, I need to find which one can minimize the sum of distances to the rest of $n-1$ points.

Ideally I'd like to have an algorithm for any distance; but giving a nice solution for the usual Euclidean distance is also fine.

Is there any algorithm you know of run less than $O(n^2)$?

Thank you.

Since you have to compare a sum of square roots, it is not clear/unknown if this problem is in NP. Otherwise, if you assume you can compute sum of square roots and compare them, then I am unaware of an algorithm that works in faster than quadratic time. For approximation, you can just approximate the 1-median using known algorithms in linear time, and then just take the closest point  to this center. This would give you a constant approximation. A better approximation can be had by working somewhat harder.


Measurable language which is not $\omega$-regular Let $\Sigma$ be a finite alphabet and let $\Sigma^\omega$ be the set of all infinite words over $\Sigma$. Consider
$$
  d(x,y):=2^{-\min(n \in \Bbb N_0:x_n\neq y_n)}
$$
to be the metric on $\Sigma^\omega$ which makes the latter being the Cantor space. Denote by $\mathscr B(\Sigma^\omega)$ the Borel $\sigma$-algebra of this space, and let's call its elements measurable languages. It follows from Proposition 6 here that any $\omega$-regular language is measurable. I am looking for an example of a measurable language which is not $\omega$-regular, so any hints are appreciated.

A simple class of examples can be found by considering singleton languages $\{w\}$. These are measurable (Let $C_n(w)$ be the set of words agreeing with $w$ up to the $n$-th letter, then $\{w\}$ is the intersection of all $C_n(w)$). However, unless $w$ is eventually periodic, the language is not $\omega$-regular.

For a concrete example, consider the word $w=ababbabbba\dots$. If $w$ is accepted by a nondeterministic Büchi automaton $A$ with $k$ states, then while parsing the $n$-th block of $b$s, with $n>k$, $A$ needs to visit some state twice, so we can construct another word accepted by $A$ by pumping this block suitably. Therefore no automaton recognizes $\{w\}$.


To what extent can the mathematics of Reals be applied to Computable Reals? Is there a general theorem that would state, with proper sanitization,
that most known results regarding the use of real numbers can actually
be used when considering only computable reals? Or is there a proper
characterisation of results that remain valid when considering only
the computable reals? A side question is whether results concerning
computable reals can be proved without having to consider all real, or
anything that is not computable. I am thinking specifically of
calculus and mathematical analysis, but my question is in no way
limited to that.

Actually, I suppose there is a hierarchy of computable reals
corresponding to the Turing hierarchy (Is that correct?). Then, more
abstractedly, is there an abstract theory of real (I am not sure what
the terminology should be), for which a number of results could be
proved, that would apply to the traditional real numbers, but also to
computable reals, and to any level of the Turing hierarchy of
computable reals, if it exists.

Then my question could possibly be stated as: Is there a
characterization of results that will apply in the abstract theory of
reals when they have been proved for traditionnal reals. And, could
these results be proved directly in the abstract theory, without
considering traditional reals.

I am also interested in understanding how and when these theories of
reals diverge.

P.S. I do not know where to fit this in my question. I realised that a good deal of the mathematics on the reals have been generalized with topology. So it may be that the answer to my question, or part of it, can be found there. But there may also be more to it.

The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 and Defintion 11.2.10 of the HoTT book.)

The following theorem is valid in any topos (a model of higher-order intuitionistic logic):

  Theorem: There is a Cauchy-complete archimedean ordered field, and in fact any two such fields are canonically isomorphic.

Moreover, in intuitionistic logic (not to be confused with intuitionism) we can do a lot of real analysis (sequences and limits, derivatives, integrals, continuity, uniform continuity, etc.) which is then valid in any topos. If we take the topos of sets we get the usual real analysis. By taking a different topos we get a different kind of real analysis – and there is a topos which yields precisely the computable reals and computable real analysis.

This of course is the effective topos, in which the real numbers are the computable reals (speaking vaguely, the reason for this is that the effective topos is constructed in such a way that everything in it is automatically computable). The answer to your question is

  Definitions, constructions, and theorems in intuitionistic real analysis are automatically translated to definitions, constructions and theorems about computable reals when we interpret them in the effective topos.

For instance, the theorem "every uniformly continuous map $f : [0,1] \to \mathbb{R}$ attains its supremum" is intuitionistically valid. When we interpret it in the effective topos we get the corresponding version for computable maps on computable reals which are computably uniformly continuous.

You also ask about the "divergence" between real analysis and its computable version. The answer is that results which rely on the law of excluded middle or the axiom of choice (although countable choice is ok) are not intuitionistic, and therefore cannot be validated in the effective topos. However, we should note that (contrary to popular opinion) most analysis can be done intuitionistically.

The effective topos is just one of many realizability toposes. When we interpret intuitionistic analysis in other realizability toposes we get alternative models of real number computatability, including computation with oracles which you allude to. The "relative Kleene function realizability topos" (whatever that is) gives the so called Type II computability on reals in which computable maps operate on all reals, not just the computable ones.

I tried to explain this once in the notes "Realizability as the Connection between Computable and Constructive Mathematics", and before that in my Ph.D. thesis.


Comparison-based data structure for finding items Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$?

I really think there isn't, so a proof that there is none is also welcomed.

Here's a proof that it's impossible. Suppose you could build such a data structure. Build it. Then choose $n/\log n$ items at random from the list, add $\epsilon$ to each of them, where $\epsilon$ is smaller than the difference between any two items on the list, and perform the queries to check whether any of the resulting items is in the list. You've performed $O(n)$ queries so far.

I would like to claim that the comparisons you have done are sufficient to tell whether an item $a$ on the original list is smaller than or larger than any new item $b$. Suppose you couldn't tell. Then, because this is a comparison-based model, you wouldn't know whether $a$ was equal to $b$ or not, a contradiction of the assumption that your data structure works.

Now, since the $n/\log n$ items you chose were random, your comparisons have with high probability given enough information to divide the original list into $n/\log n$ lists each of size $O(\log n)$. By sorting each of these lists, you get a randomized $O(n \log \log n)$-time sorting algorithm based solely on comparisons, a contradiction.


Maximum flow using Ford-Fulkerson and DFS This question is about the time complexity of the Ford-Fulkerson
maximum flow algorithm when using DFS to find augmenting paths.

There is a well-known example showing that using DFS one can need a
linear number of iterations in the maximum flow, see for instance the
Wikipedia page linked to above.

However, I'm not really convinced by this example: a standard DFS
implementation would not exhibit the behaviour of alternating between B and C as
first node of the path (using the vertex names from the Wikipedia page).

So, let us impose the very natural condition that whenever the DFS visits a node
$u$, it always examines the neighbors of $u$ in the same order.  Are there
still examples for which FF with DFS uses a large number of
iterations?

As a variant, suppose that we have the additional property that the
different orderings of neighbors are consistent with some arbitrary
but fixed global ordering of the vertices.  Does that make a
difference?

This seems to me like a pretty basic question; I apologize in advance
if the answer is well-known but I am not an expert on flows and some
googling did not turn up anything.

Edit:
The answer turns out to be yes, there are still examples.  See Figure 2 of this paper.  In these examples FF with DFS take an exponential (in the number of vertices) number of iterations.  It seems easy to prove that this is tight, i.e., that the number of iterations are always bounded by $2^{O(n)}$ (regardless of the values of the capacities).

If adjacency lists are fixed in advance then DFS always terminates (even if there are irrational capacities).

See Dean, Goemans, Immorlica -- Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data.


Algorithmic problem classification I'm trying to classify the following problem:

  I have $N$ empty boxes ($n_i$ is the volume of the $i$-th box, $1 \leq i \leq N$) and $M$ divisible items ($m_j$ is the volume of $j$-th item, $1 \leq j \leq M$). The total volume of all boxes is exactly equal to the total volume of all items. I need to find a distribution of items among boxes which minimizes the number of item divisions.

I suppose this problem is NP-complete, and is some kind of set coverage problem, but I can't find appropriate variation of it.

The decision version of your problem is NP-complete. The NP-complete 3-Partition problem is reducible to your problem (input has only three boxes having the same volume with zero divisions of items).


A generalization of edge cover Suppose we are given a general (connected) undirected graph $G = (V, E)$. An EDGE COVER asks a set $S\subseteq E$ of the minimum number of edges, such that each vertex $v\in V$ is incident to at least one edge $s\in S$. Note that this is solvable in polynomial time.

Now I'd like to generalize this problem to find a set $S$ of vertex-induced connected subgraphs that covers each vertex $v\in V$, but each subgraph $s\in S$ consists of at most (or exactly) 3 vertices (The goal is still to minimize $|S|$). Of course, the topology of a connected subgraph with 3 vertices is fixed (the only way is to form a line with 2 edges connecting them). In other words, we need to find a minimum path cover but the length of each path is at most (or exactly) 3.

Is this problem still poly-time solvable or it's NP-hard? Is it related with 3d matching or steiner tree?

This problem is known to be NP-complete (since the 1970s).
Dyer and Frieze established its NP-hardness even for the highly restricted special case where the graph $G$ is planar and bipartite:

  Martin E. Dyer, Alan M. Frieze:
  On the complexity of partitioning graphs into connected subgraphs.
  Discrete Applied Mathematics 10(2): 139-153 (1985)


Reduction of a language to a shorter equivalent I'm new to Theoretical Computer Science, and my textbook says that it is easy to verify that the following language
\begin{array}{l}
L_{1}=A^{*} \cdot\{b\}-\left(A^{*} \cdot(A-\{a\}) \cdot A^{*} \cdot\{b\}\right) \\
L_{2}=A^{*}-\left(A^{*} \cdot(A-\{b\}) \cdot A^{*}\right) \\
L_{3}=L_{1} \cdot L_{2}
\end{array}
is equivalent to $L_{1}=a^{*} \cdot b$, $L_{2}=b^{*}$, and $L_{3}=a^{*} \cdot b^{+}$.
However, I don't seem to understand the process of reducing the languages. Can someone easily explain it to me?

Think set theory.
We have for L1
$$ (A - {a}) \subset A^* $$
$$ A^*.(A-{a}).A^* \subset A^* $$
Then
$$ S1 = A^*.\{b\} $$
$$ S1 = A^*.(A)^*.A^*.\{b\} $$
$$ S2 =  (A^*.(A-{a})).A^*.\{b\} $$
$$ S1 - S2  = a^*b$$
Basically you removed everything from A* that does not have a, then you end up with a*.
Same argument goes for L2.
Then:
$$ L1.L2 = a*.b.b* = a^*.{b+b*} = a.b^+ $$
Note: This does not "reduce" the languages, but help you see how to arrive to the answer.
You may have to brush up on the operations of regular expressions, but the general logic should be a bit similar, if you realize that A* is a prefix closure and can be  written in many forms.


Status on circuit lower bounds for polylog-bounded depth circuits Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ function is not computed by $AC^{0}[q]$", where $AC^0[q]$ is the class of languages decidable by non-uniform, constant depth, polynomial size, unbounded fan-in AND, OR, NOT and modulo $q$ gates, where $\gcd(p,q)=1$. However, getting concrete lower bounds results on polylogarithmic depth circuits seems to be out of reach by using classical methods like restricting inputs and approximating polynomials on finite fields.

I know a STOC'96 paper which leads to geometric complexity theory and which shows that efficient parallel computing using operations without bit-wise ones cannot compute the min-cost-flow problem.

This means that in certain limited settings, we can prove $NC$ lower bounds for some $P$-complete problem.

First, are there other methods or techniques that may be plausible approaches for proving polylogarithmic depth circuit lower bounds?

Second, how useful is the following statement for the theory community?

The size of an $NC$ circuit computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ is at least $l$, where $l$ is some mathematical quantity depending on the hardness of the target function $f$. The value of $l$ may be, for example, a combinatorial quantity like discrepancy, a linear algebraic quantity like the rank of certain type of matrix over a field, or some entirely new quantity which has not previously been used in complexity theory.

On techniques for proving poly-log circuit-depth lower bounds, all current approaches work under restricted settings.
Like, in the work leading to GCT that you mention, the lower bound applies to a restricted PRAM model without bit operations.

Under another restriction, which is the monotone restriction for monotone boolean functions, there is a Fourier-analytic (or enumerative-combinatorial) approach for proving monotone circuit-depth lower bounds, in my joint work with Aaron Potechin (ECCC and STOC).
This improves on an earlier result by Ran Raz and Pierre McKenzie, which extends the communication game framework of Mauricio Karchmer and Avi Wigderson concerning circuit-depth.

Another line of research to extend the Karchmer–Wigderson game was proposed as a referred communication game by Scott Aaronson and Avi Wigderson, whose extension to a competing-prover protocol is suggested as an approach to separate NC from P by Gillat Kol and Ran Raz (ECCC and ITCS).

Apart from studying the syntactic restriction of monotonicity, there is an approach to study a semantic restriction related to pebble games (called thrifty branching programs) by Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam.
There is a strong lower bound under the thrifty restriction by Dustin Wehr, matching the best known upper bound for P-complete problems.
These results concern deterministic space complexity, which lower bounds parallel time or circuit-depth by known simulation results (e.g. since $\text{AlternatingTime}[t] \subseteq \text{DeterministicSpace}[t]$).

About the question relating the size and depth of circuits, the following approach may be related.
Richard Lipton and Ryan Williams show that, given a sufficiently strong lower bound on depth (i.e. $n^{1-O(1)}$), a weak size lower bound (i.e. $n^{1+\Omega(1)}$) can separate NC from P.
This result follows from a size-depth trade-off argument based on block-respecting simulations.
An earlier result on trading depth for size is due to Allender and Koucký based on the idea of self-reducibility, but it studied smaller complexity classes like NC$^1$ and NL.

Note that among the above mentioned approaches, some of them consider both the size and the depth of circuits, while other approaches consider only circuit-depth.
In particular, the semi-algebro-geometric approach of Mulmuley, the competing-prover protocol approach studied by Kol–Raz, and the size-depth trade-off approach of Allender–Koucký  and Lipton–Williams all concern both the size and the depth of circuits.
The results in Chan–Potechin, Raz–McKenzie, Cook–McKenzie–Wehr–Braverman–Santhanam, and Wehr give circuit-depth lower bounds under restricted settings regardless of size.
Also, the referred communication game of Aaronson–Wigderson concerns only circuit-depth.

It is still consistent with our knowledge that some P-complete problem cannot be computed by circuits of small depth (i.e. $\log^{O(1)}n$), regardless of size.
If size does not matter for small depth circuits (of bounded fan-in), then perhaps it makes sense to focus more on circuit-depth, than to focus on the size of small depth circuits.


Runtime of a TM enumerator Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)?

For simplicity let's say the string is binary,
the obvious answer is exponential to input length.
But the question is can we do better?

(Sorry if I mixed up some notations,
been a while since my Theory of Computation class.)

I somehow feel like I can make something out of

Are runtime bounds in P decidable? (answer: no)

but can someone please give a hint?

If you weaken the time bound very slightly from linear, the answer is definitively no. Probably a more delicate construction will work for linear time.

Let $f(n)$ be any monotone increasing time-constructible function $\geq n$. Then there is a language $L \in \mathsf{DTIME}(n^2)$ (in fact, in time $n f^{-1}(n)$, e.g. when $f(n)=2^n$ this is $n \log n$) such that any enumerator for that language requires $f(n)$ delay between enumerating the $n$-th and $(n+1)$-st strings. In particular, $L = \{0^{f(m)} : m \geq 0\}$ has this property.

$L$ can be decided in time $n f^{-1}(n)$: if $x \neq 0^{n}$ then $x \notin L$. Otherwise, compute $f(1), f(2), \dotsc$ until $f(k) \geq n$. In fact, in the computation of $f(k)$, if the counter ever surpasses $n$, stop. This ensures that each computation of $f(i)$ takes at most time $n$. The largest $k$ for which such a computation needs to be done is $\lceil f^{-1}(n) \rceil$, giving the claimed runtime.

Finally, any enumerator for $L$ requires delay $f(n)$ between strings in the worst case. If the enumerator enumerates $L$ in lexicographic order, this clear because it takes time $f(n)$ to just write down the next string. If the enumerator is out of order finitely often, the same is still true after the finitely many. If the enumerator is out of order infinitely often, then infinitely often it is enumerating longer strings earlier than otherwise, hence takes time more than $f(n)$.


What's the difference between ADTs, GADTs, and inductive types? Might anyone be able to explain the difference between:

Algebraic Datatypes (which I am fairly familiar with)
Generalized Algebraic Datatypes (what makes them generalized?)
Inductive Types (e.g. Coq)

(Especially inductive types.) Thank you.

Algebraic data types let you define types recursively. Concretely, suppose we have the datatype

$$
  \mathsf{data\;list = Nil \;\;|\;\; Cons\;of\;\mathbb{N} \times list}
$$

What this means is that $\mathsf{list}$ is the smallest set generated by the $\mathsf{Nil}$ and $\mathsf{Cons}$ operators. We can formalize this by defining the operator $F(X)$

$$
   F(X) == \{ \mathsf{Nil} \} \cup \{ \mathsf{Cons}(n, x) \;|\; n \in \mathbb{N} \land x \in X \}
$$

and then defining $\mathsf{list}$ as

$$
   \mathsf{list} = \bigcup_{i \in \mathbb{N}} F^i(\emptyset)
$$

A generalized ADT is what we get when define a type operator recursively. For example, we might define the following type constructor:

$$
   \mathsf{bush}\;a = \mathsf{Leaf\;of\;}a \;\;|\;\; \mathsf{Nest\;of\;bush}(a \times a)
$$

This type means that an element of $\mathsf{bush\;}a$ is a tuple of $a$s of length $2^n$ for some $n$, since each time we go into the $\mathsf{Nest}$ constructor the type argument is paired with itself. So we can define the operator we want to take a fixed point of as:

$$
  F(R) = \lambda X.\; \{ \mathsf{Leaf}(x) \;|\; x \in X\} \cup \{ \mathsf{Nest}(v) \;|\; v \in R(X) \}
$$

An inductive type in Coq is essentially a GADT, where the indexes of the type operator are not restricted to other types (as in, for example, Haskell), but can also be indexed by values of the type theory. This lets you give types for length-indexed lists, and so on.


Computational query complexity of SQ-learning It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic learning by a computationally unbounded learner, and the sample complexity needed by a polynomial-time learner. (see, e.g. http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE or http://portal.acm.org/citation.cfm?id=301437)

These results seem to depend on encoding a secret in particular examples, however, and so don't naturally translate into the SQ-model of learning, where the learner just gets to query statistical properties of the distribution.

Is it known whether there exist concept classes for which information-theoretic learning in the SQ model is possible with O(f(n)) queries, but computationally efficient learning is only possible with Omega(g(n)) queries for g(n) >> f(n)?

I've asked (myself) this question a while ago. At least for learning with respect to a specific distribution there is a fairly simple example of a concept class that is information theoretically SQ-learnable but is NP-hard to SQ learn. Let \phi  a binary encoding of a SAT instance and y be its lexicographically first satisfying assignment (or 0^n is the instance is unsatisfiable). Now let f(\phi) be a function that over one half of the domain is the MAJ(\phi) and over the second half of the domain equals PAR(y). Here MAJ is the majority function over variables which are set to 1 in the string \phi and PAR(y) is the parity function over variables which are set to 1 in the string y. Let F be the class of functions obtained in this way. To SQ learn F over the uniform distribution U one only needs to learn majorities (which is easy) to find \phi and then find y. On the other hand, it is fairly easy to reduce SAT to SQ learning of F (to any accuracy noticeably greater than 3/4) over the uniform distribution. The reason for this, naturally, is that parities are essentially "invisible" to SQs and hence it is necessary to solve SAT to learn F.


Is there an official name for a notion of "reusably universal"? There are several different (probably inequivalent) notions of computational universality (see for example the last couple pages of http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf) and there is no consensus among experts about which notions are most correct (see for example http://cs.nyu.edu/pipermail/fom/2007-October/012148.html).

I'm trying to say something about a particular model of biomolecular computation.  I'd like to argue that it's "more universal" or "more usefully universal" than some other models, because you can construct a universal machine that runs a program and then deletes the input at the end and is ready to run another program.  Contrast this to, say, cellular automata, which can emulate any Turing machine, but then at the end of the computation, you've got a final, unchangeable configuration.  To emulate another TM, you need to define a completely separate CA.  So I'd like to say something is "reusably universal" if it behaves like your desktop, not a CA (i.e., can execute multiple programs without needing to recreate the universe).  Has this notion been formalized anywhere?

There has been work in the PL/systems community on the semantics and modelling of operating systems.  As you point out, what you are talking about is much like an OS: it does something, but is guaranteed (well, in the case of an OS, guaranteed-ish) to return to a "ground state."  The PL people may not have formalized your notion of reusably universal, but you might find some inspiration there.

Your formalization will have to capture the difference between "a universal machine that, after it runs with one input, if you replace the input with another input it is ready to go" and "a universal machine that, given a sequence of input programs, runs them in succession."  And of course, all reasonable notions of universal machine probably satisfy the latter requirement.  So it seems quite tricky...


What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH? Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (exponential time hypothesis). I cannot find this talk and am interested in said problems, for I want to look into quantum algorithms for this group of problems during the semester I'm beginning right now.

Virginia Vassilevska Williams lectured at a bootcamp (link to outline) at the Simons Institute, and presents what may be your memory in the introductory video. The whole workshop is worthwhile; the outline and links to videos of all talks can be found here.

She explains (starting at 42:30 in the video) that if there is a $O\left(n^{2-\varepsilon}\right)$ algorithm for some $\varepsilon>0$ for the Orthogonal Vectors problem, then the Strong Exponential Time Hypothesis (SETH) is false. This would not immediately imply $P=NP$, but it would show an $O\left(2^{n-\epsilon}\right)$ algorithm for every $k$-SAT, which would be better than what we have right now; right now we have algorithms which solve $k$-SAT in $2^{n-O\left(\frac{1}{k}\right)}$, so these algorithms tend to $2^{n}$ for large $k$.

The proof is originally by Ryan Williams, and is quite elegant; I do recommend the lecture.


Probability of random (in)finite graphs being isomorphic I once skimmed a paper which examined the probability of two (infinite) graphs picked at random being isomorph. The surprising result was that for two random infinite graphs this probability is quite high as opposed to the finite case. I remember it being referenced in the context of why so many graph invariants  - often claimed to be complete - work correct on most inputs.

I think the paper was published before the nineties.

From the comment: in the mathematical field of graph theory, the Rado graph [1], also known as the random graph or the Erdős–Rényi graph, is the unique (up to isomorphism) countable graph $R$ such that for every finite graph $G$ and every vertex $v$ of $G$, every embedding of $G − v$ as an induced subgraph of $R$ can be extended to an embedding of $G$ into $R$. As a result, the Rado graph contains all finite and countably infinite graphs as induced subgraphs.

In this note you can find other details, in particular: ... if we produce two random infinite graphs, then, with probability 1, they both have the extension property. Hence they are isomorphic (and also isomorphic to the Rado graph); in other words, any two random countably infinite graphs are isomorphic ...

[1] Rado, Richard (1964), "Universal graphs and universal functions", Acta Arith. 9: 331–340.


Number of solutions to the biclique cover problem Given a bipartite graph and the number bicliques K, how many ways exist to solve the biclique cover problem using K (possibly empty) bicliques?

Given a Graph $G=(V, E),$ it takes $O(|V|^3)$ delay and $O(2^|V|)$space to find all bicliques  in lexicographical order in $G$ [1]. There is no polynomial-delay enumeration algorithm for all bicliques in reverse lexicographical order unless P=NP [2].

Given a bipartite graph $G=(U, V, E),$ it takes $O((|U|+|V|)^2)$ delay with exponential space to find all maximal bicliques in $G$ in lexicographical order in $U$ [3].

[1] Vania M.F. Dias, Celina M.H. de Figueiredo, and Jayme L. Szwarcfiter.
“Generating Bicliques of a Graph in Lexicographic Order”. In:
Theoretical Computer Science 337.1-3 (June 2005), pp. 240–248. doi:
10.1016/j.tcs.2005.01.014.

[2] Wasa, Kunihiro. "Enumeration of enumeration algorithms." arXiv preprint arXiv:1605.05102 (2016).

[3] Alain Gely, Lhouari Nourine, and Bachir Sadi. “Enumeration aspects
of maximal cliques and bicliques”. In: Discrete Applied Mathematics
157.7 (Apr. 2009), pp. 1447–1459. doi: 10.1016/j.dam.2008.10.
010.


Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression? I understand that Disjoint Feedback Vertex Set (= looking for a solution $X$ of size $k$ given a solution $W$ of size $k+1$ s.t. $X \subseteq V \setminus W$ ) can be solved in time $4^k poly(n)$, see 4.3 here.

They also say FVS can be solved in $5^k poly(n)$ using iterative compression with the DFVS algorithm, but I can't see how.
If I start with a $2$-approximation, the total runtime would be $5^{2k} poly(n)$ by iterating over all subsets of a given solution as $W$ and executing the DFVS algorithm for each.

What is the starting point for the iterative compression and how does it lead to the given runtime?

I found the solution, it is also mentioned in the book in chapter 4.1.

We start by taking a subgraph with $k+1$ arbitrary vertices instead of the whole graph, so the whole vertex set is a $k+1$-solution. Then we do DFVS with every subset to obtain a $k$-solution. Finally we add another vertex from the original graph to our current subgraph (and current solution) and repeat.

Thus each step takes $5^kpoly(n)$ time and we do $n$ iterations.


MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates CMSOL is Counting Monadic Second Order Logic, i.e. a logic of graphs where the domain is the set of vertices and edges, there are predicates for vertex-vertex adjacency and edge-vertex incidence, there is quantification over edges, vertices, edge sets and vertex sets, and there is a predicate $\textrm{Card}_{n,p}(S)$ which expresses whether the size of $S$ is $n$ modulo $p$.

Courcelle's famous theorem states that if $\Pi$ is a property of graphs expressible in CMSOL, then for every graph $G$ of treewidth at most $k$ it can be decided in linear time whether $\Pi$ holds, provided that a tree decomposition of $G$ is given in the input.
Later versions of the theorem dropped the requirement that a tree decomposition is given in the input (because one can be computed with Bodlaender's algorithm), and also allowed optimization instead of merely decision; i.e. given a MSOL formula $\phi(S)$ we can also compute the largest or smallest set $S$ which satisfies $\phi(S)$.

My question concerns the adaptation of Courcelle's theorem to graphs of bounded cliquewidth. There is a similar theorem saying that if you have a MSOL1 which allows quantification over vertices, edges, vertex sets but not edge sets then given a graph $G$ of cliquewidth $k$ (with given clique-expression), for every fixed $k$ it can be decided in linear time whether graph $G$ satisfies some MSOL1 formula $\phi$; all references I have seen point to

  Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width by Courcelle, Makowsky and Rotics, Theory of Computing Systems, 2000.

I have tried to read the paper, but it is not self-contained with respect to the exact definition of MSOL1 and it is frankly hard to read. I have two questions with respect to what exactly is possible to optimize in FPT, parameterized by the cliquewidth of the graph, if a clique expression is given in the input.

Does MSOL1 allow the $\textrm{Card}_{n,p}(S)$ predicate for testing the size of a set modulo some number?
Is it possible to find a minimum / maximum size set $S$ which satisfies a MSOL1 formula $\phi(S)$ in FPT parameterized by cliquewidth, when the expression is given?

For both these questions I would also like to know what the correct references are to cite when claiming these results. Thanks in advance!

After asking around some more, it seems that the answers to 1) and 2) are both YES. Optimizing the cardinality of a set is possible in LinEMSOL (as mentioned by Martin Lackner); as I have been told, the existence of the cardinality predicates is no problem since they can be efficiently handled by finite-state tree automatons, which should follow (more explicitly than in the originally referenced paper) from On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width.


The originator of the fixed point theorem for DCPOs Pataraia proved in

  "A constructive proof of Tarski’s fixed-point theorem for dcpo's", presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997

that in a directed-complete partial order (dcpo) with a minimum element each monotone map has a fixpoint. (For the purpose of this particular theorem, a directed set is a poset in which each finite subset is bounded from above, and a dcpo is a poset in which each directed subset has a supremum.) Dito Pataraia is mostly acknowledged for the new proof method rather than the theorem itself.

Who was the first to actually state and prove this theorem is any way? One can argue that the proof of Markowski's Theorem 9(i) in "Chain-complete posets and directed sets with applications" can be adapted to our situation. Still, the clear-cut statement of the aforementioned theorem is not present in Markowski's paper.

The non-constructive version of Pataraia's theorem is called the Bourbaki-Witt fixed point theorem. I learned it from Davey and Priestley's Introduction to Lattices and Order, and Wikipedia gives the following references:

Nicolas Bourbaki (1949). "Sur le théorème de Zorn". Archiv der Mathematik. 2: 434–437. doi:10.1007/bf02036949.
Ernst Witt (1951). "Beweisstudien zum Satz von M. Zorn". Mathematische Nachrichten. 4: 434–438. doi:10.1002/mana.3210040138.

However, as usual, some classically equivalent formulations of this theorem become distinguishable constructively. Andrej Bauer and Peter Lumsdaine have a very nice paper about this, On the Bourbaki-Witt Principle in Toposes, where they examine these issues in detail.


Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity Let $$f(c)=\min_{x \ge c} K(x)$$ where $K(x)$ is the kolmogorov complexity of $x$. Since $K(x)$ is always a natural number, there will always be a minimum. My question is, what is the growth rate of $f$? We know that $$f \in \mathcal O(1) + \log c$$ since $f(c)\le K(c) \in \mathcal O(1) + \log c$. We also know $f$ is increasing, since if $c_1 \ge c_2$, then $\min_{x \ge c_1} K(x) \ge \min_{x \ge c_2} K(x)$. We also know that $$\lim_{c\to\infty}f(c)=\infty$$ since otherwise a finite number of programs would be able to generate arbitrarily large outputs.

Can we get a tigher bounds on $f$? What is $f$'s growth rate?

As commenters @Lwins and @SashaNikolov have already stated, it is non-computably hard to compute a function as slow-growing as $f$. (So no really humanly comprehensible rate can be given.)

Namely, suppose we just have one direction of your equality: $f(c)\le\min_{x\ge c} K(x)$, but suppose $f$ does goes to infinity monotonically.

Then $x\ge c$ implies $K(x)\ge f(c)$. So given $n$, if we find $c$ with $f(c)\ge n$ then $K(c)\ge n$. So letting $F(n)=c$ we have a function $F$ with $K(F(n))\ge n$ for all $n$.

But according to Theorem 4.1 of my paper with Merkle and Stephan, this allows us to compute a diagonally non-computable function with finite range, i.e., it allows us to compute a complete extension of Peano arithmetic.


Which definition of asymptotic growth-rate should we teach? When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class:
$$
f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).
$$
Perhaps we even give the whole list with all its quantifiers:

$f = o(g) \mbox{ iff } (\forall c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$
$f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$
$f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$.

However, since these definitions are not so easy to work with when it comes to proving even simple things such as $5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$, most of us quickly move to introduce the "trick of the limit":

$f = o(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is $0$,
$f = O(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $+\infty$,
$f = \Theta(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is neither $0$ nor $+\infty$,
$f = \Omega(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $0$,
$f = \omega(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is $+\infty$.

My question is:

Would it be a big loss for teaching an undergraduate algorithms class to take the limit conditions as the definitions of $o$, $O$, $\Theta$, $\Omega$, and $\omega$? That's what we all end-up using anyway and it seems pretty clear to me that skipping the quantifier definitions makes everybody's life easier.

I would be interested to know if you have encountered some convincing natural case where the standard $c,n_0$-definitions are actually required, and if not, whether you have a convincing argument to keep the standard $c,n_0$-definitions upfront anyway.

I prefer teaching the original definition with quantifiers.

IMO, humans generally have trouble in understanding formulas and definitions with more than two alternation of quantifiers directly. Introducing new quantifiers can clarify what the definition means. Here, the last two quantifiers just mean "for all sufficiently large n", introducing this kind of quantification can help.

The pictures I draw for explaining these concepts match better with the quantifier versions.

I think the limit simplification is useful for engineering student who are only interested in computing the growth rate, but won't be as useful for computer science students. In fact, using this simplification can cause more harm than good.

This idea is similar to suggestion that we use the rules for computing derivatives (of polynomials, exponentiation, ..., chain rule, ...) in place of the epsilon-delta definition of it, which IMHO is not a good idea.


What is the current state of the art in black-box grammar induction? Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's Grammatical Inference book, and looking through previous papers). What is the current bound on inducing a Context Free Grammar given unstructured (non parenthesized) input?

In particular, I would like to know the community's opinion on the paper by Bastani et al. Synthesizing Program Input Grammars. How it compares to existing work. Does it improve the algorithmic bounds?

de la Higuera's book focuses mostly on the classical theory of Angluin style learning of finite state automata and related results. This theory has been lifted to the class of context free grammars and beyond to multiple context free grammars etc. using what is called "distributional learning" which in its modern form started with Clark & Eyraud paper in JMLR 2007 (I was the first author). The most recent papers in this line of research are  Chihiro Shibata, Ryo Yoshinaka:
Probabilistic learnability of context-free grammars with basic distributional properties from positive examples. Theor. Comput. Sci. 620: 46-72 (2016) which looks at learning when the samples are generated by a PCFG.
There are analogues of the basic Angluin results using membership queries etc as well, and results for strong learning where you want to recover a CFG which generates the same trees as the target grammar (Learning Trees from Strings, Clark JMLR 2013).
(Apologies for the self citations)

I wasn't familiar with the Bastani paper, but it seems to be a heuristic paper with no theoretical guarantees.


Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs I'm looking for problems which are known to be NPC for directed graphs but has a polynomial algorithm for undirected graphs.

I've seen the question regarding the other way around here “Directed” problems that are easier than their “undirected” variant, but I'm looking for for hardness on the directed side.

For example, Feedback edge set is known to be NPC on directed but polynomial time solvable on undirected graphs.

Which other natural problems have the same property?

The first problem comes to my mind is the 2-path problem (or more generally k-path problem). Given $(s_1,t_1)$ and $(s_2,t_2)$, find two disjoint paths from $s_1$ to $t_1$ and $s_2$ to $t_2$, respectively. The problem is NPC for directed graphs but polynomial-time solvable for undirected graphs (although not trivial).