Seja , B i uma sequência de matrizes circulantes de tamanho n × n .UMAEuAiA_{i}BEuBiB_{i}n × nn×nn \times n Sabemos que pode ser calculado em tempo quadrático (use FFT para diagonalizar e adicionar matrizes diagonais e aplicar IFFT).∑ni = 1UMAEuBEu∑i=1nAiBi\sum_{i=1}^{n}A_{i}B_{i} Supondo é uma...
No artigo "Assinaturas curtas do emparelhamento Weil" de Boneh, Lynn e Shacham, eu estava examinando a prova de segurança como qualquer outra assinatura. Mas a técnica usada neste artigo é bastante única. Em vez de usar a interação normal do desafiante e do adversário, eles dividiram a prova em 6...
Estou curioso para saber se existem documentos sobre a capacidade de os dados de imagem alterados esteganograficamente manterem sua integridade depois de terem sido recodificados em um formato diferente (por exemplo, de PNG para JPEG). Essa é uma característica inerente às boas implementações de...
Existem maneiras de conhecer novas posições de doutorado no TCS, além de procurar nos sites dos grupos de universidades / pesquisa? Talvez pessoas de diferentes ramos (teoria de tipos, verificação, complexidade etc.) possam nomear algumas listas de discussão especializadas nas quais os anúncios...
Existe um método trivial para simular uma caminhada aleatória através de um gráfico, exponenciando uma matriz de adjacência estocástica, mas o problema se torna mais difícil se você solicitar que a caminhada aleatória seja auto-evitável. Em outras palavras, o processo deve percorrer o gráfico...
Seja uma dada matriz quadrada. Existe alguma evidência de que ultrapassar limites inferiores quadráticos para modo que possa ser difícil?B det ( B ) = por ( A )UMAAABBBdet ( B ) = por ( A )det(B)=per(A)\text{det}(B) = \text{per}(A) Existe alguma conjectura plausível que implique que provar...
Quais são os resultados mais conhecidos para uma estrutura de dados que oferece as seguintes operações em conjuntos de pontos no espaço euclidiano bidimensional: insert(x)insert(x)insert(x) delete(x)delete(x)delete(x) (onde k é um número inteiro maior que 0) retorna os k pontos mais próximos de...
Considere o seguinte algoritmo, em que é uma constante fixa.ccc void partition(A[1..m], B[1..n]) { if m=1 or n=1 return k = random(min(c,m,n)); partition A into k sublists Asub[1..k] at k-1 distinct random indices partition B into k sublists Bsub[1..k] at k-1 distinct random indices for i...
Dado um grupo agindo em um conjunto X com uma ordem total ≤ e x ∈ X , qual é o algoritmo mais eficiente para decidir se x é ou não o menor elemento em sua órbita, ou seja, decidir se m i n ( G x ) = x ?GGGXXX≤≤\leqx∈Xx∈Xx\in Xm i n(Gx)=xmin(Gx)=x min(Gx) = x Minha motivação vem da solução SMT,...
Estou tentando desenvolver algumas noções de cálculo de diferença entre uma Máquina Ideal de Turing ideal concebida por um desenvolvedor (por exemplo, o que se pretende que um desenvolvedor de software), chame de , e as Máquinas que representam o software que realmente é projetado e implementado,...
Alice quer passar uma mensagem para um grande número de pessoas que vivem sob um governo feliz de censura, administrado por Eve. A maneira tradicional de fazer isso é o samizdat, mas esse processo exige que cada pessoa que passa uma mensagem corra um certo risco. Seria bom que houvesse alguma...
Muitos resultados em criptografia dependem de resultados / conjecturas de impossibilidade na teoria da complexidade. Por exemplo, acredita-se que a criptografia de chave pública usando RSA é possível devido à conjectura sobre a inviabilidade do fatoramento (e os problemas de localização modular da...
Edit: Eu acho que o espírito da pergunta era bom, mas precisa ser melhorado. As suposições feitas para o sorteio fizeram com que essa pergunta fosse trivial, e a rolagem do dado ainda não está definida com precisão suficiente. Quais são as suposições razoáveis que podemos fazer sobre uma...
É bem conhecido que os gráficos planares de um familiar fechado com menores proibidos , gráficos com treewidth limitada também são gráficos da família fechados sem H k como menor.K3,3,K5K3,3,K5K_{3,3}, K_{5}HkHkH_{k} Suponho que gráficos com corte máximo delimitado fechem gráficos de família. Dado...
Estamos trabalhando em um artigo que apresenta alguns algoritmos para encontrar triângulos e motivos de rede (subgráficos de tamanho constante, também conhecidos como gráficos) em uma configuração distribuída. Caracterizamos a troca entre o número de triângulos no gráfico e a carga de comunicação...
O lema de corte (também conhecido como lema de decomposição celular) afirma que, dadas linhas no plano, é possível dividi-lo em regiões (triângulos pares) para qualquer modo que o interior de qualquer região é interceptada por linhas . Para mais informações, ver, por exemplo, o livro de Matousek,...
A idéia de um MST com diâmetro restrito é que você mantenha todos os vértices conectados e a uma certa distância um do outro. Mas todos os papéis que eu vi cumprem a exigência de que você produza uma árvore, ao permitir ciclos pode ajudar a reduzir o diâmetro. Alguém conhece algum artigo que...
Embora seja muito comum ver músicos, pintores, autores e arquitetos de autodidatas bem-sucedidos - não estou familiarizado com nenhum autodidata famoso no campo da TCS. Existem exemplos de um cientista da computação teórico do autodidata (alguém que publicou um artigo importante, sem nunca ter...
Um aluno me perguntou o seguinte e não conseguiu encontrar uma resposta completa: Existem propriedades de fechamento para a classe de idiomas que não são livres de contexto? É bastante fácil encontrar exemplos que mostram que ele não está fechado sob interseção e iteração (operador estrela...
Suponha que haja partes , cada uma com um pouco . Eu quero calcular a multiplicação do número de vezes o número de zeros, ou seja, .p j b j ∈ { 0 , 1 } R = ( ∑ b j ) × ( N - ∑ b j )N>2N>2N>2pjpjp_jbj∈{0,1}bj∈{0,1}b_j\in{\{0,1\}}R=(∑bj)×(N−∑bj)R=(∑bj)×(N−∑bj)R=(\sum{b_j})\times(N-\sum{b_j}) O...