5 papers
Improved lower bounds for the Shannon capacity of odd cycles
Nathaniel Itty, Christopher D. Rosin, Chase Carstensen +1
The Shannon capacity of a graph quantifies the maximum rate at which information can be transmitted with zero error over a noisy channel. It is lower bounded by $α(G^d…
Improved Upper Bounds for Slicing the Hypercube
Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin +5
A collection of hyperplanes slices all edges of the -dimensional hypercube with vertex set if, for every edge in the hypercube, there exists…
Automated Discovery of Improved Constant Weight Binary Codes
Christopher D. Rosin
A constant weight binary code consists of -bit binary codewords, each with exactly bits equal to 1, such that any two codewords are at least Hamming distance apart. $A(n…
Optimal Depth-Three Circuits for Inner Product
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +2
We show that Inner Product in variables, , can be computed by depth-3 bottom fan-in 2 circuits of size $\mathsf{poly}…
Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +3
Gurumuhkani et al. (CCC'24) introduced the local enumeration problem as follows: for a natural number and a parameter , given an -variate -CNF with no sat…