We display an application of the notions of kernelization and data reduction from parameterized complexity to proof complexity: Specifically, we show that the existence of data reduction rules for a parameterized problem having (a). a small-length reduction chain, and (b). small-size (extended) Frege proofs certifying the soundness of reduction steps implies the existence of subexponential size (extended) Frege proofs for propositional formalizations of the given problem. We apply our result to infer the existence of subexponential Frege and extended Frege proofs for a variety of problems. Improving earlier results of Aisenberg et al. (ICALP 2015), we show that propositional formulas expressing (a stronger form of) the Kneser-Lovász Theorem have quasipolynomial size Frege proofs for each constant value of the parameter k. Another notable application of our framework is to impossibility results in computational social choice: we show that, for any fixed number of agents, propositional translations of the Arrow and Gibbard-Satterthwaite impossibility theorems have subexponential size Frege proofs.

A heapable sequence is a sequence of numbers that can be arranged in a min-heap data structure. Finding a longest heapable subsequence of a given sequence was proposed by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011) as a generalization of the well-studied longest increasing subsequence problem and its complexity still remains open. An equivalent formulation of the longest heapable subsequence problem is that of finding a maximum-sized binary tree in a given permutation directed acyclic graph (permutation DAG). In this work, we study parameterized algorithms for both longest heapable subsequence and maximum-sized binary tree. We introduce alphabet size as a new parameter in the study of computational problems in permutation DAGs and show that this parameter with respect to a fixed topological ordering admits a complete characterization and a polynomial time algorithm. We believe that this parameter is likely to be useful in the context of optimization problems defined over permutation DAGs.

A heapable sequence is a sequence of numbers that can be arranged in a min-heap data structure. Finding a longest heapable subsequence of a given sequence was proposed by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011) as a generalization of the well-studied longest increasing subsequence problem and its complexity still remains open. An equivalent formulation of the longest heapable subsequence problem is that of finding a maximum-sized binary tree in a given permutation directed acyclic graph (permutation DAG). In this work, we study parameterized algorithms for both longest heapable subsequence and maximum-sized binary tree. We introduce alphabet size as a new parameter in the study of computational problems in permutation DAGs and show that this parameter with respect to a fixed topological ordering admits a complete characterization and a polynomial time algorithm. We believe that this parameter is likely to be useful in the context of optimization problems defined over permutation DAGs.

In this paper we advocate the study of discrete models of social dynamics underadversarial scheduling. The approach we propose forms part of a foundational basis for agenerative approach to social science(Epstein 2007). We highlight the feasibility of the adversarial scheduling approach by using it to study thePrisoners's Dilemma Game with Pavlov update, a dynamics that has already been investigated under random update in Kittock (1994), Dyeret al. (2002), Mossel and Roch (2006) and Dyer and Velumailum (2011). The model is specified by letting players at the nodes of an underlying graphGrepeatedly play the Prisoner's Dilemma against their neighbours. The players adapt their strategies based on the past behaviour of their opponents by applying the so-called win–stay lose–shift strategy. With random scheduling, starting from any initial configuration, the system reaches the fixed point in which all players cooperate with high probability. On the other hand, under adversarial scheduling the following results hold: — A scheduler that can selectbothgame participants can preclude the system from reaching the unique fixed point on most graph topologies. — A non-adaptive scheduler that is only allowed to chooseoneof the participants is no more powerful than a random scheduler. With this restriction, even an adaptive scheduler is not significantly more powerful than the random scheduler, provided it is ‘reasonably fair’.

We study nondeterministic and probabilistic versions of a discrete dynamical system (due to T. Antal, P. L. Krapivsky, and S. Redner [3]) inspired by Heider's social balance theory. We investigate the convergence time of this dynamics on several classes of graphs. Our contributions include: 1. We point out the connection between the triad dynamics and a generalization of annihilating walks to hypergraphs. In particular, this connection allows us to completely characterize the recurrent states in graphs where each edge belongs to at most two triangles. 2. We also solve the case of hypergraphs that do not contain edges consisting of one or two vertices. 3. We show that on the so-called "triadic cycle" graph, the convergence time is linear. 4. We obtain a cubic upper bound on the convergence time on 2-regular triadic simplexes G. This bound can be further improved to a quantity that depends on the Cheeger constant of G. In particular this provides some rigorous counterparts to experimental observations in [25]. We also point out an application to the analysis of the random walk algorithm on certain instances of the 3-XOR-SAT problem.

Phase transitions in combinatorial problems have recently been shown to be useful in locating "hard" instances of combinatorial problems. The connection between computational complexity and the existence of phase transitions has been addressed in statistical mechanics and artificial intelligence, but not studied rigorously. We take a first step in this direction by investigating the existence of sharp thresholds for the class of generalized satisfiability problems, defined by T.J. Schaefer (1978). In the case when all constraints have a special clausal form we completely characterize the generalized satisfiability problems that have a sharp threshold. While NP-completeness does not imply the sharpness of the threshold, our result suggests that the class of counter examples is rather limited, as all such counter examples can be predicted, with constant success probability by a single procedure.

We define a version of structural equivalence of ET0L grammars, called strong equivalence, that takes into account their matrix structure, and prove its decidability.