Group decision-making is a ubiquitous phenomenon with diverse applications ranging from political elections to recommender systems and from organ exchanges to online marketplaces.
Expander graphs are sparse but highly connected graphs, which find a variety of uses in CS. If the vertices of an expander are labelled by 0 or 1, a $t$-step walk gives a $t$-bit string.
A directed graph is said to be k-vertex-connected if after deleting any k-1 vertices, therer is a directed path from every vertex to every other vertex along the directed edges.
Cryptography is a beautiful branch of theoretical computer science that seeks to provide guarantees to the art of secret keeping. The questions it poses are fundamental -- does the universe permit asymmetry of computation?
One of the fundamental issues facing deployment of supervised learning models in real life applications is the issue of out-of-distribution (OOD) generalization.
Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)).