In the context of finite, simple, undirected graphs, associate with each node $v\in V$ an integer $n(v)$ (you can limit this to positive integers without loss of generality). Create the set of edges by defining a threshold $T$, and join an edge $x,y$ iff $n(x)+n(y) \geq T$. These are called threshold graphs$^{[1]}$ and they are well-studied, their structure has been characterized. If, instead, $x,y$ are joined by an edge iff $n(x)+n(y)=0\ (mod\ T)$, we form another very simple class of graphs. But have they been studied and do they have a name? $^{[1]}$ Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.

In the (unweighted) minimum k-cut problem, the goal is to partition the nodes in a given graph to at least $k$ subsets, such that the number of edges between different subsets is as small as possible. I am interested in a variant in which the number of subsets is not fixed in advance, but there can be at most $t$ vertices in each subset. So the goal is to partition the nodes into subsets of cardinality at most $t$, such that the number of edges between different subsets is as small as possible. Is there a polynomial-time algorithm for this problem, assuming $t$ is fixed? And assuming $t$ is part of the input?

I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$. It is also very easy, from a monoid $M$ and a morphism $\mu:\Sigma^*\to M$, to build an equivalent deterministic automaton $A(M)$ by using the monoid itself as the set of states and the morphism to build the transition function. However, if I understand well, $A(M(L))\ne A(L)$, i.e. the syntactic monoid is the transition monoid of the minimal automaton, but the automaton I trivially get from the syntactic monoid is not the minimal automaton. Of course, to get $A(L)$ one could minimize $A(M(L))$, but I wonder if there is a more direct definition or construction. So if the above is correct, is there a way to get the actual minimal automaton $A(L)$ from the syntactic monoid $M(L)$, without building $A(M(L))$ and then minimize it?

The Brouwer fixpoint theorem states that any continuous mapping $f$, from a convex, compact set to itself will contain a fixpoint. The Brouwer algorithm finds these (approximate) fixpoints. But how is a continuous function inputted into this algorithm? Is it as a black box? If so, would changing this to a discrete set of points change the complexity of the algorithm?

I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated. So far I've found two. One is $L_1=\{a^ku\,\,|\,\,u\in \{a,b\}^∗$ and $u$ contains at least $k$ $a$'s, for $k\geq 1\}$, from this post, and the other is $L_2 = \{uww^rv\,\,|\,\, u,w,v\in\{a,b\}^+\}$, which is an exercise (exercise 19 from section 4.3) in An Introduction to Formal Languages and Automata by Peter Linz. I suppose the aspect of seeming to be regular depends on your familiarity with the topic, but, for me, I would have said that those languages were not regular at a first glance. The trick seems to be to write a simple language in more complicated terms, like using $ww^R$, which reminds us of the irregular language of even length palindromes. I'm not looking for extremely complicated ways of expressing a regular language, just some examples where the definition of the language seems to rely on concepts that usually make a language irregular, but are then "absorbed" by the other terms in the definition.

In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has been strengthened later, showing that, in the limit, almost all boolean functions have exponential circuit complexity. It is often said that, even in 2022, we still cannot construct a single example of such a function. I'm interested in, and slightly confused about, the state-of-the-art in research on this question. In particular: - Wikipedia [2] states that "complexity theorists have only been able to prove superpolynomial circuit lower bounds on functions explicitly constructed for the purpose of being hard to calculate" which seems to contradict that no explict function is know. - Are there any candidate boolean functions (or family of functions) that are conjectured to have exponential circuit complexity, but where this has not been proven? - What is the state of exhaustive exploration of the circuit complexity of $n$-ary boolean functions? Presumably there is some small $n$ such that this complexity has been computed for all $i - C. E. Shannon, The synthesis of two-terminal switching circuits https://ia802700.us.archive.org/6/items/bstj28-1-59/bstj28-1-59.pdf - Wikipedia entry Circuit complexity https://en.wikipedia.org/wiki/Circuit_complexity#History

In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems. Question: I was wondering if there exists something like a database or a book with some known reductions (or with maybe more than only the NP-complete ones) and the proofs for them? I know there is a very nice database for Rings, but I couldn't find something similar for reductions.

Problem. Given positive integers $a$ and $b$, obtain $\frac{a}{b}$ without using division ($/$) directly, though addition ($+$), subtraction ($-$), multiplication ($\times$) and bit-shifts ($\gg$ and $\ll$) are allowed. Is there a good algorithm to solve the aforementioned problem? This algorithm does not have to be very accurate and $4$ decimal places would be good enough, e.g., $$\frac{222}{103} \approx 2.1553$$ Could anyone please give some advice or references?

It is known that neural networks, such as convolutional neural networks, struggle with pattern recognition if training sets contain ambiguities (i.e. several labels can correspond to one and the same pattern). However, I struggle to locate the paper that directly discusses this issue, or demonstrates it for the first time, etc. If anybody can point me to the paper(s), that would really help. Thanks!

I just finished watching the 1986 SICP lectures, and the concepts are rolling around in my head. My question: why is "finite-state controller with datapath" the implementation of computer programs we use? I can think of a few of types of answers, which have different emphases: - We don't use it: there are various implementations of computation in use; this is just one of the more important ones. - We don't use it: it is a pedagogical abstraction which isn't a total lie, but when you get into microarchitecture, the trade-offs at multiple levels of design yield implementations which defy simple categorization. - This model has arisen over time through a selection process, with selection pressures from economics and managability of design. Types 1 and 3 are enticing to me, because these would endeavor to explain the comparative advantages of FSCwD compared to other models/implementations of computing. (And explain what those other models are along the way.) Note I'm not asking about models of computation as such, as those are about how to model computation conceptually, not how to model the implementation of computation on hardware. Lastly let me say I am aware that a thorough answer to this question would constitute a whole book or more; therefore I am looking for "leads" in my search (search terms, particular books or articles). I've been searching things like - Models of computation - FSM with datapath - Processor design etc, but none of them have so far have compared various models of implementation.