Handbook of Logic in Computer Science - is it worth it?

The series is a wonderful resource, but I wouldn't recommend buying it when it is available in the library, unless you knew you were going to use it for many years to come. (I have too many expensive books on my shelf that are lovely to look at, but not used much.) Many articles and tutorials with comparable contents are available on the web. These are probably a better alternative for the moment, in my opinion.


CLRS's Fibonacci Heap size(x) analysis has a flaw?

In CLRS, $s_k$ is defined to be "the minimum possible size of any node of degree $k$ in any Fibonacci heap." Assuming your example data structure is a valid Fibonacci heap, your Fibonacci heap has a node of degree 2 with size 8 and a node of degree 3 with size 6. Thus, these are possible sizes that nodes of degree 2 and 3 can have but not lower bounds on their sizes.

Using Lemma 19.1 (as in the proof of Lemma 19.4), $s_2 = 3$ and $s_3 = 5$, monotonically increasing as CLRS claim.


I posted some quantum complexity theory project ideas at http://scottaaronson.com/blog/?p=471

(But beware, most of these are problems that have been open for years!  My suggestion for an undergraduate project would be to break off a chunk of one of the problems.)


Complexity of computing the order of a permutation group

The order of permutation groups can be computed in polynomial-time. In fact, I believe even in $\mathsf{NC}$ and also nearly linear Las Vegas time. See, e.g., the book by Seress.

For reference, subgroups of $S_n$ (and algorithms related thereto) are typically called "permutation groups" rather than merely "subgroups (of $S_n$)". So you can google "permutation group algorithms" etc.


Minimal non-negative linear combination of positive integers larger than a positive integer

This is a variant of making change with a given set of coins, for which the knapsack/dynamic programming algorithm seems to be the best that is known. E.g., http://www.algorithmist.com/index.php/Coin_Change


What is the underlying physical principle behind quantum fault tolerance in quantum computation?

I would encourage you to think of error correction not as entanglement-swapping, per se, but the stimulated dissipation of excitations from a carefully engineered Hamiltonian — not the Hamiltonian which governs the unitary evolution, but a different Hamiltonian in whose ground-state manifold one thinks of trying to keep the state of the system, by dissipating excitations into a system of low temperature. Then we can describe fault tolerance as the threshold at which the rate of stimulated dissipation is such that the probability of an uncontrolled spontaneous dissipation can be efficiently suppressed by any desired factor.

Against the role of entanglement — per se — in error correction

The picture of 'entanglement swapping' which you describe brings to mind the question of coherence, and the issue of the state of the computation being isolated from the environment: in the quantum circuit model, we would quite like (short of what transformations are being applied) for the state of the computation to be essentially closed off from the outside world. This is the classic catch-22 behind the engineering problem of designing a quantum computer: to be open to the environment only when you want it to be (because you are part of the environment), and to control when it is open to the environment (from within the environment). It invites us to think of the problem in terms of a double-bind. Furthermore, not all errors necessarily would manifest as entanglement with the environment: an environment which deterministically performs Pauli operations on each of our qubits in some order would not be entangling and would be just as bad from an error perspective as anything which did involve entanglement.

Error correction as a form of Hamiltonian engineering

An alternative view is that the error correcting process is a sort of dissipative process.

Each detectable error corresponds to a sort of excitation of the system — an event corresponding perhaps to a projector onto a partial error syndrome — and what we are attempting to determine is whether the state of the system has become "excited" because it has a substantial overlap with the 'signature' of some error due to interaction with an environment with non-zero temperature.

In the case of stabilizer codes, for instance, you could think of the Pauli generators $S_1, S_2, \ldots$ of the code as giving rise to projectors $P_j = \tfrac12(\mathbf 1 - S_j)$. The Hamiltonian is then $H = \sum_j P_j$, and the codespace is the ground state manifold — that is, the lowest-energy eigenspace: the zero eigenspace, i.e. the joint zero eigenspace of the projectors, as opposed to the joint +1-eigenspace that one often considers. The error syndrome is then a description of a collection of commuting excitations of the projectors $P_j$ representing energy contributions — the error-free syndrome corresponding to the highly degenerate ground-state manifold, $\mathrm{null}(H)$.
What we attempt to do is to measure the energy terms in the Hamiltonian frequently enough, not to mention accurately enough, to detect the excitations (errors). Then, we attempt to dissipate away these excitations (correct the errors) the dissipation process being the efficient transmission of the excitation (error) out of the state of the computation and into some auxiliary system.
Furthermore, we would like to do it quickly enough so that the system
does not accumulate too much error, and then spontaneously and uncontrollably dissipate the excitations. For the error correcting code to be useful, it has to encode a highly degenerate subspace: thus, the error-excitations which we are trying to dissipate are excitations of a highly degenerate Hamiltonian. Because of the degeneracy of the ground-state manifold, there is a risk that a spontaneous relaxation of an excited state to a ground state could give rise to a non-trivial transformation of the ground-state manifold: an uncorrectable encoded error.

In all of the above, entangled states will sometimes be involved, and one may think of codes such as the Shor 9-qubit code as exploiting entanglement (correlations in multiple bases of measurement) to represent a quantum analogue of a simple repetition code. But in all this, entanglement is an incidental feature of the more fundamental phenomenon of correlations of multi-qubit observables representing excitations (or lack of them) in a physical process. That is, the role of entanglement here is the same as in many-body systems: it just so happens that the ground states of Hamiltonians may be entangled, but the mere presence or absence of entanglement is not what makes the states ground-states.

Competing dissipation processes

Above, I talk about spontaneous versus stimulated dissipation. However, this is a distinction of engineering, not of physics: the fact that the 'stimulated' process is under our control is not relevant from a physical perspective. Physically, we merely have two interaction/dissipation processes with the computational system: an uncontrolled 'noise' process with a bath, and a controlled dissipation process which we might think of as happening with a cold reservoir (corresponding to the ancillas which we prepare to aid with the error correction process). The error rate per unit time is the interaction of the bath with the computational system; the error rate per gate is the effective three-way interaction of the bath with the reservoir and computational system. The error correction is the interaction of the computational system with the cold reservoir alone.

In this picture, what would it look like if we could make the interaction with the reservoir dominate these interactions of the computational system with the bath, or the bath-system-reservoid interaction? It would look as if any interaction of the bath with the system would be more and more efficiently transmitted into the cold reservoir, with the computational system left essentially undisturbed.

This is how we can interpret what the threshold theorem tells us — if the interaction of the system with the warm bath is sufficiently low, we can simulate a bath at arbitrarily low temperature by simulating a coupling of the computational system with a cold reservoir, where the transmission of excitations from the system to the reservoir is arbitrarily swift; and furthermore the resources to do so is $\mathrm{poly} \log(\varepsilon)$, where $\varepsilon > 0$ is the factor of suppression of noise in the computational system.


Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?

I ended up getting a hint on how to accomplish this by reading the leo semantics post from Jeffrey Kegler's deprecated Marpa algorithm page. https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/pod/Advanced/Algorithm.pod#Leo-Semantics:-Indirect-and-Lazy

Snippit that really helped:

  Leo Semantics: Indirect and Lazy

  Leo's hints about semantic processing, while brief, were insightful.
  The first decision to make with the Leo semantics was direct versus
  indirect. The direct approach does the semantic processing with the
  Leo items themselves, without converting them. This has the advantage
  that costs are incurred only for the Leo items that are actually used
  by the semantics. It has the very serious disadvantage of intertwining
  the Leo logic with the semantics. Dealing directly with Leo items
  would more than double the complexity of the logic for Marpa's
  semantics. Because of this, Marpa rejected the direct approach.

  Leo 1991 suggests an indirect approach. The indirect approach is to
  expand the Leo completions into the stacks of Earley items for which
  Leo completions are a shorthand. However, in a naive implementation,
  the indirect approach eliminates every advantage of using the Leo
  speedups -- it merely moves processing from the recognizer into the
  semantic phase.

  Marpa optimizes by using a lazy implementation of the indirect
  approach. Only those Leo completions useful for the semantics are
  expanded.

  For a lazy and indirect implementation, in all cases, time complexity
  is the same as with a direct implementation. But for some ambiguous
  grammars, the space required grows from linear to quadratic with any
  indirect approach. This does not change the worst case time-complexity
  -- that was already quadratic. Fortunately, this worst case -- highly ambiguous parses where all the parse results are demanded -- is of
  limited practical interest.

I ended up using the lazy approach as well and did just in time evaluation for only items needed to complete the parse tree. This avoids the intermediate items that the normal algorithm adds.


Kolmogorov Complexity of a Decidable Language

Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^* KCDL(L_x)$, where $L_x$ is the language which consists only of the string $x$, and $=^*$ means equals up to an additive constant.

The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be solved with a Halting Problem oracle, but KCDL (when the input is a TM) is, if I recall correctly, hard for a higher level of the arithmetic hierarchy.

If you want to talk about the complexity of KCDL you also have to be careful to define what the input is. You want the input to be some finite object - languages are generally not. One natural thing for decidable languages is that the input should be a (total) TM. Another possibility is that the input is a TM, along with a proof (in some fixed, formal language) that the TM is total. Other possibilities exist too.

I haven't seen published work about it, but I thought about it a bit in grad school and proved/observed some elementary results. You can do the same for any computable function, not just a language.


Space complexity of Coppersmith–Winograd algorithm

Yes, all algorithms which stem from Strassen's original algorithm (this includes most known $n^{3-\varepsilon}$ algorithms for matrix multiplication, but not all -- see the comments) have space complexity $\Theta(n^2)$. If you could find a $n^{3-\varepsilon}$ time algorithm with $poly(\log n)$ space complexity, this would be a great advance. One application would be a $2^{(1-\varepsilon)n}$ time, $poly(n)$ space algorithm for the Subset-Sum problem.

However there are some obstacles to such a result. For some computational models, there are fairly strong lower bounds for the time-space product of matrix multiplication. References like Yesha and Abrahamson will give you more information.


Why doesn't computer science follow biology more closely in computer design?

This might be more suitable as a comment than an answer.

From computability point of view, any machine which uses finite memory (but not necessarily constant) at any point in time and modifies it according in a local way is equivalent to Turing machines (this is an informal statement of a result by Robin Gandy from 1980 IIRC). On the other hand Turing Machine models are simpler to deal with in many respects and therefore are easier as a object of study. Natural models of computation are usually more complicated to study.

There are also studies into natural models of computation. You may want to take a look at Aaron's answer here.


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


Forbidden subgraph characterisation of interval graphs

ISGCI's page on proper interval graphs (from our FAQ) lists a few equivalent classes; one of them is the class of $(C_{n+4}$, $S_3$, claw, net)-free  graphs (see the same website for definitions).


The connection between compressed sensing and sparse representation

Consider a real world 'signal' - a discrete set of numbers representing something real (e.g. an image, an audio recording, etc.). These numbers form a vector in some vector space. Any such vector can be transformed into many different bases. The vector will be more 'sparse' in some of those bases than others. In fact, there's even a set of bases where the signal is 100% sparse - i.e. a basis set which includes that particular vector as one of it's components. The representation of the vector in a basis in which it is very sparse is a 'sparse representation' of that vector. Unless there is some deliberate connection between the two, the common sense assumption is that in any randomly chosen basis, a given vector will most likely have a very not sparse representation. However, it turns out that in the real world, useful signals are often time very sparse in certain domains. This information can be used.

Compressed sensing seeks to reconstruct a signal with more information than given directly by the measurements (e.g. in imaging, a higher resolution than the number of pixels actually measured, etc.). This is mathematically impossible... unless you have some additional information about the signal aside from the measurements, such as knowing it will likely be sparse in some known domain (e.g. images tend to have a sparse representation in the Fourier domain). So, you measure the signal in some domain (not the sparse one), then you fill in the missing values with guesses to form a a bigger dataset, transform to the sparse domain, and measure the sparsity there. You then adjust your guesses and check again, and so on until you find a set of guess values that minimize sparsity in the alternate domain. You  now have a more complete vector.

So the connection is: compressed sensing uses the fact that the signal has a sparse representation in some known basis


Is deciding whether all satisfying assignments are NAE assignments coNP-complete?

Consider the following reduction from coNP-complete problem $k$-UNSAT to your language $L$ (where $k$-UNSAT is the language of all unsatisfiable $k$-CNF formulas):

On input a $k$-CNF formula $\psi$, create new variables $x_1, \ldots, x_k$ and output formula $\phi = \psi \land (x_1 \lor x_2 \lor \cdots \lor x_k)$.

If $\psi$ is unsatisfiable then $\phi$ is also unsatisfiable. In that case, it is vacuously true that every satisfying assignment $x$ of $\phi$ is a NAE assignment. (Equivalently, $\phi(x) \implies \phi(\neg x)$ is always true since $\phi(x)$ is always false.) This shows that $\phi \in L$. Thus, we see that if $\psi \in k$-UNSAT (that is, $\psi$ is unsatisfiable) then $\phi \in L$.

On the other hand, if $\psi$ is satisfiable then $\phi$ is also satisfiable by keeping the old assignment for the variables in $\psi$ and setting $x_1 = x_2 = \ldots = x_k = 1$. Notice that this is a satisfying assignment of $\phi$ that is not NAE. In other words, $\phi \not\in L$. Thus, we see that if $\psi \not\in k$-UNSAT (that is, $\psi$ is satisfiable) then $\phi \not\in L$.

The above shows that $\psi \in k$-UNSAT if and only if $\phi \in L$ and therefore that the reduction is correct. Since $k$-UNSAT is coNP-complete, we can conclude that $L$ is coNP-hard.


Survey of transformations related to the use of SAT solvers

Not sure if that is what you're looking for but here is one: J.M. Silva, Practical applications of Boolean Satisfiability.


Scrambling a Rubik's cube by an adversarial noob

If the aim is to frustrate amateur solvers, maybe the best is to give them a configuration that seems very simple to solve, but will be hard with the common algorithms.
For instance you can just invert all the centers, or do a few swaps between squares, to have just 1 or 2 wrong on each face.
This is of course betting they don't know the special algorithms to create/solve these special configurations ;)


Yes, we can always say that $X$ has pseudoentropy at least $H(X)$. You can take $Y$ to be a completely separate, independent random variable that has the same distribution as $X$. Then $X$ and $Y$ are computationally indistinguishable (indeed they are "completely" indistinguishable): $\Pr[A(X) = 1] = \Pr[A(Y) = 1]$ for all algorithms $A$.

Instead of thinking of psuedoentropy as a property of a random variable, maybe it is more helpful to think of it as a property of a distribution. Not a big difference but emphasizes that, for instance, $X$ and $Y$ are never correlated in the definition.


First: Student's heuristics. At your level, what can you prove? Equivalence with TM or PDA should work by simulation. Equivalence to LBA might be slightly harder. Anything in between is certainly harder. So start with the easy inclusions.

You can see very quickly that languages like $a^nb^nc^n$ that are not context-free can be accepted by a 2-PDA. So you are certainly stronger than PDA.

Next in line is TM. Of course, every 2-PDA can be simulated by a 2-TM which can in turn be simulated by a TM. Turns out that the other direction works out, too. Take a TM and simulate it by a 2-PDA. You can keep the state graph but have to translate reading/writing/moving to reading$^2$/writing$^2$. What can simulate the TM's head? Also, take care what happens if the TM accesses new fields.

Can you figure it out now?


If there exist some NP language L that's hard on the average on some distribution $\mu$, then by applying the standard reduction $f$ from L to 3SAT you get that 3SAT is hard on $f(\mu)$.

Your understanding is wrong. By saying that the inverting task  for a function f is NP hard, one means that there is a polynomial-time algorithm A such that A can solve 3SAT on every input given black-box access to an inverter I that inverts f on a non-negligible fraction of the inputs.


Approximations for the Stable Fixtures Problem

Your problem is called maximum weighted simple b-matching, and it's solvable in strongly polynomial time. See this paper for instance.


Genetic Algorithm to Draw a Graph? Position assignment problem

I don't think it is wise to use local search techniques. There are many (fast) methods which work pretty good for many classes of graphs. Of course you can also test local search methods.

A few comments:

  Number of intersecting edges should be minimal

Is your graph planar? If yes, there are many good methods for planar graphs (e.g. dominance drawings).

Is it a general digraph? In this case a hierarchical approach may be suitable (more information later).

  All edges flow in one direction (i.e from left to right)

Does it contain cycles? If yes, this is not possible.

A great source for graph drawing algorithms is Graph Drawing: Algorithms for the Visualization of Graphs.

In my opinion a good first approach to this problem is the hierarchical approach. Check the paper by Sugiyama et. al Methods for Visual Understanding of Hierarchical System Structures (chapter 9 in 1 describes such methods).

If you go with the local optimization methods, I would definitely use the initial configuration to start with (since it should be close to a good local optimum).


Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size

Consider circuit value problem and Boolean formula evaluation for various small complexity classes. Deterministic sequential time complexity of them are the similar as far as we know, yet they are very different from circuit complexity perspective. Similarity in one particular type of resource on one model doesn't imply similarity for other resources in other models. One problem can be such that we can exploit parallel computation for one while we can't do that for another one, yet their sequential time complexity can be the same.

When can we expect a more robust relation between the complexity of two problems across models and different resources? When they're are robust reduction between them in both directions that respects resources in those models.

Edit: multiplication has subexponential size depth 3 circuits. Proving a lower-bound of that kind for determinant would show it is not in $\mathsf{NL}$ separating it from $\mathsf{NC^2}$ which is not known.


I didn't check if the Bangye's solution is correct/simpler, but a quick transformation from RESTRICTED X3C (the name is the same used by Gonzales)  to SINGLE OVERLAP RESTRICTED X3C (the name is invented) that should work is:

Replace each subset $C_j=\{x_1,x_2,x_3\}$ adding 6 new elements $z_{j,1},z_{j,2},...,z_{j,6}$ and 5 new three elements subsets $L_{j,1}=\{x_1,z_{j,1},z_{j,4}\}$,$L_{j,2}=\{x_2,z_{j,2},z_{j,5}\}$,$L_{j,3}=\{x_3,z_{j,3},z_{j,6}\}$,$L_{j,4}=\{z_{j,1},z_{j,2},z_{j,3}\}$,$L_{j,5} = \{ z_{j,4},z_{j,5},z_{j,6}\}$ .

like in the figure below (blue triples).
Informally, the three elements originally in $C_j$ are grouped and in order to include elements $z_{j,1},...,z_{j,6}$ the exact cover must include the group of triples $L_{j,1},L_{j,2},L_{j,3}$ OR the two triples $L_{j,4},L_{j,5}$, but not both.

At this point no pair of triples share more than one element and each element is included in exactly 3 triples; except elements $z_{j,1},...,z_{j,6}$ which are included only in two triples.

In order to fix this it's enough to add a duplicate of every element element $x_i \rightarrow x'_i, z_i \rightarrow z'_i$, a duplicate of each triple containing $x_i$ or $z_i$ elements using the corresponding duplicated elements (green triples in the figure below) and for each original triple $C_j$ add three new elements $t_{j,1},t_{j,2},t_{j,3}$ and 7 new
dummy subsets with elements:
$D_{j,1} =\{ z_{j,2},z_{j,6},t_{j,1} \}$,
$D_{j,2} =\{ z_{j,3},z_{j,4},t_{j,2} \}$,
$D_{j,3} =\{ z_{j,1},z_{j,5},t_{j,3} \}$,
$D_{j,4} =\{ z_{j,2}',z_{j,6}',t_{j,2} \}$,
$D_{j,5} =\{ z_{j,3}',z_{j,4}',t_{j,3} \}$,
$D_{j,6} =\{ z_{j,1}',z_{j,5}',t_{j,1} \}$,
$D_{j,7} =\{ t_{j,1},t_{j,2},t_{j,3} \}$ (yellow triples in the figure below).

(note that the $z,z'$ elements of dummy triples $D_{j,1}, D_{j,2}, ..., D_{j,6}$ and elements $t$ of dummy triples $D_{j,4},D_{j,5},D_{j,6}$ are "shifted"  to avoid triples that share more than one element)

($\Rightarrow$) Suppose that $\bigcup_{j \in A \subseteq \{1,...,3n\}} C_j$ is an exact cover of the original RESTRICTED X3C instance.
Then by construction:

$$\bigcup_{j \in A } ( L_{j,1} \cup  L_{j,2} \cup  L_{j,3} \cup L'_{j,1} \cup  L'_{j,2} \cup  L'_{j,3} \cup D_{j,7} ) \cup \bigcup_{j \notin A } (L_{j,4} \cup L_{j,5} \cup  L'_{j,4} \cup  L'_{j,5} \cup D_{j,7}) $$

is an exact cover of SINGLE OVERLAP RESTRICTED X3C.

($\Leftarrow$) Suppose that there exists an exact cover of the SINGLE OVERLAP RESTRICTED X3C instance.
Every original element $x_i$ must be included exactly once in the cover, but, as seen above, the only way to include an element $x_i$  is by choosing a group of triples $L_{j,1},L_{j,2},L_{j,3}$ that correspond to an original triple $C_j$ that contains $x_i$.
Furthermore  if $L_p, L_q, p \neq q$ are included in the exact cover we have $L_p \cap L_q = \emptyset$.
So the collection $L_{j,k}$ of subsets in the  SINGLE OVERLAP RESTRICTED X3C exact cover correspond to a valid cover $\bigcup C_j$ of the original RESTRICTED X3C instance.

The reduction can be done in polynomial time, so we can conclude that SINGLE OVERLAP RESTRICTED X3C is NP-complete.

Just note that a SINGLE OVERLAP RESTRICTED X3C instance built using the above reduction can contain two valid and distinct exact covers of the original RESTRICTED X3C problem, but we are sure that if only one exact cover exists, it can be "mirrored" to form a valid exact cover of SINGLE OVERLAP RESTRICTED X3C.

Let me know if you need a more formal proof for a paper.

Update 20/04/2020: I noticed that the previous figure had a small issue in the dummy triples and I fixed it.


First, I think the CCA-security is not enough, and the encryption scheme must be at least IND-CCA2-secure.

Second, I believe the protocol is not zero-knowledge, at least in the auxiliary-input model. The reasoning is as follows: Let z be the auxiliary input to the malicious verifier V*. It's safe to assume that $z = Enc_{p_k}(m)$, where m is unknown to V*. Then, V* can deviate from the original protocol: Instead of choosing a random m and computing c (as prescribed in the protocol), she lets c = z, and sends c to the prover. This way, V* exploits P as a "decryption oracle," and obtains knowledge beyond what she could possibly compute.

One piece of advice: Read the paper Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, specially section 4. It suggests a protocol similar to yours; one which has never been realized. It also proposes the now-famous "knowledge-of-exponent" assumption (KEA), one which was later used to construct a non-black-box ZK protocol. (The reason why you can't find a simulator, beyond the line of reasoning above, is that you try to imagine a black-box simulator. That's impossible by the result of Goldreich and Krawczyk). For more info on the use of the KEA in constructing non-black-box ZK, see [Hada and Tanaka] and the more recent [Bellare and Palacio].

--Edit-- @cyker: I'm working on a similar issue as (presumably) you're doing: The (right) definition of simulators. A partial result of mine, closely related to the protocol you offered, can be found at http://eprint.iacr.org/2010/150. The latest results are submitted but not published online yet.


Reference Request: Error correction code for a random projection

I think the term is deletion channel. As the Wikipedia article says, this "should not be confused with the binary erasure channel".


Halting on a (possibly one-way) write-once tape

Ad 1. Write-once TMs are equivalent to ordinary TMs (I think this is an exercise in Sipser, but I don't have the text at hand to confirm) so $\rm woBB$ is uncomputable.

Ad 2. No. The usual zipper encoding also works for write-once TMs, so write-once TMs that never move past the end of the one-way infinite tape are equivalent those with two-way infinite tape. Therefore $\rm owwoBB$ is uncomputable, and the choice of behaviour when moving past the end of the tape doesn't affect this.


My question is just whether there is a known relativization barrier.

Yes, there is a known relativization barrier. It's given by $A:=TQBF$, because Emil Jeřábek (see comments) is right: the statement that $TQBF$ is $PSPACE$-complete under logspace many-one reductions is well known.

Emil Jeřábek's remark "(or even uniform $\mathbf{AC}^0$)" seems less relevant, because $\mathbf{AC}^0$ is easily separated from $L$ (or even uniform $\mathbf{NC}^1$). Because the resulting formula actually depends only very locally on the input for the $PSPACE$-Turing machine, one could even claim that $TQBF$ is $PSPACE$-complete under $L$-uniform $\mathbf{NC}^0$ (instead of uniform $\mathbf{AC}^0$). But I find this misleading, because the circuit doesn't really do any non-trivial work at all, it basically just writes down a template.

(The reduction writes down $n^k$ times $\exists c_{1.5}\forall (c_3, c_4) \in \{(c_1, c_{1.5}), (c_{1.5}, c_2)\}$ with systematically varying indices, where each $c_i$ are actually $n^k$ Boolean variables. This entire part only depends on the length of the input, hence the corresponding output variables are hardwired to constants. The final formula could be written as $\forall z. (z_1=i_i\land\dots\land z_n=i_n)\land \phi(x,y,z)$ such that only $i_i,\dots,i_n$ depends on the actual input, and such that this is the only place where $i_i,\dots,i_n$ appear. So this is nearly trivially an $\mathbf{NC}^0$, the entire work has been done by the $L$-algorithm writing down the circuit, whose outputs are nearly all directly hardwired to constant.)


What would a quantum computer architecture look like?

Really my question comes down to where in the standard computer processing pipeline does the quantumness come in, in order to produce the intended theoretical behaviour of quantum computer?

The critical part to get the intended theoretical (scaling) behaviour of quantum computer is probably to achieve and maintain the coherence between the different qubits in the computer.

Let me illustrate this with a hypothetical architecture. Assume that you have ready made modules with a fixed number of qubits (say 49=7x7). Further assume that each module for itself is able to maintain coherence between its qubits (by using quantum error correction), and reliably operate on its qubits controlled by a classical computer (my mental model is similar to this simple model of a finite quantum coprocessor I asked about before, but it doesn't really matter for this illustration1).

Now assume that you scale your quantum computer by putting many of those modules together, using some suitable topology. The modules cannot talk directly to each other, but we may assume that the classical computer controlling those modules is able to freeze any quantum operation of the modules and then permute qubits between those modules according to the topology.

Now assume that the quantum operation of each module randomly changes its global phase in a way uncontrollable and unmeasurable by the controlling classical computer. This is not even true decoherence (as would occur in practice - the density matrix formalism could be used for a better model), but I guess it will be sufficient to destroy the intended theoretical (scaling) behaviour of quantum computer. But if the qubits of the different modules stay perfectly coherent with each other, and the global phase differences between the modules are known to the classical computer, then I guess it will be possible to achieve the intended theoretical (scaling) behaviour of quantum computer.

Edit Actually, the part of the model about initialization and measurement does matter a bit. Even if we assume that we know the global phase differences between the modules after initialization, we certainly have to assume that measurement is restricted to each module alone, and that coherence with other modules is lost after measurement. I still don't think that this will destroy the quantum speedup, since the global state can be (quantum/unitarily) transformed suitably before the measurement, hence one should still be able to perform any desired single measurement at the end of the quantum computation.


Compared growth of the number of syntactic classes and Nerode classes.

It seems that this paper     http://arxiv.org/abs/1010.3263  may be relevant to your question.

The abstract states:

The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We study the syntactic complexity of the class of regular ideal languages and their complements, the closed languages. We prove that $n^{n-1}$ is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity $n^{n-1}+n-1$, and two-sided ideals and factor-closed languages of syntactic complexity $n^{n-2}+(n-2)2^{n-2}+1$.

Thus, as far as I understand, this  answers your question about the sizes of syntactic and Myhill-Nerode semigroup: in general, syntactic congruence may have exponentially many classes than Myhill-Nerode relation.

The last comment. Usually the finitness of both semigroups for regular languages is attributed to M.Rabin and D.Scott (Finite automata and their decision problems. IBM Jourmal. April 1959). In particular, it follows from the text of Rabin and Scott that the number of syntactic classes does not exceed $n^n$, where $n$ is the number of Myhill-Nerode classes.


Bounded-input bijections of infinite sequences

I am not a CS theory guy. But in ergodic theory this type of mapping is known as finitary isomorphisms. For example people considered if two Bernoulli sequences of the same entropy is finitarily isomorphic or not. For example (this is one-sided shift because it seems you are concerned with $P^{\mathbb{N}}$ rather than $P^{\mathbb{Z}}$):

A. Del Junco, “Finitary codes between one-sided Bernoulli shifts,” Ergodic
Theory Dynamical Systems, vol. 1, pp. 285–301, 1981.

P.S. I intend to leave this as a comment but I cannot due to lack of reputation. Let me know if it is completely off-topic then I will delete it.


Four color theorem and map pre-simplification of faces with less than 5 edges

The result is known since Kempe in 1879, and is mentioned in http://en.wikipedia.org/wiki/Four_color_theorem as "Kempe also showed correctly that G can have no vertex of degree 4...."  Your proof does not work, because when you remove two edges joining face B with A and C, A and C may already have been adjacent.  Since you give the combined face a color, then return face B with a new color, you leave A and C adjacent and of the same color.


Here is an interesting problem whose succinct version has interesting properties. Define Circuit-Size-$2^{n/2}$ to be the problem: given a Boolean function as a $2^n$-bit string, does this function have a circuit of size at most $2^{n/2}$?  Note this problem is in $NP$.

One way to define Succinct-Circuit-Size-$2^{n/2}$ would be: for a constant $k$, given an $n$-input, $n^k$-size circuit $C$, we want to know if its truth table is an instance of Circuit-Size-$2^{n/2}$. But this is a trivial problem: all inputs which are actual circuits are yes-instances. So this problem is in $P$.

A more general way to define Succinct-Circuit-Size-$2^{n/2}$ would be: we are given an arbitrary circuit $C$ and want to know if its truth table encodes an instance of Circuit-Size-$2^{n/2}$. But if $n$ is the number of inputs to $C$, $m$ is the size of $C$, and $m \leq 2^{n/2}$, we can automatically accept: the input itself is a witness for the language. Otherwise, we have $m \geq 2^{n/2}$. In that case, the input length $m$ is already huge, so we can try all possible $2^n$ assignments in $m^{O(1)}$ time, obtain the truth table of the function, and now we are back to the original $NP$ problem again. So this is a problem in $NP$ whose succinct version is also in $NP$.

This problem is believed to be not $NP$-hard; see the paper by Kabanets and Cai (http://www.cs.sfu.ca/~kabanets/Research/circuit.html)


Length of a minimal DNF Boolean expression

The answer is $2^{n-1}$.

To see that this is a lower bound consider the n variable parity function and observe that the unique (equivalent) DNF has $2^{n-1}$ clauses, none of which are resolvable.

To see that this is an upper bound, consider any DNF and the  full ordered decision tree for that DNF (i.e., tree where every leaf is at depth n and every path from the root to the leaf has all variables and in the same fixed order). Any two leafs which are siblings and which are both "true"  represent resolvable clauses in the full equivalent DNF. In this way one has at least has an equivalent clause-set of size at most $2^{n-1}$ by taking for every node at level n-1 either the DNF clause given by the only true leaf child of that node (if it has one true child) or the resolvent of the two clauses corresponding to its two children (if it has two true children). That is we have at most one clause for each node at this level in the tree, I.e., $2^{n-1}$.


How to prove relations between "classes" of types?

One approach to such questions is via encodings.

Say you have a language $L_1$ and a language $L_2$ and you want to show that they are somehow "the same", you can do this by finding an encoding

$$
   \newcommand{\SEMBTYPE}[1]{\ulcorner #1 \urcorner}
   \newcommand{\SEMB}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack}
    \SEMB{\cdot} : L_1 \rightarrow L_2
$$

and then show that for all $L_1$ programs $M, N$ the following holds:

$$
   M \cong_1 N
   \qquad \text{iff} \qquad
   \SEMB{M_1} \cong_2 \SEMB{M_2}
$$

Here $\cong_i$ is a chosen notion of program equivalence for $L_i$. In order to do this for typed languages, one typically also maps $L_1$-types to $L_2$ by way of a function $\SEMBTYPE{\cdot}$ which is extended to typing environments, such that
something like the following holds:

$$
   \Gamma \vdash_1 M : \alpha
   \qquad \text{implies} \qquad
   \SEMBTYPE{\Gamma} \vdash_2 \SEMB{M} : \SEMBTYPE{\alpha}
$$
Here $\vdash_i$ is the typing judgement for $L_i$.
The whole approach is called full abstraction.

In order to avoid the "curse of Church-Turing universality", one typically imposes conditions on $\SEMB{\cdot}$, e.g. that it's compositional, or closed under injective renaming. The more conditions $\SEMB{\cdot}$ meets, the stronger the full abstraction result.

This is also Orchard & Yoshida are attempting to do (Theorems 1- 5), although they don't quite achieve it.


Partitioning a connected shape into rectangles

David Eppstein gave an excellent answer for this question here on MathOverflow (responding to a question for which it is not quite as good an answer). To summarize, there is a polynomial-time algorithm for finding the minimum number of rectangles.


Efficient CNF Simplification based on Binary Implication Graphs, Marijn Heule, Matti Jarvisalo, and Armin Biere, 2011

  "This paper develops techniques for efficiently detecting and removing redundancies from CNF (conjunctive normal form) formulas based on the underlying binary clause structure (i.e., the binary implication graph) of the formulas.

  In addition to considering known simplification techniques (hidden tautology elim- ination (HTE), hyper binary resolution (HBR), failed literal elimination over binary clauses, equivalent literal substitution, and transitive reduction  of the binary implication graph), we introduce the novel technique of hidden literal elimination (HLE) that removes so-called hidden literals from clauses without affecting the set of satisfying assignments."

I recommend Section 2.1 of the paper which reviews known simplification techniques.


Vertex disjoint simple paths of length k

It appears that this problem (or a generalization of it) was considered with the Divide and Color approach yielding a $O^*(4^{(k-1)\cdot p})$ run-time algorithm for deciding the problem.


Is there a list of forbidden subgraphs for comparability graphs?

You could refer to the entry for comparability graphs on graphclasses.org: http://www.graphclasses.org/classes/gc_72.html
(look at "equivalent classes" and note that the list is not finite)


Sperner family that maximizes the subsets of a partition

The correct upper bound is the sum of the $2^k$ most central binomial coefficients:
$$|\mathcal{F}_B|\leq\binom \ell {\lfloor (\ell - 2^k)/2+1\rfloor} + \dots + \binom \ell {\lfloor(\ell + 2^k)/2\rfloor},$$
or just $|\mathcal{F}_B|\leq 2^\ell$ if $2^k\geq \ell+1$. The sets $\{B\cap C\mid C\in\mathcal F\text{ and }A\cap C=A'\}$ are antichains. By the LYM inequality the union of $2^k$ antichains cannot be larger than the sum of the largest $2^k$ binomial coefficients. To achieve the bound, let $A=\{a_0,\dots,a_{k-1}\}$, and let
$$\mathcal F=\left\{C\subseteq A\cup B \mid \lfloor(\ell + 2^k)/2\rfloor- \sum_{i\colon a_i\in C} 2^i=|C\cap B| \right\}.$$


Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

This is open, as far as I know. It could be provable (because its hypothesis may be false) or it just be difficult to show that any $2^{n^k}$-time algorithm for Succinct3SAT can be converted into a $2^{O(n)}$-time algorithm for Succinct3SAT.

In general, theorems of this kind are called "downward collapses" which say if two "large" classes are equal then two "smaller" classes are equal. These theorems are rare. Usually you can either prove an "upward collapse" (small classes equal implies larger classes equal, like $P = NP$ implies $NEXP = EXP$) or its contrapositive, a "downward separation".

Something along the lines of what you want is the theorem by Hartmanis, Immerman and Sewelson (http://dl.acm.org/citation.cfm?id=808769) that $NE = E$ $\iff$ every sparse set in $NP$ is contained in $P$. This gives a "downward collapse" but only for the sparse sets (those sets that contain only $poly(n)$ strings of length $n$).


If P = NP were true, would quantum computers be useful?

The paper "BQP and the Polynomial Hierarchy" by Scott Aaronson directly addresses your question. If P=NP, then PH would collapse. If furthermore BQP were in PH, then no quantum speed-up would be possible in that case. On the other hand, Aaronson gives evidence for a problem with quantum speedup outside PH, thus such a speed-up would survive a collapse of PH.


Gift bits when encoding a sequence of messages, how is that?

The important thing is what "information quantity is additive" with respect to.

Information quantity is additive with respect to concatenating messages

each of which can only have one length, rather than forming a multiset

of messages each of which can only have one length.

Information quantity is subadditive with respect to forming a multiset of messages

each of which can only have one length, because for every concatenation,

there is a unique multiset that is consistent with that concatenation.


A property of suffix-free regular languages of maximal state complexity for the reverse operation

StefanH: You are right, there was this bug in the proof of Theorem 9 in the arxiv version; the argument worked only for $|F|=1$. We fixed this in the revised version for a journal (not published yet) in a similar way you proposed. I have just updated arxiv (https://arxiv.org/abs/1504.05159).


(1): This question was studied in the paper "Towards proving strong direct product theorems" by Ronen Shaltiel, and it turns out that such a conjecture is false: For example, it could be that $f$ can be computed with probability $0.99 * p$ with size much smaller than $s$, and only the additional $0.01 * p$ probability mass requires size $s$. In such case, when computing $f$ on $k$ instances, the circuit could solve $f$ on most of the instances with size much smaller than $s$, and will need size $s$ only on few of the instances.

(2): A direct product theorem for worst-case complexity is known for formulas and for monotone circuits, but is actually known to be false for general circuits. For an easy example, consider a function $f : \{0,1\}^n \to \{0,1\}^n$ that views its input as a vector and multiplies it by some fixed $n \times n$ boolean matrix. Then, computing the function $f$  may require size $n^2$, but computing it on $n$ instances can be done much faster than $n^3$ using a matrix multiplication algorithm.
You can find a thorough discussion of this subject in the book "The complexity of Boolean Functions" by Ingo Wegener - see Chapter 10.2 here: http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/.


The problem you mention is called "replacement paths".
Here are a few references:

Gotthilf and Lewenstein, Improved algorithms
for the k simple shortest paths and the
replacement paths problems. Inf. Proc. Letters,
109(7):352–355, 2009. This paper gives the fastest to date exact algorithm for the replacement paths problem, running in time $O(mn+n^2\log\log n)$ time in graphs with $n$ nodes and $m$ edges.
A. Bernstein. A nearly optimal algorithm for approximating
replacement paths and k shortest simple
paths in general graphs. In Proc. SODA, pages
742–755, 2010. This paper amazingly gives a quasilinear time approximation scheme for the problem.
J. Hershberger, S. Suri, and A. Bhosle. On the
difficulty of some shortest path problems. In Proc.
STACS, pages 343–354, 2003. This paper shows that any path-comparison algorithm solving the replacement paths problem exactly must take at least $\Omega(m\sqrt{n})$ time.
V.Vassilevska W., R. Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. In Proc. FOCS, pages 645-654, 2010. We show that if you obtain an $O(n^{3-\varepsilon})$ time exact algorithm for replacement paths for any constant $\varepsilon>0$, then this can be converted to an $O(n^{3-\varepsilon'})$ time algorithm for all pairs shortest paths for constant $\varepsilon'>0$. Such a truly subcubic algorithm for all pairs shortest paths is a longstanding open problem.
O. Weimann, R. Yuster. Replacement Paths via Fast Matrix Multiplication. In Proc. FOCS, pages 655-662, 2010. and V. Vassilevska W. Faster Replacement Paths. In Proc. SODA, pages 1337-1346, 2011. These papers show how to use fast matrix multiplication to find replacement paths in graphs with integer edge weights in the interval $\{-M,\ldots, M\}$. The latter paper gives the best known runtime so far, $\tilde{O}(Mn^\omega)$.


Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.


Has this form of "kind-of-dual" homomorphisms been studied?

In the case of undirected graphs, there is literature about such morphisms called graph emulators.
They are a refinement of the notion of covering graph.
A covering graph maps the neighbourhood of a vertex $u$ bijectively to the neighbourhood of $h(u)$, while an emulator is only required to do it surjectively, which seems equivalent to your question.

This notion appears in the context of characterizing graphs having planar covers or planar emulators, which yields several open problems, see for instance this paper for a survey.


I believe "maximum weight fair bipartite matching" as you've defined it is NP-hard.  Even more, determining the existence of a fair bipartite matching is NP-hard.

Before I give a proof sketch, for intuition, consider the following small instance.  Take $G'=(L, R, E'=L\times R)$ where $L=\{a,b\}$, $R=\{c,d,e,f\}$.  Take $p$ such that $p(u,w) = 0$ for $u\in L$ and $w\in\{c,d\}$, while $p(u,w) = 1$ for $u\in L$ and $w\in\{e,f\}$.  Then $a$ and $b$ are equivalent, in the sense that $p(a, w) = p(b, w)$ for all $w\in R$, so any fair matching must give $a$ and $b$ the same profit.  Hence, the only fair matchings either match $a$ and $b$ to $c$ and $d$, or they match $a$ and $b$ to $e$ and $f$.  Using this kind of gadget, we can force coordination of the edges in the matching.  This is the basis of the reduction.

Here's an attempt at a proof.  It's a bit involved. Probably there are some mistakes, but hopefully any mistakes can be fixed.

Lemma 1. Given $G'=(L, R, E'=L\times R)$ and $p:E'\rightarrow\mathbb{R}_+$ as described in the problem, determining whether $G'$ contains a fair matching is NP-hard.

Proof sketch. The proof is by reduction from Independent Set in cubic graphs.  Let $(G=(V,E),k)$ be a given instance of Independent Set where $G'$ is a cubic graph (every vertex has degree 3).  We describe how to construct a graph $G'=(L, R, E'=L\times R)$ and profit function $p:E'\rightarrow\mathbb{R}_+$ such that $G'$ has a fair bipartite matching if and only if $G$ has an independent set of size $k$.

The vertices in $L$ will come in pairs, called partners.
Likewise for the vertices in $R$.
For each vertex $v\in L\cup R$, we let $v'$ denote the partner of $v$.
Each vertex $\ell\in L$ and its partner $\ell'\in L$ will be equivalent, meaning that we will make
$$p(\ell, r) = p(\ell', r) \text{ for all } r\in R.$$
Consequently, any fair matching must assign the same profit to $\ell$ and $\ell'$.
In what follows, we use $\pi(\ell, r)$
to denote the value of $p(\ell,r) = p(\ell', r)$.

Further, for each pair $\ell$ in $L$,
and each pair of partners $r, r'$ in $R$,
either we make
$$\pi(\ell, r) = \pi(\ell, r')$$
or we make
$$\pi(\ell, r) \ne \pi(\ell, r').$$
In the former case, we say we allow $\ell$ and $\ell'$ to be matched to $r$ and $r'$
(because doing so would assign the same profit to $\ell$ and $\ell'$,
as required).
In the latter case, we say we prevent $\ell$ and $\ell'$ from being (both) matched to $r$ and $r'$
(because doing so would not assign the same profit to $\ell$ and $\ell'$).

As the given graph $G=(V,E)$ is cubic, it satisfies $3|V|=2|E|$, and any independent set $I$ of size $k$ in $G$ is incident to exactly $3k$ edges.  Assume for ease of notation that $V=\{1,2,\ldots,n\}$.

For each edge $\{i, j\}\in E$, do the following.

Add a pair of partner vertices $r(\{i,j\}), r'(\{i,j\})$ to $R$.
For endpoint $i$, add a pair of partner vertices $\ell(i,j),
    \ell'(i,j)$ to $L$. Set $$\pi(\ell(i,j), r(\{i,j\})) =
    \pi(\ell(i,j), r'(\{i,j\}))= i,$$ allowing $\ell(i,j)$ and
$\ell'(i,j)$ to be matched to $r(\{i,j\})$ and $r'(\{i,j\})$.
Symmetrically, for the other endpoint $j$: add another pair of
partner vertices $\ell(j,i), \ell'(j,i)$ to $L$, and set
$$\pi(\ell(j,i), r(\{i,j\}) = \pi(\ell(j,i), r'(\{i,j\}))= j,$$
allowing $\ell(j,i)$ and $\ell'(j,i)$ to be matched to $r(\{i,j\})$
and $r'(\{i,j\})$.

For every $\ell\in L$ and $r\in R$ added so far,
if the pair $\ell, \ell'$ is not explicitly allowed (above)
to be matched to $r, r'$, then prevent the match
by assigning $\pi(\ell, r)$ and $\pi(\ell, r')$ each some unique number.

Next, add $3(|V|-k)$ pairs of filler vertices to $R$.
For each filler vertex $r$ and each $\ell(i,j)\in L$,
set $\pi(\ell(i,j), r) = 0$.

Finally, add two vertices $L_0$ and $L'_0$ (partners) to $L$, along with a two vertices $R_0$ and $R'_0$ (also partners) to $R$.
Set $\pi(L_0, R_0) = \pi(L_0, R'_0) = 1$, allowing $L_0$ and $L'_0$ to be matched to $R_0$ and $R'_0$.  For every other vertex $r\in R$, set $\pi(L_0, r)$ to some unique number.  (Hence, any fair matching must match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.)
For every $i\in V$, for every incident edge $\{i,j\}\in E$,
set $\pi(\ell(i,j), R_0) = i$ and $\pi(\ell(i,j), R'_0) = |V|-i+1$.

That completes the reduction.  To finish, we prove it is correct.

First consider for what pairs of vertices $\ell(i,j),\ell(i',j')\in L$
the latter dominates the former, that is,
$$(\forall r\in R)~\pi(\ell(i,j),r) \le \pi(\ell(i',j'), r).$$

Considering the profits assigned to edges incident to $R_0$ and $R'_0$,
this condition can only be met if $i=i'$, and, inspecting the definition of $\pi$ for the remaining edges, the condition $i=i'$ is sufficient.  Hence a matching is fair if and only if it assigns $L_0$ and $L'_0$ to $R_0$ and $R'_0$, and also, for each $i\in V$, gives the same profit to all vertices in
$$N(i) = \{\ell(i,j) : \{i,j\}\in E\} \cup \{\ell'(i,j) : \{i,j\}\in E\}.$$

First, assume that $G$ has an independent set $I$ of size $k$.  Obtain a fair matching for $G'$ from $I$ as follows.

Match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.

For each vertex $i\in I$,
let $\{i,j_1\}, \{i,j_2\}, \{i,j_3\}$ be its three incident edges.
For each edge $\{i, j_h\}$,
match vertex $\ell(i,j_h)$ and its partner $\ell'(i,j_h)$
to $r(\{i,j_h\})$ and $r'(\{i, j_h\})$.
This gives all vertices in $N(i)$ profit $i$.

For each of the $|V|-k$ vertices $i\in V\setminus I$,
for each of the three edges $\{i,j\}$ incident to $i$,
match $\ell(i,j)$ and its partner $\ell'(i,j)$
to some unique pair of filler vertices $r$ and its partner $r'$.
This gives all vertices in $N(i)$ profit $0$.

Hence, this matching is fair.

Next, assume that $G'$ has a fair matching $M$.

$M$ must match $L_0$ and $L'_0$ to $R_0$ and $R'_0$.
For each $i\in V$, the matching must give each of the vertices in $N(i)$
the same profit.  For each $\ell(i,j)\in N(i)$, its partner $\ell'(i,j)$ is also in $N(i)$.  So, by inspection of the reduction,
the profit of each such vertex must be either $i$
(in which case all six vertices in $N(i)$ are matched
to vertices $r(\{i,j\})$ and their partners)
or zero
(in which case all six vertices in $N(i)$ are matched
to filler vertices in $R$).
Let $I$ be the set of vertices for which the former case holds.
For each edge $\{i,j\}$, the vertex $r(\{i,j\})$,
and its partner, are each matched to one vertex.
It follows that $I$ is an independent set.
Since the number of filler vertices is $6(|V|-k)$,
the size of $I$ must be at least $k$.

QED (?)

I think it's basically correct, if a bit convoluted.  Let me know if you see any mistakes, or a way to simplify the proof.

The reduction above assumes it's okay to take $|R|>|L|$.
If that's undesirable, then I'd guess we can pad $L$
with $|R|-|L|$ filler vertices, assigning profit 0
to all of their edges except the edges to $R_0$ and $R'_0$.
We can assign profits to the latter edges to ensure
the filler vertices are not dominated by (nor dominate)
any other vertex.


Newman's lemma for distributional communication complexity

There's nothing wrong in your proof, but you can do even better; by taking the average in

$$
\mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon
$$

you can conclude that there's a single $r_0$ for which

$$
\mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r_0) \neq f(x,y)} \leq \varepsilon.
$$

So in particular, randomized distributional communication complexity is the same as deterministic distributional communication complexity, which explains why it didn't get much attention in the literature...


I think the following is a polynomial-time algorithm based on maximum flow. Let $G(V,E), b, c$ be the input.

Construct a directed bipartite graph $H(L,R,F)$ with $L$ and $R$ being the left and right partitions and $F$ being the directed edges from $L$ to $R$.
Let $|V| = n$. There are $n$ vertices in $L$ and $n$ vertices in $R$.
Each vertex $v \in V$ has a "copy" in $L$ (say $v_l$) and a copy in $R$ (say $v_r$).
If $(u,v) \in E$ add a directed edge from $u_l$ to $v_r$. Each such edge has capacity 1.
Add a "source" node $s$ and add directed edges from $s$ to each vertex in $L$. Each such edge has a capacity $b$.
Add a "sink" node $t$ and add directed edges from each vertex in $R$ to $t$. Each such edge has a capacity $c$.
Find maximum flow from $s$ to $t$.

The given graph $G$ has a solution if and only if the max-flow computed above saturates every edge from $s$ to $L$, i.e., the flow on every edge from $s$ to $L$ is equal to $b$.


A proof that Partition into forests is NP-Complete

First, let me address what is wrong with your proof. The general idea you give for how to prove your reduction correct seems reasonable. The problem is that your reduction is not actually correct. In particular, the statement "if there is no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits, then there will be a clique of size at least $m$ in $G′$" is false. Consider the following counterexample:

This graph has no 5-cliques, but also cannot be partitioned into 2 forests.

Reduction alternative

You can instead reduce from graph 3-coloring. Given a graph $G = (V, E)$, you can modify this graph by adding three new vertices $u_1, u_2, u_3$ and adding every possible edge with any of these vertices as an endpoint. Let $G'$ be this new graph. Then we claim that $G$ is 3-colorable if and only if $G'$ can be partitioned into 3 forests.

First direction:

Suppose $G$ is 3-colorable. Let $A$, $B$, and $C$ be the sets of vertices in $G$ with each of the three colors. Let $A' = A \cup \{u_1\}$, $B' = B \cup \{u_2\}$, and $C' = C \cup \{u_3\}$. Notice that by the properties of a 3-coloring, no two vertices in $A$ are adjacent. Therefore the only edges induced by $A'$ are of the form $(u_1, v)$ with $v \in V$. Clearly, the graph induced by $A'$ has no cycles. The same logic applies to show that $B'$ and $C'$ also induce forests. Thus, $A'$, $B'$, and $C'$ is a partition of $G'$ into three forests.

Second direction:

Now suppose $G'$ can be partitioned into three forests. Since $u_1, u_2, u_3, u_1$ is a cycle, the three vertices $u_1, u_2, u_3$ cannot all be in the same part of the partition. Then there are two cases.

Case 1: each vertex $u_1, u_2, u_3$ is in a different part of the partition.
Then consider any two vertices $v_1, v_2$ from the same part of $G'$ other than $u_1, u_2, u_3$. If $(v_1, v_2)$ were an edge, then there would be a cycle $u_i, v_1, v_2, u_i$ in the part containing $v_1$ and $v_2$. Since that is not the case, we see that no two adjacent vertices of $G$ are in the same part of the partition. In other words, the partition of $G'$ directly induces a 3-coloring of $G$.

Case 2: some two vertices among $u_1, u_2, u_3$ are in the same part. WLOG, suppose $u_1$ and $u_2$ are in the same part of the partition, call it $A$. Let the part of the partition containing $u_3$ be $B$ and let the final part be $C$. Note that $A$ contains no vertices from $G$ since if any $v \in V$ were in $A$ then the cycle $v, u_1, u_2, v$ would be present in one of the parts. Thus, every vertex from $G$ is either in $B$ or in $C$. Since $C$ induces a forest, it is possible to 2-color the vertices in $C$ (such that no two vertices of the same color are adjacent). If we then color the vertices of $B$ with a third color, we will have an assignment of three colors to the vertices of $G$. We already know that two of those colors have no adjacent monochromatic pairs of vertices. Using the same logic as in case 1, we can also conclude that $B$ contains no two adjacent vertices in $G$, and therefore that the third color also has no adjacent monochromatic pairs of vertices. We can conclude then that the described coloring is a valid 3-coloring of $G$.


What are the negative consequences of extending CIC with axioms?

One first reason to reject axioms is that they might be inconsistent. Even for the axioms that are proved consistent, some of them have a computational interpretation (we know how to extend definitional equality with a reduction principle for them) and some do not -- those break canonicity. This is "bad" for different reasons:

In theory, canonicity lets you prove things about the values of your language, without having to go to a specific model. This is a very satisfying property to have thinking about your system; in particular, it supports claims about the real world -- we can think of the nat type as formalized in the system as really "natural numbers" because we can prove that its closed normal inhabitants really are natural numbers. Otherwise it's easy to think that you modelled something correctly in your system, but actually be working with different objects.
In practice, reduction is a major asset of dependent type theories, because it makes proof easy. Proving a propositional equality can be arbitrarily difficult, while proving a definitional equality is (less often possible) but much easier, as the proof term is trivial. More generally, computation is a core aspect of the user experience of a proof assistant, and it is common to define things just so they reduce correctly as you expect. (You don't need axioms to make computation difficult; for example, using the conversion principle on propositional equalities can already block reductions). The entire business of proof by reflection is based on the use of computation to help proofs. This is a major difference in power and convenience with respect to other logics-based proof assistant (eg. HOL-light, which only supports equality reasoning; or see Zombie for a different approach), and using unchecked axioms, or other programming styles, can get you out of this comfort zone.


Maximum Positive Negative Set Cover Problem

This problem has a few simple constant-factor approximation algorithms, such as the trivial algorithm that picks the $C' \in \{\emptyset, C\}$ with a higher objective score.

Here's a loose constant-factor hardness result. No significant effort was put into optimizing the constant. I'm sure others can find something tighter.

Let $G = (V,E)$ be an instance of Max-Cut. We construct $A$, $B$, and $C$ as follows:

$A$ contains two vertices, $a_{u,v}$ and $a_{v,u}$, for each $(u,v) \in E$.
$B$ contains two vertices, $b_{u,v}$ and $b_{v,u}$, for each $(u,v) \in E$.
$C$ contains one set $c_v$ for each $v \in V$.
$c_v := \bigcup_{u \in \mathcal{N}(v)} \{a_{u,v}, a_{v,u}, b_{u,v}\}$, where $\mathcal{N}(v)$ denotes the neighborhood of $v$ in $E$.

Every subset of $C$ naturally corresponds to a collection of vertices from $V$ (i.e. via the subscripts). Call the set of vertices in this solution $V_C$.

Now for every edge $(u,v) \in E$, we count how many vertices from $\{a_{u,v}, a_{v,u}, b_{u,v}, b_{v,u}\}$ belong to $S = \left(A\cap \left(\bigcup_{c \in C} c\right)\right) \cup \left(B \setminus \left(\bigcup_{c \in C} c\right)\right)$.

If $u \in V_C$ and $v \in V_C$, then only $a_{u,v}$ and $a_{v,u}$ are in $S$.
If $u \in V_C$ and $v \not\in V_C$, then $a_{u,v}$, $a_{v,u}$, and $b_{u,v}$ are in $S$.
If $u \not\in V_C$ and $v \in V_C$, then $a_{u,v}$, $a_{v,u}$, and $b_{v,u}$ are in $S$.
If $u \not\in V_C$ and $v\not\in V_C$, then only $b_{v,u}$ and $b_{u,v}$ are in $S$.

Therefore, the total number of vertices in $S$ is equal to $2|E| + |\textrm{Cut}_E(V_C, V \setminus V_C)|$. Thus, the optimal solution involves a Max-Cut computation.

If it is hard to distinguish Max-Cut instances with optimal value $\geq \alpha |E|$ from those with value $\leq \beta |E|$, then for your problem it's hard to distinguish instances with optimal value $\geq (2+\alpha)|E|$ from those with value $\leq (2+\beta)|E|$, for a hardness of $\frac{2 + \beta}{2 + \alpha} = 1 - \frac{\alpha - \beta}{2 + \alpha} < 1 - (\alpha - \beta)/3$.

At this point we can plug in our favorite result on the hardness of max cut. E.g. UGC implies that we can choose $\alpha - \beta > .1$,$^*$ so this gives us a UGC gap of something less than $1-(1/10)/3 = 29/30$. Similar results can be had for NP-hardness, albeit with a slightly bigger constant.

$^*$ Note: this is not quite $1-\alpha_{GW}$, since $\alpha_{GW}$ measures the gap ratio rather than the gap difference.


Complexity reductions to Hamiltonian Path?

For undirected graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that

$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N-N^c$.

Karger Motwani Ramkumar 1997

For directed graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that

$G$ has $N=\operatorname{poly}(n)$ vertices
If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
If $I$ is not satisfiable, then $G$ has no path of length $N^{1-c}$.

Björklund Husfeldt Khanna 2004


Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

Serge Gaspers already mentioned why your conjecture is trivially true.

However, one can in fact get polynomial-time fixed-parameter isomorphisms,

which I now realize isn't that much less trivial, since it applies to every

ordered pair of non-trivial FPT problems with a reduction in the ordinary sense.

Let $c$ be an integer that's greater than the degree of the FPT algorithm for $\pi_1$,

and let $Y$ and $N$ be a yes and no instance respectively of $\pi_2$.

The following will be a polynomial-time fixed-parameter reduction from $\pi_1$ to $\pi_2$:

Try the FPT algorithm on $\pi_1$ for up to $n^{\hspace{.02 in}c}$ steps.

If that gives an answer, then output $Y$ or $N$ as indicated by that answer.

Otherwise, output the result of applying an ordinary polynomial-time reduction from $\pi_1$ to $\pi_2$.

Correctness and polynomial runtime are obvious. $\:$ Since $c$ is greater than the degree of the FPT algorithm for $\pi_1$, it's the case that for each fixed $k$, there are only finitely many input lengths $n$ for which the FPT algorithm's maximum runtime is not less than $n^{\hspace{.02 in}c}$. $\:$ Thus, for each fixed $k$, the above reduction has only finitely many outputs. $\:$ Therefore it satisfies your fixed-parameter condition.


Probability of a $k$-path in a random graph

When $k$ is a constant, the threshold probability for a path of length $k$ is $p \sim \dfrac{1}{n^{1+1/k}}$. The same is true for any tree with $k$ edges. The general result is that the threshold probability for the appearance of a subgraph $H$ is $max_{J \subseteq H} n^{-|V(J)|/E(J)|}$, which happens to be the same as $n^{-|V(H)|/E|(H)|}$ for balanced graphs $H$ (such as trees, complete graphs, cycles).

The situation is different when $k$ grows with $n$. I don't know what the threshold is, but looking at the Hamiltonian path case, I'd guess that an extra $\log n$ factor suffices.


Is the complexity of this path problem known?

Assume there are no self-edges in $G$.

For each edge between node $v_i$ and $v_j$ in $G$, let $E[i,j]=1$, and $E[i,j]=0$ if there is no edge. Compute $n\times n$ matrix $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$, which gives the number of two-hop paths between each pair of nodes $v_i$ and $v_j$. Then for edge between $v_i$ and $v_j$ in $G$ compute $D[i,j]=E[i,j]\cdot C[i,j]$ otherwise set $D[i,j]=\infty$, which gives the number of triangles the edge is part of (or infinity if there is no edge). The matrix multiplication needed to compute $C$ costs $O(n^3)$ (could be computed faster depending on sparsity of $G$).

Now compute $n\times n$ matrix $A$, such that $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$. $A$ is all shortest-paths in $D$ of length up to two augmented to account for paths that go along two edges of some triangle.

Now just compute the shortest path between $v_i$ and $v_j$ in $G$ on a new graph of which $A$ is the (weighted) adjacency matrix using Dijkstra (since all edge-weights are positive) i.e. and determine if $A^*[i,j]\leq k$, where $A^*$ is the closure over the tropical semiring (which gives the distance matrix).


Algebraic (or numeric) invariants of complexity classes

First of all, the relation you defined is usually called polynomial-time isomorphism ($\cong^p$). Although isomorphism is an interesting notion that has been studied, the (weaker) relation that is more frequently of concern in complexity is polynomial-time equivalence: $A$ and $B$ are equivalent ($A \equiv_m^p B$) if there are polynomial-time many-one reductions (aka Karp reductions) from $A$ to $B$ and vice versa, but those reductions need not be inverses to one another, and need not even have polynomial-time inverses. Sometimes we also care about equivalence under polynomial-time Turing reductions rather than many-one ($\equiv_T^p$), aka Cook reductions. For example, either of these notions of equivalence is "good enough" for $P$ vs $NP$ (that is, you don't need to consider isomorphism classes).

From the perspective of polynomial-time equivalence, there is partial "good reason" that you don't hear about numerical invariants: they can't work in general. A theorem in Andrew Marks's thesis states that $\equiv_T^p$ is complete for countable Borel equivalence relations (the introduction of his thesis gives a good overview of Borel equivalence relations and their significance). In particular, this implies that there is no Borel function $f: 2^{\mathbb{N}} \to \mathbb{R}$ such that $A \equiv_T^p B$ iff $f(A) = f(B)$.

The reason I say this is only partially a good reason is that there still might be a Borel function $f:2^{\mathbb{N}} \to \mathbb{R}$ such that if $f(A) \neq f(B)$ then $A \not\equiv_T^p B$. Or there might be a non-Borel function that does the job, but if there is we're a little unlikely to find it...

But classifying all equivalence classes is also stronger than what we usually care about, since the number of equivalence classes that show up as natural complexity classes is comparatively small (despite the forbidding size of the complexity zoo). However, there are other "numerical" invariants we can associate to languages. One such is their density: the density of a language $A$ is the function $d_A(n) :=$ number of strings in $A$ of length $\leq n$. Note that density is preserved, up to a polynomial change, by poly-time isomorphisms, but not necessarily by polynomial-time equivalences (e.g. all languages in $P$ are polynomial-time equivalent, but they can have wildly different densities).

We know things like: if $A$ is polynomially sparse ($d_A(n) \leq poly(n)$) then $A$ cannot be $NP$-complete unless $P=NP$ (Mahaney's Theorem). There are lots of other results about sparse languages and their relation to complexity classes. For good surveys, see Cai and Ogihara "Sparse Sets versus Complexity Classes" in Complexity Theory Retrospective II (available online - just Google) and Hemaspaandra and Glaßer's pair of articles "A Moment of Perfect Clarity I,II" in SIGACT News.

As mentioned by @SureshVenkat, you can kind of view Geometric Complexity Theory in the light you're talking about. However, the algebraic objects used there - namely representations - are more akin to general properties of a language than to numerical properties per se, but at least they are properties of an algebraic flavor.

Finally, in algebraic complexity theory one numerical property that's worth mentioning, but probably won't work to resolve the big questions, is degree. (As in the degree of a polynomial.) Strassen's degree bound is still the only known super-linear lower bound on unrestricted algebraic circuits. Degree also gets used e.g. in Razborov-Smolensky and many other areas of low-level (Boolean) circuit complexity.


Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

If you think of sets as living in universe $[u]$, it is quite easy to solve your problem with $O(\lg u)$ update time. All you need is a fast hash function for a vector of $u$ numbers, with fast "local updates".

Wikipedia/Universal hashing suggests $h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$, where $p$ is a large enough prime and $a$ is uniformly drawn from $[p]$. When you add or remove element $i$, you have to add/subtract $a^i$ from the hash code, which takes $O(\lg i)$ time using divide and conquer for the exponentiation. Since a polynomial of degree $u$ can only have $u$ roots, the probability of collision for two distinct sets is $O(u/p)$. This can be made very small by taking $p$ to be large enough (for instance, $p=u^2$ and you work in "double precision"). If the sets are much smaller than $[u]$, you can of course begin by hashing the universe down to a smaller universe.

Does anybody know a solution with $O(1/p)$ collision probability when hashing to range $[p]$? This ought to be possible.


Do any quantum algorithms improve on classical SAT?

Indeed, as wwjohnsmith1 said, you can get a square root speed-up over Schöning's algorithm for 3-SAT, but also more generally for Schöning's algorithm for k-SAT. In fact, many randomized algorithms for k-SAT can be implemented quadratically faster on a quantum computer.

The reason for this general phenomenon is the following. Many randomized algorithms for k-SAT that run in time $O(T(n) \mathrm{poly}(n))$ (where $T(n)$ is some exponentially growing function of $n$) actually do something stronger. At their core, there is a polynomial-time algorithm that outputs a satisfying assignment, if one exists, with probability at least $1/T(n)$. From this it is clear that if you repeat this poly-time algorithm $O(T(n))$ many times and accept if any of the runs returns a solution, you will get a randomized algorithm for k-SAT that runs in time $O(T(n) \mathrm{poly}(n))$.

Now instead of running this algorithm $O(T(n))$ times, you can run amplitude amplification on this poly-time algorithm. Amplitude amplification is a general quantum algorithm that can decide if another algorithm accepts with probability 0 or with probability $1/T$ using only $O(\sqrt{T})$ uses of this algorithm. Applying amplitude amplification to such a k-SAT solver will immediately yield a quantum algorithm for k-SAT with running time $O(\sqrt{T(n)}\mathrm{poly}(n))$, which is quadratically faster (ignoring the poly(n) term).


Which factors make the problem of inferring the grammar difficult?

Regarding the difficulty of learning grammars, let's stick to regular ones for concreteness. These are precisely the grammars/languages recognized by Deterministic Finite-state Automata (DFAs). The source of difficulty is purely computational; the statistical aspects are quite straightforward.

If you were able to find the smallest DFA consistent with your finite sample, simple Occam/cardinality arguments guarantee that this will generalize very well (it's the "optimal" learner in some sense). See Theorems 2 and 3 of Graepel et al.
http://research.microsoft.com/pubs/65635/graepelherbrichtaylor05.pdf
for actual state-of-the-art bounds.

However, finding such a small DFA is VERY hard (see Angluin, Gold, Pitt-Warmuth, etc):
http://www.sciencedirect.com/science/article/pii/S0019995878906836
http://web.mit.edu/6.863/www/spring2010/readings/gold67limit.pdf
http://dl.acm.org/citation.cfm?id=138042
[the latter even gives a hardness-of-approximation result].

But wait, it gets worse! Suppose you didn't care about a DFA and just wanted to learn the grammar in some representation (i.e., a mechanism for predicting the labels of test strings drawn from the same distribution as the training set).
If such an algorithm were to exist, and succeeded against all distributions, then it would also break RSA and related cryptographic primitives:
http://dl.acm.org/citation.cfm?id=697797


Mathematical background needed for pursuing a PhD in TCS

do the tripos!
its an incredibly awesome opportunity and many of its alums are fantastic computer scientists.

ultimately though its your life though  and you should do stuff because you'll enjoy it.


Check the match of the maximum of each subset

You can do the following. For every $i\in\{1,\dotsc,n\}$, start with the set $I=\{k\,:\,a_k\leqslant a_i\}$. Let $K=\{k\,:\,\exists j\ b_k^j=\max\{b^j_\ell\,:\,\ell\in I\}=a_i\}$. If $K=\emptyset$, then $I$ is a counterexample. If $i\in K$ then there is no counterexample with $i\in I$ and $a_i=\max\{a_k\,:\,k\in I\}$. If $K\neq\emptyset$ and $i\not\in K$ then any counterexample $J$ with $i\in J$ and $a_i=\max\{a_k\,:\,k\in J\}$ will be a subset of $I\setminus K$. So we can replace $I$ by $I\setminus K$, and iterate.

It is necessary and sufficient that for every $i$ we end up with $i\in K$.


Is it decidable to determine if a given shape can tile the plane?

According to the introduction of [1],

The complexity of determining if a single polyomino tiles the plane remains open [2,3], and
There is an undecidability proof for sets of 5 polyominoes [4].

[1] Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Open questions in tiling. Online, published 2000.

[3] C. Goodman-Strauss. Can’t decide? undecide! Notices of the American
Mathematical Society, 57(3):343–356, 2010.

[4] N. Ollinger. Tiling the plane with a fixed number of polyominoes. In
A. H. Dediu, A. M. Ionescu, and C. Mart´ın-Vide, editors, LATA 2009,
volume 5457 of LNCS, pages 638–647. Springer, 2009.


Deterministic Büchi + its complement covers LTL?

From your example, it is easy to derive a language $L$, such that neither $L$ nor its complement is recognized by a DBA.

Take an alphabet of four letter $\{a,b,c,d\}$, and let $L=((a+b)^* a^\omega)+(c^*d)^\omega$. It is not DBA-recognizable because of the $\{a,b\}$-part, and its complement is not because of the $\{c,d\}$-part.

For a less artificial example, you can for instance take on alphabet $\{a,b,c\}$ the language $L$ of words with infinitely many $b$ and finitely many $c$. Both $L$ and its complement have to check that the number of something is finite, so both are not DBA-recognizable.


Hardness of approximation - additive error

The question is somewhat open-ended, so I do not think that it can be answered completely.  This is a partial answer.

An easy observation is that many problems are uninteresting when we consider additive approximation.  For example, traditionally the objective function of the Max-3SAT problem is the number of satisfied clauses.  In this formulation, approximating Max-3SAT within an O(1) additive error is equivalent to solving Max-3SAT exactly, simply because the objective function can be scaled by copying the input formula many times.  Multiplicative approximation is much more essential for the problems of this kind.

[Edit: In earlier revision, I had used Independent Set as an example in the previous paragraph, but I changed it to Max-3SAT because Independent Set is not a good example to illustrate the difference between multiplicative approximation and additive approximation; approximating Independent Set even within an O(1) multiplicative factor is also NP-hard.  In fact, a much stronger inapproximability for Independent Set is shown by Håstad [Has99].]

But, as you said, additive approximation is interesting for the problems like bin packing, where we cannot scale the objective function.  Moreover, we can often reformulate a problem so that additive approximation becomes interesting.

For example, if the objective function of Max-3SAT is redefined as the ratio of the number of satisfied clauses to the total number of clauses (as is sometimes done), additive approximation becomes interesting.  In this setting, additive approximation is not harder than multiplicative approximation in the sense that approximability within a multiplicative factor 1−ε (0<ε<1) implies approximability within an additive error ε, because the optimal value is always at most 1.

An interesting fact (which seems to be unfortunately often overlooked) is that many inapproximability results prove the NP-completeness of certain gap problems which does not follow from the mere NP-hardness of multiplicative approximation (see also Petrank [Pet94] and Goldreich [Gol05, Section 3]).  Continuing the example of Max-3SAT, it is a well-known result by Håstad [Has01] that it is NP-hard to approximate Max-3SAT within a constant multiplicative factor better than 7/8.  This result alone does not seem to imply that it is NP-hard to approximate the ratio version of Max-3SAT within a constant additive error beyond some threshold.  However, what Håstad [Has01] proves is stronger than the mere multiplicative inapproximability: he proves that the following promise problem is NP-complete for every constant 7/8<s<1:

Gap-3SATs
Instance: A CNF formula φ where each clause involves exactly three distinct variables.
Yes-promise: φ is satisfiable.
No-promise: No truth assignment satisfies more than s fraction of the clauses of φ.

From this, we can conclude that it is NP-hard to approximate the ratio version of Max-3SAT within an additive error better than 1/8.  On the other hand, the usual, simple random assignment gives approximation within an additive error 1/8.  Therefore, the result by Håstad [Has01] does not only give the optimal multiplicative inapproximability for this problem but also the optimal additive inapproximability.  I guess that there are many additive inapproximability results like this which do not appear explicitly in the literature.

References

[Gol05] Oded Goldreich.  On promise problems (a survey in memory of Shimon Even [1935-2004]).  Electronic Colloquium on Computational Complexity, Report TR05-018, Feb. 2005.  http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad.  Clique is hard to approximate within n1−ε.  Acta Mathematica, 182(1):105–142, March 1999.  http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM, 48(4):798–859, July 2001.  http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank.  The hardness of approximation: Gap location.  Computational Complexity, 4(2):133–157, April 1994.  http://dx.doi.org/10.1007/BF01202286


In addition to what others say, I like the package todonotes for LaTeX that allows to have colorful reminders of what remains to do in the text.


Is Scott's reduction sound for $\mathrm{FO}^2$ with equality?

Yes. Just employ the formula $\forall{x}\forall{y} \; R(x,y) \leftrightarrow (x=y)$ (for a fresh binary predicate $R$), which allows you to "hide" the equality inside the $\forall\forall$-part of the Scott normal form. Then you proceed as usual.
EDIT: I've noticed that you wrote that $\alpha$ in $\forall{x}\forall{y} \; \alpha$ is a binary predicate. It is not true and obviously not all $\textit{FO}^2$ formulae are reducible to such a form. The aforementioned $\alpha$ should be a quantifier-free formula (line 13 of page 60 of the attached pdf). Maybe this is what made you problems while understanding the Scott reduction.


I believe the best result (with regards to the number of queries) is still Håstad's 3-query PCP. So if you choose at least 3, then it's a definite yes.

These lecture slides might be a bit more useful as they cut straight to the chase.


Inferring Cartesian position from a set of nodes where only distance is known

I think that "Trilateration" should solve your problem.

In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and navigation, including global positioning systems (GPS). In contrast to triangulation it does not involve the measurement of angles. ...


Communication complexity of finding common element of two subsets

(Reduction from set disjointness)

Suppose Alice and Bob are given sets $S, T \subseteq [n]$ with the guarantee
that $|S\cap T| \leq 1$. Alice and Bob run the protocol for finding the common
element of $S$ and $T$ assuming that their sets have a non-trivial intersection
to decide a common element $X$. Now, they can communicate with each other to
verify that $X$ is in fact common to both $S$ and $T$ with $O(\log n)$ bits.

Therefore, any protocol for finding the common element of $S$ and $T$ must take $\Omega(n)$ bits of communication.


Yes, this is a compactness property.

Let $X$ be the region you want to tile, and $T$ the finite set of possible tiles. The space $T^X$ of all assignments of tiles to $X$ is compact by Tychonoff’s theorem. For any finite $X_0\subseteq X$, the set $C_{X_0}\subseteq T^X$ of all correct tilings of $X_0$ is closed (in fact, clopen), and since $C_{X_0\cup X_1}\subseteq C_{X_0}\cap C_{X_1}$, they generate a filter. Thus, assuming every finite subset of $X$ can be tiled, the system $\{C_{X_0}:X_0\subseteq X\text{ finite}\}$ has fip, and by compacteness, its intersection is nonempty. This intersection is the set of all correct tilings of $X$.

Instead of all finite $X_0$, it suffices to use any family of finite subsets which is upwards directed and covers $X$, such as, in your case, the set of all finite square subregions of the plane.

Alternatively, you may set up the argument to use the compacteness of classical propositional logic: let $\{p_{x,t}:x\in X,t\in T\}$ be a set of propositional variables, and let $C$ be the theory consisting of the formulas
$$\begin{gather*}
\bigvee_{t\in T}p_{x,t},\qquad x\in X,\\
\neg(p_{x,t}\land p_{x,t'}),\qquad x\in X,t\ne t'\in T,
\end{gather*}$$
and
$$\neg(p_{x,t}\land p_{x',t'})$$
for all $x,x'\in X$ that are neighbours, and $t,t'\in T$ that are incompatible when placed on $x$ and $x'$, respectively. If each finite subset of $X$can be tiled, then $C$ is consistent, and any satisfying assignment gives a tiling of $X$.


Minimum number of transpositions to sort a list

If you're only dealing with permutations of $n$ elements, then you will need exactly $n-c(\pi)$ swaps, where $c(\pi)$ is the number of cycles in the disjoint cycle decomposition of $\pi$. Since this distance is bi-invariant, transforming $\pi$ into $\sigma$ (or $A$ into $B$, or conversely) requires $n-c(\sigma^{-1}\circ\pi)$ such moves.


For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is

in P if $L(\alpha)$ is finite;
coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$ for some $w_1,\ldots, w_k$);
PSPACE-complete otherwise.

[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages, Journal of Computer and System Sciences, Volume 12, Issue 2, 1976, Pages 222-268, ISSN 0022-0000, http://dx.doi.org/10.1016/S0022-0000(76)80038-4.
(http://www.sciencedirect.com/science/article/pii/S0022000076800384)


Does a weighted graph have a path with weight zero?

You can reduce Subset Sum to your problem.

Rough idea: Connect s,t with chain of double edges corresponding to weights and zero. A path from s to t picks a subset.
These double edges can be expanded with dummy nodes to make a normal graph. To ensure non-empty subset make n chains to t with initial single edge corresponding to weight.


Best SAT upper bounds based on number of clauses

It's of the order 2^{0.30897m}, see http://logic.pdmi.ras.ru/~hirsch/abstracts/sodafull.html

(I am not aware of improvements for the number of clauses.)


Algorithms for computing the minimal vertex separator of a graph

A simple way to find just some minimal $u$-$v$-separator is to find one that is close to $u$. A separator $S$ is called close to $u$ if $S \subseteq N_G(u)$. This is actually very easy and can be done in time $O(n + m)$. Consider the graph $G - N_G(u)$ where $u$ is isolated and $v$ lies in some different component, $C$, which simply contains all vertices which are reachable from $v$. Now, adding the vertices $N_G(u)$ back to the graph, the neighbors $N_G(C)$ of $C$ form a minimal $u$-$v$-separator.

Suppose this was not the case, then there exists $x \in N_G(C)$ such that $N_G(C) \setminus \{x\}$ still separates $u$ and $v$. As $x$ is a neighbor of $u$ and also a neighbor of some vertex in $C$, there exists a path from $u$ through $x$ to $C$, from which $v$ can be reached, a contradiction.

To find $N_G(C)$ in linear time, we can first traverse the neighborhood of $u$ and mark all of its neighbors with some color, say blue. This takes time $O(n)$. Then, we start a DFS at $v$ and mark all reachable vertices with another color, say red. However, when a blue vertex is encountered, it is not visited but simply added to another set, $S$. In the end, $S$ contains all neighbors of $C$. The running time of a DFS is $O(n + m)$, including the time that is needed for checking whether a vertex is blue, and adding it to $S$.

Also, in general any set $S \subseteq V(G)$ which separates $u$ and $v$ can be made minimal in time $O(nm)$ by the following steps:
for each $x \in S$, test whether $S \setminus \{x\}$ still separates $u$ and $v$. If it does, remove $x$ from $S$ and repeat this step. As $S$ can contain at most $n - 2$ vertices and checking whether $u$ and $v$ are still separated can be done by a simple DFS in time $O(m)$, the total time needed is $O(nm)$.


Minimum relevant variables in linear system - additive approximation

Unless $P=NP$, there does not exist a polynomial time approximation algorithm that returns solutions of value at most $\text{OPT}+d$.

Suppose otherwise, and consider some fixed $d$ for which there does exist such an  approximation algorithm $A$. We construct a new multiplicative polynomial time approximation algorithm from $A$, that always returns solutions of value at most $2\cdot\text{OPT}$. Hence consider an arbitrary instance $I$ of Min-RVLS:

For all $k=1,\ldots,d$ check whether $I$ has a solution $x$ with $k$ nonzero variables. This can be done by checking every subset $S$ of $k$ Variables: Set all variables outside $S$ to zero, and solve the linear equation system for the remaining variables. Since there are only $O(n^d)$ subsets to be checked, the overall running time is polynomial. (Here we use that $d$ is a fixed integer.)
If the first step does not reveal any feasible solution, we know that $\text{OPT}>d$. We call the additive approximation algorithm $A$ and find in polynomial time a feasible solution of value at most $\text{OPT}+d<2\cdot\text{OPT}$.

As we either detect an optimal solution (first step) or a solutions with value at most twice the optimum (second step), the resulting polynomial time approximation algorithm
has a multiplicative approximation guarantee of $2$.


determining if a matrix of linear forms represents a non-degenerate matrix

This answer summarizes and expands my comments above:

1) If the size of the underlying field is large enough, then this problem has efficient randomized algorithms: You have to test whether the resulting determinant is nonzero as a polynomial. You can use the Schwartz-Zippel lemma for this. (Search for the keyword "Polynomial Identity testing"
for further algorithms/results.)

2) The question whether this problem can be derandomized is open.
Derandomizing it implies circuit lower bounds. See the work by Kabanets & Impagliazzo. (Comput. Complexity 13, 2004, http://www.cs.sfu.ca/~kabanets/Research/poly.html), the problem is called
SDIT (Symbolic Determinant Identity testing) in the paper.

3) Gurvits has a deterministic algorithm for some special cases of SDIT
(http://dx.doi.org/10.1145/780542.780545). He refers to SDIT as "Edmond's problem". (This item was provided by Joshua Grochow. I suggest that when
you want to upvote my answer, you should upvote any of his answers with probability 1/4 instead.)

4) Over finite fields (size is fixed), it is NP-complete. Over GF(2), you can just arithmetize a given formula in 3-CNF (that is, write it as an equivalent arithmetic formula)
and then use fact that you can write any arithmetic formula as a poly-size determinant (proven by Valiant, see also Bürgisser, Clausen, Shokrollahi,
Algebraic Complexity Theory, Chapter 21). Over other finite fields, you can start with appropriate CSPs instead of 3-SAT.


What is the number of languages accepted by a DFA of size $n$?

I think that this question has been studied previously. Mike Domaratzki wrote a survey on research in this area:
"Enumeration of Formal Languages", Bull. EATCS, vol. 89 (June 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf